6.5

[me-04]

Ich würde hier den Algorithmus von Kruskal vorschlagen. Das Ganze ist doch ein MST, mit der Abänderung, dass die Summe der Gewichte maximal statt minimal sein sollte.

Pseudocode ist gleich wie Algorithmus 43 aus dem Skriptum, nur mit einer veränderten Zeile 2:
Sortiere Kanten: w(e1) >= w(e2) >= ... >= w(em);

Somit wird iterativ immer die Kante mit dem grössten Gewicht hinzugenommen.

[maitscha]

post gelöscht

[matrix-sisters]

Dh Kruskal wird nur in 2. Zeile geändert (sortiert Gewichte der Kanten absteigend statt aufsteigend), Hinzunahme der nächst kleineren Kante nur, wenn sich kein Kreis ergibt.

Das ergibt dann einen MaxST = {77,55,54,36,29,28,26,25,24,23,23,22,14,12,11,9} = 468

Bezüglich Laufzeit kann man sagen?

"Normaler Kruskal (Aufruf von DFS)" -> O(|V||E|)
Kruskal + Union Find -> O(|E| log |E|)

Oder?

[GALLA]

Braucht man hier nicht die Spanning-Tree Heuristik verwenden? Sonst ich würde auch gerne Kruskal nehmen.

mfg

[ChristofNeutron]

Braucht man hier nicht die Spanning-Tree Heuristik verwenden? Sonst ich würde auch gerne Kruskal nehmen.

mfg

aber die ST Heuristik ist doch nicht kreisfrei, oder?

[Havoc]

ein baum muss doch immer kreisfrei sein oder!!!!????
also muss doch die spanning tree heuristik auch kreisfrei sein oder hab ich da was falsch
verstanden!!!

find dass der kruskal ansatz gar net schlecht ausschaut!!!

[_logonoff_]

mit der spanning tree heuristik löst man das tsp, ergebnis ist ein eulerkreis, der natürlich _nicht_ kreisfrei ist...

bin auch für kruskal, obwohl mir das doch fast etwas zu einfach erscheint... :-)

[Merlin]

natürlich sollen wir hier die Spanning Tree Heuristik verwenden.
Im Skriptum geht es da um den genau umgekehrten Zweck, möglichst minimale Gewichte auf den Kanten zu haben.
Das muss man dann umändern.
Im 1.Schritt wird ein Minimal Spanning Tree gemacht aus |V| .
Das kann ich mit Kruskal, Prim oder wie auch immer machen.

Anschliessend verdopple ich alle Kanten und gebe ihnen Orientierung.
Den Rest kann man dann am besten mit einer Tiefensuche implementieren...

Muss dass noch genauer konzeptionieren, aber so glaub ich muss man das ganze machen...

[Merlin]

Also, ich hab mir das mal so überlegt. Keine Ahnung ob das der absolute Blödsinn schlechthin ist, aber so hab ich mir das mal vorgestellt:

Schritt 1 und 2 wie auf Seite 150

Bei Schritt 3 verändere ich jetzt die Tiefensuche:
DFS(v) {

markiert[v] == 0;

sortiere kanten(v,w) nach Gewicht für alle w aus N(v)

für alle Kanten e(v,w) {
falls markiert[w] == 0 dann DFS(w)
}

Wenn alle Knoten markiert, verbinde Endknoten mit Startknoten.

dann weiter wie im Buch.

Dadurch das ich die Kanten nach ihrem Gewicht sortiere, wird dann immer die schwerste zuerst ausgewählt, dann rekursiv in die Tiefe weiterverfolgt bis alle Knoten erreicht worden sind.

Eine andere Möglichkeit, die mir jetzt auch noch eingefallen ist:
Vielleicht sollte man nicht Punkt 3 ändern, sondern Punkt 5.

Normal würde ich in Schritt 5 immer von p nach q(unmarkierter Knoten) laufen und diesen dann markieren. Also wird zufällig ein Knoten gewählt, der noch nicht markiert ist. Ich könnte aber einfach schauen, welcher Knoten dann eine Kante mit maximalem Gewicht gibt. Ich glaube dass würde aber nicht viel bringen. Es geht ja darum, dass zufällig gewählt werden soll, oder? Damit ich einem lokalen Optimum entkomme.
Oder hab ich das falsch verstanden?

Dann wäre noch eine Idee: Ich könnte statt eines Minmal aufspannenden Baumes einen maximal aufspanenden Baum aufstellen.

Hmm...die erste Idee hat mir am besten gefallen auf jedenfall.

Vielleicht kann jemand von euch seinen Senf dazugeben was er davon hält?
Wär super, hab in 2 Stunden Übung ;)

[b_evil]

hm, ich kann echt nichts finden, was gegen kruskal spricht (außer das gefühl im bauch, das mir sagt, das is zu einfach)

[Merlin]

also würdest du NUR Schritt 1 machen?

Wozu haben wir dann überhaupt diese Spanning-Tree Heuristik dann gemacht???


hm, ich kann echt nichts finden, was gegen kruskal spricht (außer das gefühl im bauch, das mir sagt, das is zu einfach)

[_logonoff_]

nocheinmal:
die spanning-tree-heuristik heißt bloß so, weil sie von einem spanning-tree ausgeht! sie dient dazu das tsp zu lösen!