Случайные остовные деревья двудольных графов
Я работаю над созданием кода с использованием метаэвристики для нахождения хороших решений проблемы транспортировки с фиксированной зарядкой (FCTP).
Проблема, которую я имею, состоит в том, чтобы сгенерировать исходное решение, основанное на поиске связующего дерева для основного двудольного графа.
Я хочу, чтобы это было случайное связующее дерево, чтобы я мог запускать процедуру для одной и той же проблемы несколько раз, возможно, получая разные решения.
У меня есть некоторые трудности с этим. Подход, который я использовал до сих пор, состоит в том, чтобы сделать случайную перестановку дуг, а затем перебрать этот список, последовательно помещая их в основу, если это не создаст цикл.
Мне нужно найти быстрый метод, чтобы проверить, создаст ли дуга цикл. Я не хочу "грубой силы", поскольку этот подход может занять много времени, учитывая большие проблемы.
При условии A такое массив со случайной перестановкой дуг, как бы вы делали процедуру выбора?
Я работаю над этим уже пару часов, и ничто из того, что я пробовал, не сработало, большая часть этого была бессмысленной, когда дело дошло до приложения...
2 ответа
Алгоритм Крускала используется для нахождения минимального остовного дерева. Обнаружение быстрого цикла на самом деле не является частью алгоритма Крускала. Алгоритм будет работать со структурой данных, которая способна находить циклы как быстро, так и с медленной наивной попыткой (однако сложность будет другой).
Однако алгоритм Kruskals здесь находится на правильном пути, так как он обычно использует так называемую структуру данных для поиска объединения или несвязанного набора для быстрого обнаружения циклов. Это часть страницы Алгоритма Крускала в Википедии, которая понадобится вам для вашего алгоритма. Это также связано в Википедии: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
Я нашел алгоритм Крускала после долгих часов исследований. Мне нужно было только рандомизировать порядок, в котором я исследовал узлы графа.