Comments 18
Ждём пулреквест, который научит алгоритм не бежать по встречке. Ну и остальные запреты учитывать. А там глядишь и скорость для эвристики подтянется.
Для этого уже нужен порт OSRM или Вальхаллы на WebAssembly
зачем?
Чтобы не превращать демонстрационное приложение в полноценный оттестированный роутер с развесистой логикой. И в случае если нужна навигация именно на github pages в javascript без хостинга бэка.
Так мы не делаем полноценный, мы делаем демонстрационный и понятный. Нам не нужна не упаковка данных с быстрым доступом, ни возможности накатывать обновления, пробки нам так же не нужны и все остальные навороты и оптимизации.
Тогда я не отговариваю всех вас делать пул реквесты в honzaap/pathfinding, реализуя на JavaScript логику движка маршрутизации с желаемым функционалом.
А если отправить алгоритм от Калининграда до Петропавловска-Камчатского пешком?
на скриншоте скорее всего какой-то транспортный маршрут.....через монголию....южную корею да еще и морским путем....в том то и загвоздка что дороги, пусть даже и грунтовки есть, только они присутствуют на разных картах и как будто не пересекаются...но если их наложить на один слой и построить сухопутный маршрут.....- сможет ли алгоритм это обработать?
Месье знает толк в извращениях? Если вам нужен такой маршрут, с теми ограничениями что вы назвали, рекомендую вам изучить документацию GraphHopper и описать требуемый профайл для навигации.
через монголию....южную корею да еще и морским путем
Такие маршруты могут влючать паромные переправы по умолчанию и пересечения границ, в этом скриншоте это: RUS - LTU - LVA - RUS - LVA - RUS - MNG - CHN - KOR - RUS
Алгоритм - это программа, может обработать только те данные что доступны ему на входе. У него нет машинного зрения, возможности просить картографов сделать их работу и прочего. Вводите нужные данные из реальности в входном формате - получаете результат с кратчайшим путем.
Двунаправленный поиск нашел не самый оптимальный маршрут, но обошел меньше улиц чем алгоритм Дейкстры:
Такого быть не должно, если алгоритм написан правильно.
Поиск от финиша проводится на обращённом графе.
Судя по работе honzaap/pathfinding на данном маршруте, он останавливается на первом пересечении двух подграфов.
Если метод сделан достаточно аккуратно - то первое пересечение и есть оптимальный маршрут (эквилалентный тому, что ищет однонаправленный поиск).
Вероятно по каким-то техническим причинам - двунаправленный поиск сделан недостаточно аккуратно.
Нет это не так. В данном случае получаются найдены минимумы по отдельности для каждого направления, а не общий минимум.
Примерно как треугольник со сторонами 3, 4, 5. По отдельности мы нашли минимумы 3 и 4, и они оба меньше 5. Но в сумме дают 7, а общий минимум 5.
Примерно ... треугольник...
Не знаю что вы имели в виду под "примерно" и "треугольник" (возможно готовы это объяснить строго)?
Вообще же двунаправленный поиск работает так:
Доказывается просто:
Пусть кратчайший путь существует и дискретизируется на нашей карте за T0 = (t0 +dt0) + (t0 - dt0) (лучшее разделение этого пути пополам по времени, в терминах дискретных переходов по нашему графу), то мы его найдём в момент времени t+dt.
(если бы делилось пополам строго (как в упрощённой реализации на уроках в школе) - то мы бы нашли его в момент времени T0/2).
*) чисто гипотетически возможны всякие эффекты дискретизации формулы выше, когда: (T1 > T0) && (t1 + dt1 < t0 + dt0) - тогда найдётся путь T1.
Но на практике слишком длинных прямых "выехал на шоссе и едешь пол-часа" стараются избегать просто их разбиением. А в рамках города - наличие таковых вдвойне странно.
Т.е. эффект: "разница в минуту" быть вполне может.
А вот значимой разницы в ответах, тем более в городе, быть не должно.
Онлайн визуализация алгоритмов: жадного, Дейкстры, A* и двунаправленного поиска