Открыть список
Как стать автором
Обновить
203.2
Карма
0
Рейтинг
anvaka @anvaka

Пользователь

Библиотека быстрого поиска путей на графе

Спасибо за дельный совет!


NBA* и есть двунаправленный А*, его особенность в том, что он делает после того как оба поиска встретились, и в том, как он учитывает эвристики с противоположной стороны поиска. Когда поиск вперед раздумывает зайти ли в узел или нет, он так же смотрит на эвристику обратного поиска — здесь f2 инициализровано обратным поиском. Доказательство корректности можно найти здесь: https://repub.eur.nl/pub/16100/ei2009-10.pdf

Библиотека быстрого поиска путей на графе

Спасибо :)

Проблема с бесконечным скролом интересная, конечно! Увы, у меня сейчас другие приоритеты.

Если вы на реакте пишете, то вот эта библиотека выглядит очень многообещающе: github.com/bvaughn/react-virtualized

Библиотека быстрого поиска путей на графе

Спастбо за детальный ответ!

Да, у меня тоже алгоритмы приоретизируют направление, которое наиболее вероятно приведет к целе (функция-эвристика дает примерную оценку от точки А1 к цели, точки с наименьшей оценкой будут рассмотрены в первую очередь)

Библиотека быстрого поиска путей на графе

Мне кажется, я видел эту петлю на гуглокартах — есть подозрение что это единственный путь к точке B

Библиотека быстрого поиска путей на графе

С удовольствием прочту о вашем методе, который дает 50-разовый прирост производительности в браузере!

Библиотека быстрого поиска путей на графе

Это не совсем верно. Все поисковики в моей библиотеке находят кратчайший путь, за исключением A* greedy.


Алгоритм Дейкстры — это частный случай алгоритма A* — просто функция эвристика всегда отдает 0.


Я так понял DaylightIsBurning сказал что 20-50ms будет скорость поиска кратчайшего пути, если использовать WebAssembly — потому мне хотелось узнать подробнее о методе/коде.

Библиотека быстрого поиска путей на графе

Примерно так. Вот запрос который я выполняю для получения дорог.


Маршрут действительно строится без весов.

Библиотека быстрого поиска путей на графе

Спасибо. Да, я тоже использую кучу для всех реализаций (включая Дейкстру)

Библиотека быстрого поиска путей на графе

все ли до того как добраться до оценки было «выжато» из Дейкстры?

Я использовал тот же код что и для А* — просто эвристику в ноль поставил.


типа модели поиска минимального значения

Можете рассказать подробнее что это означает, пожалуйста?

Библиотека быстрого поиска путей на графе

Спасибо! Развитие в виде продукта я не планировал. А вот чтобы быстро подменить алгоритм нужно добавить его ключ/имя сюда, чтобы показывался в выпадающем списке. Потом для этого ключа нужно создать поисковик здесь — у поисковика только один метод find(fromNodeId, toNodeId), вернуть он должен массив узлов графа.


Можете также прислать ссылку на демо вашего алгоритма, если он публичный — я помогу потестировать.

Библиотека быстрого поиска путей на графе

Очень интересно! Откуда данные? Можно ли посмотреть на код?

Библиотека быстрого поиска путей на графе

Интересно. Я думал wasm это просто asm.js завернутый в бинарный формат. Это не так?

Библиотека быстрого поиска путей на графе

Хороший вопрос! Я когда-то считал pagerank в javascript'e и ради интереса написал алгоритм на asm.js и на типизированных массивах. Только что проверил на node 7.2.1, asm.js все еще медленнее чем типизированные массивы раза в пять (60 операций в секунду против 12). Мозиловский javascript движок, конечно, выигрывал на asm.js версии, когда проверял его несколько лет назад

Библиотека быстрого поиска путей на графе

> gzip распаковывается браузером.

Вы правы. Меня больше смущало отсутствие потокового парсинга JSON'a. Ну и потом, работа напрямую с типизрованными массивами потенциально дает возможность загнать данные сразу в видеобуфер. Не то, чтобы я это делал, но все же :)… Впрочем, глядя критично на вещи, не исключено что я тут чуть-чуть занялся велосипедостроительством и преждевременной оптимизацией.

> Ну а на сколько эффективнее (меньше) получилось чем JSON, XML/gzip?

Карта Москвы из 7.1МБ превратилась в 6.5МБ. Не сильно

Самые популярные слова в двух терабайтах кода

Наверное, мне стоило уточнить, что только в десятеричной системе числа игнорируются.

Если на гитхабе поискать 0x00 extension:lua то можно найти примеры

Самые популярные слова в двух терабайтах кода

Добавлю Эрланг в скором времени и отпишусь тут :)!

Информация

В рейтинге
6,081-й
Откуда
Seattle, Washington, США
Дата рождения
Зарегистрирован
Активность