Random-Spanning-Bäume von bipartite Graphen

Question

Ich arbeite daran, einige Code mit Metaheuristiken für die Suche nach guten Lösungen für die Fixed Charge Transportation Problem (FCTP).

Das Problem, das ich habe, ist eine Startlösung zu generieren, basierend auf dem Auffinden eines Spanning-Tree für die zugrunde liegende bipartite Grafik.

Ich möchte, dass es ein zufälliger spannender Baum ist, so dass ich die Prozedur für dasselbe Problem mehrere Male ausführen kann, möglicherweise unterschiedliche Lösungen zu erhalten.

Ich habe einige Schwierigkeiten dabei. Der Ansatz, den ich bisher gegangen bin, besteht darin, eine zufällige Permutation der Bögen zu machen, dann durch diese Liste zu iterieren und sie sequentiell in die Basis zu setzen, wenn sie keinen Zyklus erzeugen wird.

Ich muss eine schnelle Methode finden, um zu überprüfen, ob das Einfügen eines Bogens einen Zyklus erzeugt. Ich will es nicht "brutal forcen", da dieser Ansatz bei großen Problemfällen viel Zeit in Anspruch nehmen kann.

Vorausgesetzt, dass A ist ein Array mit einer zufälligen Permutation der Bögen, wie würden Sie gehen um eine Auswahlverfahren zu gehen?

Ich habe jetzt ein paar Stunden daran gearbeitet, und nichts, was ich versucht habe, hat gearbeitet, die meisten es unsinnig, wenn es um Anwendung kommt ...

Answer 1

Krusksalgorithmus wird verwendet, um den minimalen Spannbaum zu finden. Die Fast-Cycle-Erkennung ist nicht Teil des Kruskals-Algorithmus. Der Algorithmus wird mit einer Datenstruktur arbeiten, die in der Lage ist, sowohl Zyklen schnell als auch mit einem langsamen naiven Versuch zu finden (die Komplexität wird jedoch unterschiedlich sein).

Allerdings ist der Kruskals-Algorithmus hier auf dem richtigen Weg, da er normalerweise eine so genannte union-find- oder disjoint-set-Datenstruktur zur schnellen Erkennung von Zyklen verwendet. Dies ist der Teil der Seite Kruskals Algorithmus auf Wikipedia, den Sie für Ihren Algorithmus benötigen. Dies ist auch auf Wikipedia verlinkt: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Answer 2

fand ich Kruskal's algorithm nach langen Stunden der Forschung. Ich musste nur die Reihenfolge randomisieren, in der ich die Knoten des Graphen untersucht habe.