Интересные ссылки и их обсуждение

[nerv_]

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

[рони]

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

[nerv_]

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

[рони]

nerv_,

[destus]

nerv_,

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

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

[nerv_]

destus,

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

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

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

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

An almost universal implementation of A* search algorithm in JavaScript.

[destus]

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

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

[cyber]

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

4) что касается тестов, то я их на коленке мастерил =)

У нас для алгоритмов была песочница и показывало только что прошло тесты или нет и когда не мог найти ошибку у себя, то брал готовые популярные реализации алгоритмов и заганял рандомные данные в свою реализацию и в те что я взял и автоматически проверял результат и так до песконечности пока не нахоидл разницу в результате. Это я к чему, можно сделать такие тесты что бы проверить твой реализацию)

[nerv_]

В любом случае спасибо за найденный алгоритм

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

чего матрица? почему не граф?

1) матрица может задавать граф
2)

работа алгоритма не завязана на именно такое представление данных

см. этот и этот посты

[cyber]

1) матрица может задавать граф

Знаю)