Является ли этот алгоритм минимального связующего дерева правильным?

Question

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

Алгоритм, который я рассматриваю:

• Найти все циклы.
• удалить наибольшее ребро из каждого цикла.

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

редактирует:

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

Answer 1

Не знаю, работает ли он, но независимо от того, , ваш алгоритм даже не стоит реализовывать . Обнаружение всех циклов будет чертовски огромным узким местом, которое убьет его. Также сделать это без итераций невозможно. Почему бы вам не реализовать какой-то стандартный алгоритм, скажем, Prim's .

Answer 2

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

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

Answer 3

@shrughes.blogspot.com:

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

Answer 4

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

Разработка:

В графе с n узлами и ребром между каждой парой узлов, если я правильно понимаю, есть n! / (2k (nk)!) Циклов размера k, если вы считаете цикл как некоторый подграф из k узлов и k ребер, причем каждый узел имеет степень 2.

Answer 5

Что произойдет, если два цикла перекрываются? У какого из них самый длинный край удален первым? Имеет ли значение, если самый длинный фронт каждого из них разделен между двумя циклами или нет?

Например:

V = { a, b, c, d }
E = { (a,b,1), (b,c,2), (c,a,4), (b,d,9), (d,a,3) }

Существует цикл a -> b -> c ->, а цикл a -> b -> d -> a

Answer 6

ОК, это попытка закончить доказательство правильности. По аналогии с алгоритмом обратного удаления мы знаем, что будет удалено достаточно ребер. Осталось показать, что не будет много удаленных краев.

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

Осталось показать, что это распространяется на> 2-х сторонние разделы.

Answer 7

@ Tynan Систему можно описать (несколько упрощенно) как систему правил, описывающих категоризацию. «Вещи находятся в категории A, если они находятся в B, но не в C», «Узлы, связанные с узлами в Z, также находятся в Z», «Каждая категория в M связана с узлом N и имеет« дочерние »категории, также в M для каждого узла, подключенного к N ". Это немного сложнее, чем это. (Я показал, что, создавая нестабильные правила, вы можете смоделировать токарный станок, но это не относится к делу.) Он не может явно определять итерацию или рекурсию, но может работать с рекурсивными данными с помощью правил, таких как 2-й и 3-й.

@ Marcin, предположим, что процессоров неограниченное количество. Нетрудно показать, что программа может быть запущена в O (n ^ 2), если n самый длинный цикл. С лучшими структурами данных это можно уменьшить до O (n * O (установить функцию поиска)), я могу представить аппаратное обеспечение (квантовые компьютеры?), Которое может оценивать все циклы в постоянное время. дать решение O (1) для проблемы MST.

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

HHMM ....