Алгоритм для нахождения двух точек дальше всего далеко друг от друга

Следуют до вопроса о 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      -

время Hosam Aly, кажется, квадратично, поэтому я рекомендовал бы использовать тот алгоритм. Также потребление памяти Floyd-Warshall является n <глоток> 2 , ясно более, чем необходимый. Если у Вас есть какая-либо идея, почему Floyd-Warshall является настолько медленным, оставьте комментарий или отредактируйте это сообщение.

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

я удалил свое исходное сообщение, рекомендующее алгоритм Floyd-Warshall. :(

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

Для записи:

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

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

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

Raimund Seidel дает простой метод с помощью умножения матриц для вычислений матрицы расстояния все-пар на невзвешенном, неориентированном графе (который является точно, что Вы хотите) в первом разделе его статьи На All-Pairs-Shortest-Path проблеме в Невзвешенных Неориентированных графах [PDF] .

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

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

алгоритм Seidel прохладен, потому что время выполнения независимо от количества краев, но мы на самом деле не заботимся здесь, потому что наш график редок. Однако это может все еще быть хорошим выбором (несмотря на slightly-worse-than n^2 время выполнения), если Вы хотите всю матрицу расстояния пар, и это могло бы также быть легче реализовать и отладить, чем floodfill на лабиринте.

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

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 dijkstra решения проблемы. Код стал немного длинным, таким образом, я отправил его где-то в другом месте: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

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

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

, Но возможно это может, по крайней мере, показать мое стремление.

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

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

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

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

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

Ваше описание звучит мне как лабиринт, направляющий проблема. Проверьте Алгоритм Lee . Книги о проблемах места-и-маршрута в дизайне СБИС могут помочь Вам - "Алгоритмы Sherwani для СБИС, Физическая Автоматизация проектирования" хороша, и можно найти СБИС Физическая Автоматизация проектирования Сайтом и Youssef полезный (и более дешевый в его версии Google...)

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

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

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