На досуге реализовал astar-algorithm алгоритм.
Найдете баги, пишите :)

nerv_,
а что это astar-algorithm?

рони, информированный алгоритм поиска пути по первому наилучшему совпадению на графе.

nerv_,
:thanks:

nerv_,

it('should work', function () { })

:). Вообще, на мой взгляд, способ задания графа неудобный. Слишком много информации нужно подготовить. Если рассматривать эту задачу как поиск проезда от остановки А к остановке Б в городе с количеством остановок ~ 200, то такой вариант задания входных параметров просто неприемлим. А ведь все можно решить простым заданием матрицы весов, start, end.

destus,

1) в прошлом году я реализовывал агоритм дейкстры, где на вход подается матрица смежности. В паблике его нет :)

2) чем плох способ с матрицей? Тем, что он требует задания сразу всей матрицы. (хотя для дейксты это как раз то, что нужнно)

3) моя реализация astar-algorithm'а, как ты мог заметить, основана на коллбеках: достаточно задать начальную, конечную точки, определить коллбеки, в том числе "порождающий" коллбек getSuccessors и дело в шляпе.

4) что касается тестов, то я их на коленке мастерил =) Иными словами: работа алгоритма не завязана на именно такое представление данных.

nerv_,
В любом случае спасибо за найденный алгоритм :) . В институте данный алгоритм мы не рассматривали. Реализовывали различные алгоритмы дискретной математики: Дейкстры, Флойда, транспортная задача, различные поиски на графе в глубину / ширину, но точно не A*.

В своем проекте мы используем как раз таки алгоритм Дейкстры, для поиска вариантов проезда из одной точки в другую. Если вкратце, то есть целый регион РФ, со своей автомобильной / жд / воздушной / водной развязками, и у пользователя через карту есть возможность найти варианты проезда из точки А в точку Б.

nerv_, чего матрица? почему не граф?
Эх вспомнил как страдал на плюсах в универе с разными алгоритмами, не помню почему но дейкстра на графе доставил мне большего всего боли)
Даже что-то тут на форуме спаршивал https://javascript.ru/forum/offtopic...ena-monet.html)
У нас для алгоритмов была песочница и показывало только что прошло тесты или нет и когда не мог найти ошибку у себя, то брал готовые популярные реализации алгоритмов и заганял рандомные данные в свою реализацию и в те что я взял и автоматически проверял результат и так до песконечности пока не нахоидл разницу в результате. Это я к чему, можно сделать такие тесты что бы проверить твой реализацию)

эм... даже не знаю что сказать... он достаточно известен :) Это вершина айсберга под названием Artifical Intelligence
---
1) матрица может задавать граф
2) см. этот и этот посты

Знаю)