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

Ответ 1

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

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 - это предположение, что заливка наводнений будет достигать точки максимум в 4 раза (со всех сторон). Так как n эквивалентно числу точек, это эквивалентно (L + W) * 8 * n, которое должно быть лучше, чем O(n ²). (Если карта квадратная, порядок будет O(16n ^1,5).)

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

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

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

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

Ответ 2

Следуйте за вопросом о Floyd-Warshall или простом алгоритме Hosam Aly:

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

• создатель лабиринта
• найти самое длинное расстояние

Во всех тестовых случаях 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      -

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

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

Ответ 3

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

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

Для записи:

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

Ответ 4

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

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

Ответ 5

Раймунд Сайдель дает простой метод с использованием матричного умножения для вычисления матрицы пар всех пар на невзвешенном, ненаправленном графике (именно это вы хотите) в первом разделе своей статьи В проблеме "Все пар-кратчайший путь" в невзвешенных непрямых графах  [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)

Ответ 6

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

В заданном размере требуется около 1,5 секунд для запуска алгоритма для одного node. Запуск его для каждого node занимает несколько минут.

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

Но, возможно, это может показаться хотя бы моей амбицией.

Ответ 7

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

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

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

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

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

Ответ 8

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

Ответ 9

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

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

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