Ich habe ein array "Kanten : array of TKante", TKante ist dabei ein record von (Startknoten,Endknoten,Distanz). Dieses array enthält alle Kanten meines ungerichteten Graphen. Mit dem Algorithmus von Kruskal habe ich es geschafft ein neues array "MinSpannbaum : array of TKante" zu erstellen, welches nur die Kanten des minimalen Spannbaums enthält. In diesem Fall kann ein Knoten allerdings mehr als 2 Nachfolger/Vorgänger Knoten haben. Ich brauch nun allerdings einen Minimalen Spannbaum bei dem jeder Knoten nur 2 Nachfolger/Vorgänger hat.

Hat da vielleicht jemand ne Idee wie ich so einn Spannbaum erzeugen könnte?

Hab schon versucht einfach bei der Kante mit der kleinsten Distanz anzufangen und einfach immer die kürzeste Kante dranzuhängen, die selbst einen Knoten der vorigen Kante als Knoten hat. Dabei entstaht zwar ein Spannbaum mit maximal 2 Kanten bzw Nachfolgern an einem Knoten, allerdings ist der Spannbaum nicht der minimale Spannbaum mit maximal 2 Kanten bzw Nachfolgern an einem Knoten.

edit: bin übrigens in delphi unterwegs

Hallo!
Ich nehme an, es geht um TSP.

Das Problem beim dem algo ist, das es NICHT immer (manchmal kann es aber vorkommen) den kürzesten Weg liefert. Einen kurzen JA, aber nicht DEN kürzsesten. Wenn du wirklich den kürzesten Weg finden willst, musst du das mit BruteForce machen.

Kann sein, dass ich daneben liege, aber müsste hier nicht auch Dijkstra funktionieren?

AXMD

Ja genau, und mit Dijkstra findet man den wirklich kürzesten Pfad ohne Bruteforce!!! (@Dragonclaw, von wegen "muss man mit BruteForce machen" )
Allerdings ists nicht gerade einfach zu implementieren

Und wenn du auch negative Gewichte hast, dann geht Dijkstra nicht, weil Schleifen entstehen können. Dann musst du Bellman-Ford benutzen.

Aber abgesehen davon geht es ja um einen minimalen Spannbaum. Aber das mit

Zitat:

maximal 2 Kanten bzw Nachfolgern an einem Knoten

muss dort dann eben selbst noch in Kruskal reingebracht werden. Ich kann mir das heute Abend mal ansehen.

Ich denke Dijkstra ist auch eine Art "Brute-Force". Er macht im Endeffekt nichts anderes als eine Breitensuche auf einer Priority-Queue und merkt sich noch wo er schon war. Er versucht also auch alle Möglichkeiten durch, eben so lange bis die Queue leer ist..

Aber Kruskal ist auf jeden Fall schonmal der richtige Weg für einen MST (Minimum Spanning Tree).


MrSaint


P.S.: Wenn du den Dijkstra ohne "suchen" (="BruteForce") implementieren kannst, hättest du glaube ich P = NP gezeigt und du könntest wirklich reich werden

Auf den ersten Blick ein kniffliges Problem. Zuerst fällt mir da folgendes ein:

Ist denn überhaupt sichergestellt, dass es überhaupt einen binären Spannbaum gibt? D.h. ist der Graph dicht genug? (Mir fällt grade kein sinnvolles Kriterium ein, irgendwie denke ich da an einen nötigen Zusammenhang zwischen maximalen Knotengrad und Kantenzusammenhang, kann dabei aber auch vollkommen falsch liegen.)

Es könnte aber sein, dass minmimaler binärer Spannbaum NP-Vollständig ist. Muss ich mal was drüber nachdenken.

MrSaint hat folgendes geschrieben:

P.S.: Wenn du den Dijkstra ohne "suchen" (="BruteForce") implementieren kannst, hättest du glaube ich P = NP gezeigt und du könntest wirklich reich werden

Uahhhhh. Dijkstra ist ein ganz normaler Algorithmus, der deterministisch in polynomieller Zeit arbeitet. Mit NP hat das nur deswegen gaaaaanz am Rande was zu tun, weil jedes Problem in P (deterministisch polynomiell lösbar) selbstverständlich auch in NP (nichtdeterministisch polynomiell lösbar) liegt. Aber das ist eine Offensichtlichkeit, und trägt nichts zur Lösung von "P=NP oder P<>NP?" bei.

edit: Hab hier in einem Vorlesungstest was gefunden, welcher meine Vermutung bestätigt. Es ist ein kniffliges Problem . Du könntest aber evtl. Kruskal modifizieren (ob das auch für binäre und nicht nur für trinäre Bäume funktioniert, weiß ich nicht), um einen "zimlich minimalen" Binärbaum zu erstellen. Dazu müsste man beim Einfügen einer neuen Kante nur überprüfen, ob der Knotengrad noch stimmt.

Hier die Implementierung des Kruskal Algorithmus in meinem Programm, wäre schön wenn mir da jemand sagen könnte wie ich den für einen binären Baum verändern muss, versuche jetzt schon seit Montag das selber hinzubekommen, aber meine Lösungen haben entweder dazu geführt das einfach Kanten gefehlt haben und so einzelne Komponenten unverbunden blieben oder das doch wieder ein nicht binärerer Baum rauskam.

Ja, also ich hab mir das mal angesehen. Das Problem ist: Wie will man feststellen, ob ein Zielknoten anders gar nicht erreicht werden kann als durch die gerade wegen Binäreigenschaft abgelehnte Kante? Dann müsste man ja die Kante einschließen und stattdessen eine andere rausnehmen. Aber... Ich glaube dazu müsste ich doch die Graphentheorie noch besser können, um da eine Lösung zu finden.

Davon, dass es einen binären MST gibt, kannst du ausgehen? (Sonst würde es noch komplizierter )

Da ich einen ungerichteten Graphen habe bei dem eine Kante zwischen jedem Punktepaar besteht, muss es auf jeden Fall eine Kante geben die den Zielknoten erreict und dabei die Binäreigenschaft erfüllt, also gibt es immer einen binären MST, welcher jedoch höhere Kosten haben kann als der nicht binäre MST. Aber wie ich diesen binären MST finde, da bin ich ratlos.