Звездный поиск: много узлов и медленный CheckLink между узлами, есть предложения?

Столкнулся с проблемой оптимизации:

У меня есть график с большим количеством узлов (10 ^ 5), который представляет точки на плоской поверхности.

Мне нужно найти кратчайший путь на графе, чтобы добраться до «конечного узла», начиная с «начального узла».

любая пара узлов может быть соединена или нет. Проверка, связаны ли они, является очень затратной операцией. Если они соединены, вес, связанный со связью, равен евклидову расстоянию между двумя узлами.

На данный момент я только проверяю все ссылки с «текущего узла» на все остальные узлы, чтобы заполнить «открытый список» для A *. Я выбрал A*, потому что это кажется лучшим алгоритмом поиска пути, и у меня есть быстрая, допустимая и простая эвристика H для узла J (H = расстояние до цели), но я не уверен, что это хорошо для моей задачи.

Построение графа заранее неуправляемо, нужно проверить N ^ 2 ссылок, это слишком медленно. На данный момент (почти) весь граф строится только в том случае, если нет решения, нет пути от начала до конца.

Я хотел бы подсказку для лучшего решения ... спасибо!


search algorithm a-star
person ugasoft    schedule 20.03.2011    source источник
comment
Как реализован CheckLink? A* следует ожидать построения почти полного графа, когда решение не может быть найдено.   -  person Fred Foo    schedule 20.03.2011
comment
Алгоритм Брезенхема над сеткой, похожей на изображение   -  person ugasoft    schedule 21.03.2011

Ответы (2)


arrow_upward
2
arrow_downward

Это действительно две проблемы в одной. Я не знаком с алгоритмом Брезенхема, поэтому могу только предложить вам ознакомиться с оптимизацией, приведенной в Википедия и ссылки там.

Что касается A*: построение почти всего графа, как я уже говорил, почти неизбежно. Вы можете поэкспериментировать с такими вариантами, как рекурсивный поиск по первому наилучшему или IDA* (Russell & Norvig, глава 4 в 2-е изд.), чтобы сэкономить немного памяти и, возможно, некоторое время, если у вас медленная память..

В зависимости от структуры вашего графа может оказаться целесообразным реализовать двунаправленный поиск. Простейший алгоритм bidir будет выполнять поиск A* от A к B в одном потоке и от B к A в другом, пока один из них не найдет решение или не обнаружит, что он застрял. Затем можно убить другой поток. (Одна из проблем заключается в том, что если есть решение, вы тратите много времени впустую, поэтому оно полезно только в том случае, если у вас есть запасное ядро ​​процессора, которое в противном случае простаивало бы.)

Более сложный алгоритм также проверит, находят ли они одну и ту же точку на графике, а затем убьет потоки и объединит их результаты. Это может быть реализовано путем чередования шагов в двух поисках; параллельная версия может быть довольно сложной.

person Fred Foo    schedule 21.03.2011
comment
Я забыл начать с обоих концов. Это хорошее предложение. Распараллеливание также может быть полезным, если CheckLink не требует блокировки. - person Judge Maygarden; 21.03.2011

arrow_upward
1
arrow_downward

Если вы не можете иметь дело с жадным алгоритмом, который не гарантирует оптимального решения, то этот подход A *, вероятно, будет настолько хорош, насколько вы собираетесь его получить. Ни один алгоритм не может избежать проверки каждой вершины, если путь не существует без дополнительной информации, которая позволяет обрезать некоторые вершины. Возможно, работу CheckLink можно оптимизировать? Можно ли кэшировать информацию о ссылках в более быстром для доступа формате или данные, похожие на изображения, меняются при каждом запуске?

person Judge Maygarden    schedule 20.03.2011