6.Übung Bsp10

[MrAngel]

Hi Leute!

Ich hab zwar für die ganzen Kanten mit der Manhatten Distanz
die Gewichte ausgerechnet, aber was muss man hier dann machen?
Ich habs mir im Buch druchgelesen, aber irgendwie kapier ich das
nicht ganz obwohl es mir logisch erscheint. :confused:

Kann vielleicht jemand den Lösungsweg bzw. posten wie man
das angeht?

Lg MrAngel

[steppenfisch]

ok, also auf seite 162 ist das ganze eh erklärt, und so wie ich das verstanden habe (man haue mich wenn ich mich irre) geht das folgendermassen, und ist irgendwie eh ziemlich einfach.

also zuerst rechnest du eben die gewichte aus, bzw zählst sie ab.
einfach die schritte die du in die x-achse machst, plus die schritte die du in die y-achse gehst. (so kann man manhattan-distanz etwas einfach angeben)

danach fängst du laut angabe bei punkt d an, und schaust bei beiden elterntouren, welche wege von d weggehen, und nimmst den mit dem geringsten gewicht. also in dem fall D zu E mit wert 4.
von dort schaust du weiter und suchst den kürzesten weg aus den elterntouren zu punkten, an denen du noch nicht warst. in dem fall E zu B mit wert 2.
das ganze machst du so lange, bis du in den elterntouren keinen weg mehr zu einem noch nicht verbundenen knoten findest. in dem fall erfindest du einfach einem weg zu einem dieser knoten und gehst von da weiter..

also nochmal die lösung:
1.schritt: DE(4) oder DF(7), nimm DE
2.schritt: EB(2) oder EA(5), nimm EB
3.schritt: BC(2) oder BA(3), nimm BC
4.schritt: CA(5) oder CF(7), nimm CA
5.schritt: nix da, erfinde weg AF(8)
6.schritt: FD(7)

der weg is zwar nicht wirklich kürzer als die alten, aber dafür isser neu, und darum gehts ja hauptsächlich bei den evolutionären algorithmen.

[bosie]

5.schritt: nix da, erfinde weg AF(8)
6.schritt: FD(7)


genau das ist mein problem.
1) darf ich einen schon besuchten knoten überhaupt noch einmal besuchen?
2) wie kommst du da auf FD ?
AD+DF ist ja wesentlich länger als zb AB+BF

danke

[Merlin]

besuchen darfst du keinen Knoten nocheinmal.
Am Schluss, wenn W={}, was soviel bedeutet, dass alle Knoten schon einmal besucht sind, stoppt der Algorithmus und schliesst die Tour sprich er verbindet den letzten Knoten, wo ich stehengeblieben bin mit dem Anfangsknoten (also F mit D).
Dies lässt sich ablesen am Algorithmus aus dem Buch.

[bosie]

ok nur wie mahce ich das dann:

ich steh dann bei A und F ist noch nicht besucht. dann kreuze ich ja meinen weg. ist das überhaupt erlaubt?
dachte das wäre nämlich nicht erlaubt :(