5.10

[buechsengustel]

wie bei 5.9 (http://hades.gothic.at/iforum/showthread.php?threadid=8856) sucht man erst einen MST.
dann macht man für alle knoten mit ungeradem grad (alle außer b) ein perfektes matching.

ich hab zwar eins gefunden, sehr algorithmisch war das aber nicht, das müsste man sich gesondert überlegen, wie man das kriegt.

eine möglichkeit ist: (a , d) , (c , g) , (e , f) mit gesamtgewicht 21

diese kanten zeichnet man sich zum MST dazu --> eulertour --> tour.
sieht bei mir so aus und hat gewicht 44

[lEn00x]

dann macht man für alle knoten mit ungeradem grad (alle außer b) ein perfektes matching.

ich hab zwar eins gefunden, sehr algorithmisch war das aber nicht, das müsste man sich gesondert überlegen, wie man das kriegt.

eine möglichkeit ist: (a , d) , (c , g) , (e , f) mit gesamtgewicht 21
Ich komme auf das gleiche ergebnis beim pattern matching.
ich bin folgender maßen vorgegangen:

1.) Knotenmenge V=(a,c,d,e,f,g), Kantengewichte wie in der Angabe
1.1.) Daraus eine Gewichtungsmatrix erstellen (wie bsp. 9 nur eben ohne "b")
2.) Zeilenweise die matrix auslesen, wobei die spalten vor dem auslesen immer aufsteigend sortiert werden.
Dann minimalen Wert wählen und der Pattern-Matching-Kantenmenge hinzufügen, sowie die beiden Knoten aus V entfernen.
Die Gewichtungsmatrix aus der neuen Knotenmenge V erstellen usw.

[tschurlo]

Hab auch dieses Matching verwendet. Hoffe halt, dass es wirklich das "perfekte" ist. Hab dieselbe Tour rausbekommen wie mit 5.9: a-b-d-c-g-e-f-a

lg

[Christoph]

Wie bestimmt man min. Kantengewicht bei perfektem Matching?

[tschurlo]

Den Algorithmus dazu haben wir nicht besprochen... In der VO haben wir immer nur so eines angenommen, a la "angenommen das waere ein perfektes Matching".
Reicht hier wohl mit ausprobieren...

lg

[Christoph]

Frage:

1) buechengustel verwende perf. Matching.
führt zu (a , d) , (c , g) , (e , f) Gewicht 21

Durch CH Algorithmus erhält man als Ergebnis Gewicht 44

2) Bei mir kommt beim perfekt Match
(a-f) (d-c) (g-e) mit Gewicht 24 !!! also schlechter

aber dafür ein besseres Endergebnis Gewicht 42


Laut Buch hätte ich das min. Gewicht beim perfekten Matching nehmen müssen,
also habe ich einen Fehler gemacht und nur zufällig ein besseres Endergebnis bekommen

a) ist das richtig ??

b) Vermute ich richtig das perfektes Matching durch die <EDIT>Distanzmatrix</EDIT> bestimmt wird?

[wolti]

Laut Buch hätte ich das min. Gewicht beim perfekten Matching nehmen müssen,
also habe ich einen Fehler gemacht und nur zufällig ein besseres Endergebnis bekommen
a) ist das richtig ??

Ja, das sehe ich so.


b) Vermute ich richtig das perfektes Matching durch die Adjaz. matrix bestimmt wird?

Naja. Durch die Adjazenzmatrix sicher nicht, aber durch die Distanzmatrix (Also wenn du die Kosten der Kanten einträgst) kannst du das sehr wohl damit machen. Du rechnest/zeichnest dann aber zuviel, da du ja nur die Knoten brauchst, wo einen ungeraden Grad haben. Obwohl.. Für den MST ist es ja auch hilfreich, wenn die Kosten hast.
De fakto geht das bei diesen drei am besten im Kopf würde ich sagen mit den Paaren. Aber ansonsten ist es ja ein Minimierungsproblem, du kannst also jeden dir bekannten Algo drauf anwenden.

Grüße,
Wolti

[Christoph]

Naja. Durch die Adjazenzmatrix sicher nicht, aber durch die Distanzmatrix


Danke, hab natürlich die Distanzmatrix gemeint

[inversesElement]

In diesem thread kommt nirgends auch nur ein wort von christophides vor!!! Hat irgendwer eine ahnung was die Christophides-Heuristik ist?
Konnte das auch nicht im superübersichtlichen skriptum finden.

Help! Ich hab morgen ue!



Ok... wollt grad editen dass ich ein tr***** bin und es gefunden hab da hat flowyes auch schon geantwortet *thx*
Wieso kann dieses Skriptum kein Strg+F?

[Flowyes]

Seite: 152.
Ich häng auch noch bei dieser Heuristik, mal schaun ob ich's versteh ;)

[inversesElement]

Seite: 152.
Ich häng auch noch bei dieser Heuristik, mal schaun ob ich's versteh ;)

Das kann ich verstehen, der einzige unterschied den ich in der beschreibung von christophides / ST feststellen kann ist, dass man bei chr die kanten nicht verdoppelt sondern ihnen gleich EINE richtung gibt (ka nach welchen algorithmischen kriterien).

Was ich nicht checke ist was jeweils "Bestimme" (eine eulertour) oder solche unscharfen sachen algorithmisch heisst...

Wenn ich mir die kürzeste tour nach "hinschauen-algo" selber zusammensuche dann macht es null unterschied ob ich ch/st verwende.

cu invel

[inversesElement]

Ok ich glaub jetzt hab ichs so ca - der Christophides gibt sozusagen einfach nur einen kleinen "tipp",
welche die tourschliessenden / kreisbildenden kanten sein könnten. Bei Spanning tree muss man (bzw der algo) die rein durch ausprobieren finden.

gn8,
invel

[Kitty]

Frage:

1) buechengustel verwende perf. Matching.
führt zu (a , d) , (c , g) , (e , f) Gewicht 21

Durch CH Algorithmus erhält man als Ergebnis Gewicht 44

2) Bei mir kommt beim perfekt Match
(a-f) (d-c) (g-e) mit Gewicht 24 !!! also schlechter

aber dafür ein besseres Endergebnis Gewicht 42


Laut Buch hätte ich das min. Gewicht beim perfekten Matching nehmen müssen,
also habe ich einen Fehler gemacht und nur zufällig ein besseres Endergebnis bekommen

a) ist das richtig ??

b) Vermute ich richtig das perfektes Matching durch die <EDIT>Distanzmatrix</EDIT> bestimmt wird?

bei (a-f) (d-c) (g-e) kommt bei mir Gewicht 21 raus und nicht 24

[locutus]

Der Unterschied zwischen Christophides und Spanning Tree ist nur die Methode zur Erreichung von geraden Knotengraden.

Diese ist notwendig um die Voraussetzungen für eine Eulertour zu schaffen. (Skriptum Seite 150 unten: ST-Heuristik Schritt 3)

Die geraden Knotengrade werden bei Spanning Tree durch Verdoppeln der Kanten und bei Christophides durch das Matching der Knoten mit ungeradem Grad sichergestellt.