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

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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