PDA

View Full Version : [FRAGE] - 6.3

bosie
16-06-2004, 14:40
hoi,
mir fällt nix ein, hat irgendeiner eine idee?

dankend
bosie
Havoc
16-06-2004, 15:11
wurd sagen man zeichnet einfacheinen nicht ganz optimalen graphen, wobei sich keine kanten kreuzen dann kann 2-opt auch nichts mehr verbessern und die sache hat sich!!!
:devil:
nonamenobody
16-06-2004, 19:52
Hast du auch ein einfaches Beispiel, für das du das leicht überprüfen kannst?

lg
Philipp
_logonoff_
17-06-2004, 02:20
[edit] tja, was das internet alles zu bieten hat, wenn man nur lang genug sucht:
http://itp.nat.uni-magdeburg.de/~mertens/TSP/node3.html#SECTION00031000000000000000

eigentlich also eh relativ simpel:

http://stud3.tuwien.ac.at/~e0325159/2-nonopt.gif

hier müsste nämlich 3-opt ran, damit das ding optimal wird und dann so ausschaut:

http://stud3.tuwien.ac.at/~e0325159/3-opt.gif
seg2
17-06-2004, 10:00
Wie ist das auf Seite 154 zu verstehen: "Alle möglichen Paare von in der Tour nicht direkt nebeneinanderliegenden Kanten werden temporär entfernt ... und durch neue ersetzt"?
_logonoff_
17-06-2004, 12:48
Wie ist das auf Seite 154 zu verstehen: "Alle möglichen Paare von in der Tour nicht direkt nebeneinanderliegenden Kanten werden temporär entfernt ... und durch neue ersetzt"?

du hast deinen graphen. aus dem nimmst du zwei kanten weg, die keinen knoten gemeinsam haben (= nicht direkt nebeneinanderliegen). dann schaust du, ob der graph "besser" wird, wenn du die knoten der weggenommenen kanten durch andere kanten miteinander wieder verbindest.
seg2
17-06-2004, 12:57
du hast deinen graphen. aus dem nimmst du zwei kanten weg, die keinen knoten gemeinsam haben (= nicht direkt nebeneinanderliegen). dann schaust du, ob der graph "besser" wird, wenn du die knoten der weggenommenen kanten durch andere kanten miteinander wieder verbindest.


OK, danke!

Aber sind deine beiden obigen Graphen nicht schon optimal?
Oder ist "global optimal" aus der Angabe anders definiert als "optimal"?
_logonoff_
17-06-2004, 14:05
Aber sind deine beiden obigen Graphen nicht schon optimal?
Oder ist "global optimal" aus der Angabe anders definiert als "optimal"?

nein, der obere ist "schlechter" als der untere (der kantenlängen mit euklidischem abstand nach). der witz daran ist eben, dass man mit 2-opt nicht aus dem oberen den unteren erzeugen kann. global-optimal heißt so viel wie "besser gehts nicht".