Найти кратчайший набор путей, соединяющих все узлы

Question

У меня есть набор точек в 2D координатном пространстве.

Я хотел бы найти набор путей, которые соединяют их все с наименьшей общей длиной. (heuristi c решение в порядке, не обязательно быть точным.)

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

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

Answer 1

Проблема, которую вы описываете, звучит как алгоритм Крускала:

Алгоритм Крускала - это алгоритм минимального связующего дерева, который находит ребро с наименьшим возможным весом, который соединяет любые два дерева в лесу. Это жадный алгоритм в теории графов, поскольку он находит минимальное остовное дерево для связанного взвешенного графа, добавляя дуги увеличивающейся стоимости на каждом шаге. Это означает, что он находит подмножество ребер, которые образуют дерево, которое включает в себя каждую вершину, где общий вес всех ребер в дереве минимизируется. Если график не связан, то он находит минимальный остовный лес (минимальное остовное дерево для каждого подключенного компонента).

Крускал Наихудший случай сложности времени O (E log E), потому что нам нужно отсортировать ребра. Наихудший случай сложности начального времени - O (E log V) с приоритетной очередью или даже лучше, O (E + V log V) с кучей Фибоначчи. Вы должны использовать Kruskal, когда график разрежен, например, небольшое количество ребер, например E = O (V), когда ребра уже отсортированы или если мы можем отсортировать их за линейное время. Мы должны использовать Prim, когда граф плотный, т.е. число ребер велико, например, E = O (V²)

Answer 2

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

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

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

Если вы хотите, я могу (попытаться) доказать алгоритм, который я только что предложил.

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

Answer 3

Если я правильно понимаю ваш вопрос, то вы ищете минимальное связующее дерево (часто сокращенно MST). MST - это просто подмножество путей, которые

• (a) соединяют все точки,
• (b) имеет наименьшую общую длину, возможную при этом, и
• (c) не имеет циклов.

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

---

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

1. Рассмотрим кратчайший путь в списке.
   • Если это создаст цикл в вашем MST, не добавляйте его в дерево (просто удалите его из списка).
   • В противном случае добавьте его в дерево (и удалите его из списка).

В итоге вы получите дерево, которое

• (a) соединяет все точки - гарантировано, так как рассматривается каждый путь, каждая вершина право на участие в MST должно быть на пути, и добавление пути для достижения ранее не связанной вершины не может создать цикл;
• (b) имеет наименьшую возможную общую длину - гарантируется, поскольку пути добавляются в порядке возрастания длины; и
• (c) не имеет циклов - гарантировано, потому что алгоритм явно избегает этого.

---

Примечания:

(1) При работе с MST (и другими проблемами с графами) мы часто называем детали по заданным c именам: набор точек «график», указанная c точка или узел - это «вершина», пути между вершинами являются «ребрами», а длины ребер - «весами».

(2) Алгоритм Крускала выполняется за время O (ElogV), где E - количество путей / ребер, а V - количество точек / вершин.

(3) Если у вашего графа есть какие-либо вершины или наборы вершин, которые отключены от остальной части набора данных, вы получите несколько MST в «лесу MST».

(4) График может иметь более одного MST; например, в на этом графике минимальная длина MST равна 6 - что достигается обоими из следующих MST: MST1 , MST2

(5) Определить, может ли добавление пути создать цикл, действительно сложно; Один из способов сделать это - использовать структуру данных UnionFind, с которой вы можете поиграть здесь .