Цитата:
|
На досуге реализовал 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) Цитата:
|
Цитата:
--- Цитата:
2) Цитата:
|
Часовой пояс GMT +3, время: 11:49. |