Алгоритм поиска двух точек, наиболее удаленных друг от друга

https://stackoverflow.com/questions/477591

20-08-2019
|

Вопрос

Я ищу алгоритм для использования в гоночной игре, которую я создаю.Карта / уровень / трасса генерируются случайным образом, поэтому мне нужно найти два местоположения, start и goal, в которых используется большая часть карты.

Алгоритм предназначен для работы внутри двумерного пространства
Из каждой точки можно перейти к следующей точке только в четырех направлениях;вверх, вниз, влево, вправо
Точки могут быть только заблокированными или неблокируемыми, только неблокируемые точки могут быть пройдены

Что касается расчета расстояния, то это не должно быть "траекторией птицы" из-за отсутствия лучшего слова.Путь между A и B должен быть длиннее, если между ними есть стена (или другая блокирующая зона).

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

Редактировать: Правильно.После просмотра через код gs's Я попробовал еще раз.Вместо python я на этот раз написал его на C ++.Но все же, даже после прочтения Алгоритм Дейкстраса, тот заполнение потоком и Решение Хосама Алиса, Я не могу заметить какой-либо существенной разницы.Мой код все еще работает, но не так быстро, как вы, кажется, запускаете свой.Полный исходный код включен пирожок.Единственные интересные строки (я думаю) - это сам вариант Дейкстры в строках 78-118.

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

В алгоритме Хосама Алиса единственное отличие в том, что он сканирует с границ, а не с каждого узла?
В Dijkstras вы отслеживаете и перезаписываете пройденное расстояние, но не в floodfill, но это все?

Решение

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

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

Я предполагаю, что это было бы в O(n^2).Если я не ошибаюсь, это (L+W) * 2 * (L*W) * 4, где L является длиной и W это ширина карты, (L+W) * 2 представляет количество пограничных точек по периметру, (L*W) - это количество баллов, и 4 предполагается, что flood-fill будет обращаться к точке максимум 4 раза (со всех направлений).С тех пор как n эквивалентно количеству баллов, это эквивалентно (L + W) * 8 * n, что должно быть лучше , чем O(n²).(Если карта квадратная, порядок будет следующим O(16n^1.5).)

Обновить: согласно комментариям, поскольку карта больше похожа на лабиринт (чем на карту с простыми препятствиями, как я думал изначально), вы могли бы использовать ту же логику, что и выше, но проверять все точки на карте (в отличие от точек только на границе).Это должно быть в порядке O(4n²), что все еще лучше, чем у F-W и Дейкстры.

Примечание: Заполнение потоком больше подходит для этой задачи, так как все вершины напрямую соединены только через 4 границы.Обход карты в ширину может дать результаты относительно быстро (всего за O(n)).Я предполагаю, что каждая точка может быть проверена при заливке потоком от каждого из ее 4 соседей, таким образом, коэффициент в приведенных выше формулах.

Обновление 2: Я благодарен за все положительные отзывы, которые я получил относительно этого алгоритма.Особая благодарность @Georg за его отзыв.

P.S.Любые комментарии или исправления приветствуются.

Другие советы

Продолжение вопроса о Флойде-Уоршалле или простом алгоритме Хосам Али:

Я создал тестовую программу, которая может использовать оба метода.Это те самые файлы:

Во всех тестовых случаях Floyd-Warshall был на значительную величину медленнее, вероятно, это из-за очень ограниченного количества ребер, которые помогают этому алгоритму достичь этого.

Это были времена, когда поле каждый раз увеличивалось вчетверо и 3 из 10 полей были препятствием.

Size         Hosam Aly      Floyd-Warshall
(10x10)      0m0.002s       0m0.007s     
(20x20)      0m0.009s       0m0.307s
(40x40)      0m0.166s       0m22.052s
(80x80)      0m2.753s       -
(160x160)    0m48.028s      -

Время Хосама Али кажется квадратичным, поэтому я бы рекомендовал использовать этот алгоритм.Кроме того, потребление памяти Флойдом-Варшаллом составляет n², явно больше, чем необходимо.Если у вас есть какие-либо идеи, почему Floyd-Warshall работает так медленно, пожалуйста, оставьте комментарий или отредактируйте этот пост.

PS:Я давно не писал C или C ++, надеюсь, я не допустил слишком много ошибок.

Я удалил свой первоначальный пост, рекомендующий алгоритм Флойда-Варшалла.:(

gs провела реалистичный бенчмарк и угадайте, что, F-W работает существенно медленнее, чем алгоритм "заливки флудом" Хосама Али для типичных размеров карты!Таким образом, несмотря на то, что F-W - классный алгоритм и намного быстрее, чем алгоритм Дейкстры для плотных графов, я больше не могу рекомендовать его для задачи OP, которая включает в себя очень разреженные графы (каждая вершина имеет только 4 ребра).

Для протокола:

Эффективная реализация Алгоритм Дейкстры занимает O (Elog V) времени для графа с E ребрами и V вершинами.
"Заливка потоком" Хосама Али - это поиск по ширине сначала, который равен O(V).Это можно рассматривать как частный случай алгоритма Дейкстры, в котором оценка расстояния ни одной вершины не может быть пересмотрена.
В Алгоритм Флойда-Уорсхолла занимает O (V ^ 3) времени, очень прост в кодировании и по-прежнему является самым быстрым для плотных графов (тех графов, где вершины обычно соединены со многими другими вершинами).Но это неправильный выбор для задачи OP, которая включает в себя очень разреженные графики.

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

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

Раймунд Зайдель дает простой метод, использующий матричное умножение для вычисления матрицы расстояний для всех пар на невзвешенном неориентированном графике (это именно то, что вы хотите) в первом разделе своей статьи О задаче о всех парах кратчайших путей в невзвешенных неориентированных графах [pdf].

Входными данными является матрица смежности, а выходными данными - матрица расстояний по кратчайшему пути для всех пар.Время выполнения равно O (M(n)*log (n)) для n точек, где M (n) - время выполнения вашего алгоритма умножения матриц.

В документе также приводится метод вычисления фактических путей (в то же время выполнения), если вам это тоже нужно.

Алгоритм Зайделя классный, потому что время выполнения не зависит от количества ребер, но на самом деле нам здесь все равно, потому что наш график разрежен.Однако это все еще может быть хорошим выбором (несмотря на время выполнения, которое немного хуже, чем n ^ 2), если вам нужна матрица расстояний для всех пар, и это также может быть проще реализовать и отлаживать, чем заполнение лабиринта.

Вот псевдокод:

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

Чтобы получить пару точек с наибольшим расстоянием, мы просто возвращаем argmax_ij(d_ij)

Закончил python-макет дейкстровского решения проблемы.Код получился немного длинным, поэтому я разместил его в другом месте: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

При том размере, который я установил, выполнение алгоритма для одного узла занимает около 1,5 секунд.Запуск его для каждого узла занимает несколько минут.

Похоже, это не работает, хотя, он всегда отображает верхний левый и нижний правый угол как самый длинный путь;58 плиток.Что, конечно, верно, когда у вас нет препятствий.Но даже добавив пару случайно расположенных элементов, программа все равно найдет тот, который самый длинный.Возможно, это все еще верно, но его трудно проверить без более продвинутых форм.

Но, может быть, это, по крайней мере, покажет мои амбиции.

Хорошо, "алгоритм Хосама" - это поиск в ширину с предварительным выбором по узлам.Алгоритм Дейкстры ЗДЕСЬ применяться НЕ должен, потому что ваши ребра не имеют весов.

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

Таким образом, в основном разница в том, что Dijkstra должен "вернуться назад" и посмотреть на края, которые он исследовал ранее, чтобы убедиться, что он следует кратчайшему маршруту, в то время как поиск в ширину всегда знает, что он следует кратчайшему маршруту.

Кроме того, в лабиринте точки на внешней границе не гарантированно будут частью самого длинного маршрута.Например, если у вас есть лабиринт в форме гигантской спирали, но с внешним концом, возвращающимся к середине, у вас может быть две точки, одна в центре спирали, а другая в конце спирали, обе в середине!

Итак, хороший способ сделать это - использовать поиск в ширину из каждой точки, но удалить начальную точку после поиска (вы уже знаете все маршруты к ней и из нее).Сложность ширины первой равна O (n), где n = |V|+|E|.Мы делаем это один раз для каждого узла в V, чтобы он стал O (n ^ 2).

Ваше описание звучит для меня как маршрутизация в лабиринте проблема.Ознакомьтесь с Алгоритм Ли.Книги о проблемах размещения и маршрута при проектировании СБИС могут помочь вам - Шервани "Алгоритмы для автоматизации физического проектирования СБИС" это хорошо, и вы можете найти Автоматизация физического проектирования СБИС от Sait и Youssef полезный (и более дешевый в своей версии Google ...)

Если ваши объекты (точки) перемещаются нечасто, вы можете выполнить такое вычисление за гораздо меньшее время, чем O (n ^ 3).

Все, что вам нужно, это разбить пространство на большие сетки и предварительно рассчитать расстояние между сетками.Затем выбор пар точек, которые занимают наиболее удаленные сетки, является вопросом простого поиска в таблице.В среднем случае вам нужно будет попарно проверить только небольшой набор объектов.

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow