NBA* и есть двунаправленный А*, его особенность в том, что он делает после того как оба поиска встретились, и в том, как он учитывает эвристики с противоположной стороны поиска. Когда поиск вперед раздумывает зайти ли в узел или нет, он так же смотрит на эвристику обратного поиска — здесь f2 инициализровано обратным поиском. Доказательство корректности можно найти здесь: https://repub.eur.nl/pub/16100/ei2009-10.pdf
Да, у меня тоже алгоритмы приоретизируют направление, которое наиболее вероятно приведет к целе (функция-эвристика дает примерную оценку от точки А1 к цели, точки с наименьшей оценкой будут рассмотрены в первую очередь)
Это не совсем верно. Все поисковики в моей библиотеке находят кратчайший путь, за исключением A* greedy.
Алгоритм Дейкстры — это частный случай алгоритма A* — просто функция эвристика всегда отдает 0.
Я так понял DaylightIsBurning сказал что 20-50ms будет скорость поиска кратчайшего пути, если использовать WebAssembly — потому мне хотелось узнать подробнее о методе/коде.
Спасибо! Развитие в виде продукта я не планировал. А вот чтобы быстро подменить алгоритм нужно добавить его ключ/имя сюда, чтобы показывался в выпадающем списке. Потом для этого ключа нужно создать поисковик здесь — у поисковика только один метод find(fromNodeId, toNodeId), вернуть он должен массив узлов графа.
Можете также прислать ссылку на демо вашего алгоритма, если он публичный — я помогу потестировать.
Хороший вопрос! Я когда-то считал pagerank в javascript'e и ради интереса написал алгоритм на asm.js и на типизированных массивах. Только что проверил на node 7.2.1, asm.js все еще медленнее чем типизированные массивы раза в пять (60 операций в секунду против 12). Мозиловский javascript движок, конечно, выигрывал на asm.js версии, когда проверял его несколько лет назад
Вы правы. Меня больше смущало отсутствие потокового парсинга JSON'a. Ну и потом, работа напрямую с типизрованными массивами потенциально дает возможность загнать данные сразу в видеобуфер. Не то, чтобы я это делал, но все же :)… Впрочем, глядя критично на вещи, не исключено что я тут чуть-чуть занялся велосипедостроительством и преждевременной оптимизацией.
> Ну а на сколько эффективнее (меньше) получилось чем JSON, XML/gzip?
Карта Москвы из 7.1МБ превратилась в 6.5МБ. Не сильно
Спасибо за дельный совет!
NBA*и есть двунаправленныйА*, его особенность в том, что он делает после того как оба поиска встретились, и в том, как он учитывает эвристики с противоположной стороны поиска. Когда поиск вперед раздумывает зайти ли в узел или нет, он так же смотрит на эвристику обратного поиска — здесьf2инициализровано обратным поиском. Доказательство корректности можно найти здесь: https://repub.eur.nl/pub/16100/ei2009-10.pdfПроблема с бесконечным скролом интересная, конечно! Увы, у меня сейчас другие приоритеты.
Если вы на реакте пишете, то вот эта библиотека выглядит очень многообещающе: github.com/bvaughn/react-virtualized
Да, у меня тоже алгоритмы приоретизируют направление, которое наиболее вероятно приведет к целе (функция-эвристика дает примерную оценку от точки А1 к цели, точки с наименьшей оценкой будут рассмотрены в первую очередь)
Мне кажется, я видел эту петлю на гуглокартах — есть подозрение что это единственный путь к точке B
Это не совсем верно. Все поисковики в моей библиотеке находят кратчайший путь, за исключением
A* greedy.Алгоритм Дейкстры — это частный случай алгоритма
A*— просто функция эвристика всегда отдает 0.Я так понял DaylightIsBurning сказал что 20-50ms будет скорость поиска кратчайшего пути, если использовать WebAssembly — потому мне хотелось узнать подробнее о методе/коде.
Примерно так. Вот запрос который я выполняю для получения дорог.
Маршрут действительно строится без весов.
Спасибо. Да, я тоже использую кучу для всех реализаций (включая Дейкстру)
Я использовал тот же код что и для
А*— просто эвристику в ноль поставил.Можете рассказать подробнее что это означает, пожалуйста?
Спасибо! Развитие в виде продукта я не планировал. А вот чтобы быстро подменить алгоритм нужно добавить его ключ/имя сюда, чтобы показывался в выпадающем списке. Потом для этого ключа нужно создать поисковик здесь — у поисковика только один метод
find(fromNodeId, toNodeId), вернуть он должен массив узлов графа.Можете также прислать ссылку на демо вашего алгоритма, если он публичный — я помогу потестировать.
Хороший вопрос! Я когда-то считал
pagerankв javascript'e и ради интереса написал алгоритм на asm.js и на типизированных массивах. Только что проверил наnode 7.2.1, asm.js все еще медленнее чем типизированные массивы раза в пять (60 операций в секунду против 12). Мозиловский javascript движок, конечно, выигрывал на asm.js версии, когда проверял его несколько лет назадВы правы. Меня больше смущало отсутствие потокового парсинга JSON'a. Ну и потом, работа напрямую с типизрованными массивами потенциально дает возможность загнать данные сразу в видеобуфер. Не то, чтобы я это делал, но все же :)… Впрочем, глядя критично на вещи, не исключено что я тут чуть-чуть занялся велосипедостроительством и преждевременной оптимизацией.
> Ну а на сколько эффективнее (меньше) получилось чем JSON, XML/gzip?
Карта Москвы из 7.1МБ превратилась в 6.5МБ. Не сильно
Если на гитхабе поискать 0x00 extension:lua то можно найти примеры