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 то можно найти примеры
Самые популярные слова в двух терабайтах кода
Самые популярные слова в двух терабайтах кода