Алгоритм кратчайшего пути (например, Дейкстры) для 500+ путевых точек/узлов?

Я спросил об алгоритме кратчайшего пути здесь: targetloca">Поиск пути в 2D: комбинации точек маршрута для перехода от curLocation к targetLocation

(Чтобы понять мою ситуацию, прочитайте этот вопрос, а также этот.)

Похоже, что алгоритм кратчайшего пути Дейкстры сможет сделать то, что мне нужно. Однако у меня на карте маршрутов от 500 до 1000 узлов.

Реализации, которые я видел до сих пор, ограничивали количество узлов чем-то меньшим, чем 50. Мой вопрос: должен ли я по-прежнему использовать алгоритм кратчайшего пути Дейкстры или его альтернативу? Существуют ли какие-либо реализации на Java?


java artificial-intelligence path-finding dijkstra graph-algorithm
person Tom    schedule 08.03.2011    source источник
comment
Правильно ли я понимаю, что вы хотите получить все пути от x до y, упорядоченные по длине, а не только самый короткий?   -  person Fred Foo    schedule 08.03.2011
comment
@larsman это то, что я хотел изначально, но, похоже, слишком много вопросов - только самый короткий вариант кажется подходящим, поскольку я могу повторить процесс без ранее возвращенных узлов.   -  person Tom    schedule 08.03.2011
comment
Простое расширение A* можно использовать для возврата по всем путям: stackoverflow.com/questions/5204444/ (хотя расширение может быть нетривиальным в Java). Однако это не работает с Dijkstra/graph A*.   -  person Fred Foo    schedule 08.03.2011

Ответы (3)


arrow_upward
5
arrow_downward

Вы не узнаете, пока не попробуете.

1000 узлов на самом деле не так уж и много. Алгоритм Дейкстры имеет линейную сложность по количеству ребер, а количество ребер в худшем случае квадратично по количеству узлов. Из вашего описания графа трудно сказать, сколько ребер в нем, но даже полный 1 000 000 не очень велик.

Основная проблема заключается в том, чтобы вы реализовали его правильно, используя приоритет очередь.

Правка: Russell & Norvig, 2-е изд., описание набора общих Алгоритмы поиска в главах 3 и 4. То, что они называют поиском по графу равномерной стоимости, по существу является алгоритмом Дейкстры. Если вы будете следовать их инструкциям, вы можете довольно легко расширить алгоритм до поиска A*, если возникнет такая необходимость.

person Fred Foo    schedule 08.03.2011
comment
Хотел бы я попробовать это с проверенной библиотекой Java. Вы случайно не знаете о каких-либо подобных реализациях алгоритма Дейкстры или A* в Java? Тот, который я нашел, имел жестко заданное ограничение в 26 узлов, и это было просто доказательство концепции. - person Tom; 08.03.2011
comment
Не тестировалось: попробуйте пример кода Java для Russell & Norvig, code.google.com/p/aima-java. Вы ищете поиск по графику единой стоимости (см. мой обновленный пост). - person Fred Foo; 09.03.2011
comment
@larsmans, я так понимаю, существующей библиотеки нет? Я мог бы показаться ленивым, потому что не попытался сразу же создать свою собственную реализацию, но учитывая, что 1) этот поиск пути - лишь незначительная часть моего проекта и 2) у меня вообще нет опыта/знаний в этой области --- я считаю, что я действительно следует использовать уже проверенную библиотеку - person Tom; 09.03.2011
comment
@Tom: Библиотека Юнга (jung.sf.net) включает алгоритм Дейкстры, но я думал, что вы этого не сделали. хочу полноценный фреймворк. Вы вряд ли найдете гораздо меньшую библиотеку, поскольку представления графов сильно различаются. - person Fred Foo; 09.03.2011
comment
@larsmans, я пытаюсь использовать библиотеку jung, но не могу найти реализацию карты дерева, предназначенную для плотных графов (все они утверждают, что подходят только для разреженных графов), см. jung.sourceforge. net/doc/api/edu/uci/ics/jung/graph/class-use/ — есть идеи почему? - person Tom; 09.03.2011
comment
@Tom: это материал для нового вопроса. Сам я не использую Юнга широко. - person Fred Foo; 09.03.2011

arrow_upward
2
arrow_downward

Поиск кратчайшего пути в метрическом 2D-мире является хрестоматийным примером алгоритма A*. Вашей эвристической функцией должно быть расстояние по прямой линии от каждой путевой точки до вашей цели.

person biziclop    schedule 08.03.2011
comment
Применяется ли алгоритм A* для такого количества путевых точек в отличие от алгоритма Дейкстры? - person Tom; 08.03.2011
comment
@Tom A * в основном представляет собой улучшенный вариант Дейкстры, где следующий кандидат выбирается с использованием эвристики расстояния (в вашем случае, прямого расстояния между двумя путевыми точками), а не в произвольном порядке. Так что да, он предназначен для использования в тех случаях, когда алгоритм Дейкстры слишком медленный. - person biziclop; 08.03.2011
comment
это не отвечает, применимо ли оно к ситуации с 500-1000 узлами или подходит ли Дейкстра. - person Tom; 08.03.2011
comment
@Tom Применимость зависит от того, какое время работы приемлемо для вас и насколько хороша ваша реализация. Я ничего не знаю об этом, поэтому я не могу дать вам определенный ответ да/нет. Все, что я могу сказать, это то, что A * намного быстрее, чем Дейкстра, если вы можете найти подходящую (допустимую) эвристику, а в вашем случае такая эвристика существует. - person biziclop; 08.03.2011
comment
Я предполагаю, что расчет кратчайшего пути от node1 к node2 должен быть рассчитан в течение 100 миллисекунд, когда есть 1000 узлов, каждый из которых имеет прямое соединение в среднем с чем-то около 5 узлов (если это имеет значение). - person Tom; 08.03.2011

arrow_upward
0
arrow_downward

Алгоритм dijkestra не является примитивным или kruskal, он вычисляет mst целиком, когда последний использует только ребро. какой еще алгоритм вы имеете в виду?

person Gigamegs    schedule 08.03.2011
comment
Я ничего не имею в виду. У меня совсем нет опыта в этой области, что объясняет мои вопросы. Я ищу уже реализованный алгоритм на Java, который может найти кратчайший путь в 2D-мире с более чем 500 узлами. - person Tom; 08.03.2011
comment
Stackoverflow .com/questions/2733051/ - person Gigamegs; 08.03.2011
comment
stackoverflow.com/questions/3818079/ - person Gigamegs; 08.03.2011