Алгоритм соединения всех точек с минимальным общим расстоянием

Question

У меня есть набор точек и функция расстояния, применимая к каждой паре точек.Я хотел бы соединить ВСЕ точки вместе с минимальным общим расстоянием.Знаете ли вы о существующем алгоритме, который я мог бы использовать для этого?

Каждая точка может быть связана с несколькими точками, так что это не обычная проблема «маршрута продавца»1005 *

Answer 1

То, что вам нужно, это Минимальное связующее дерево .

Два наиболее распространенных алгоритма для генерации одного:

• Алгоритм Прима
• алгоритм Крускала

Answer 2

Как уже говорили другие, минимальное остовное дерево (MST) позволит вам сформировать подграф минимального расстояния, который соединит все ваши точки.

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

Существуют эффективные алгоритмы для обоих MST (Фазы Прим / Крускала O(E*log(V))) и Триангуляции Делоне (Разделяй и властвуй O(V*log(V))), поэтому возможны эффективные общие подходы.

Надеюсь, это поможет.

Answer 3

Алгоритм, который вы ищете, называется минимальным остовным деревом.Полезно найти минимальную стоимость для воды, телефона или электросети.Есть алгоритм Прима или алгоритм Крускала.Алгоритм IMO Prim немного проще понять.

Answer 4

Взгляните на алгоритм Дейкстры:

Алгоритм Дейкстры, разработанный голландским ученым-программистом Эдсгером Дейкстрой в 1956 году и опубликованный в 1959 году, представляет собой алгоритм поиска графа, который решает проблему кратчайшего пути из одного источника дляграф с неотрицательными путями стоимости пути, производя дерево кратчайшего пути.Этот алгоритм часто используется в маршрутизации и в качестве подпрограммы в других алгоритмах графа.

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Answer 5

здесь http://en.wikipedia.org/wiki/Minimum_spanning_tree вы можете найти больше информации о минимальном остовном дереве, чтобы вы могли адаптировать его для решения вашей проблемы.