Bsp 6.8

[Merlin]

Also eine Nachbarschaftsfunktion muss sozusagen nur folgende Bedingung erfüllen:
Ausgehend von jeder möglichen Lösung muss eine optimale Lösung durch wiederholte Anwendung der Nachbarschaftsfunktion mit einer Wahrscheinlichkeit größer Null erreichbar sein.

Da würde ich das 2-Opt-änhnlichen Verfahren beim Symmetrische TSP von Seite 158 einfach umkehren.
Zwei benachbarte (also sich nicht überkreuzende) Kanten werden zufällig ausgewählt und entfernt.
Die zwei verbleibenden Pfade werden mit zwei neuen Kanten zu einer neuen Tour zusammengefügt, sprich es werden gekreuzte Verbindungen hergestellt.

zu Punkt 3:
Es ist doch gar nicht möglich 100% mit Simulated Annealing eine absolut optimale Lösung zu erreichen, oder habe ich das falsch verstanden?
Ich dachte ich kann mich nur annähern an ein Optimum...

[[fl]Quel`Tos]

ich glaub beim 3. punkt gehts eher darum, dass man zeigt, dass die verwendete nachbarschaftsfunktion auch wirklich die optimale lösung liefern KANN.

[Merlin]

Oder könnte man auch das r-Opt-Verfahren nehmen?

In PseudoCode dann:

r-Opt(x) = N(x) {

1) Wähle eine beliebige Anfangstour T = {(i1,i2),(12,i3),...(in,i1) }

2) Sei Z die Menge aller r-elementigen Teilmengen von T

3) Für alle R € Z : Setze S=T\R und konstruiere alle Touren, die S enthalten. Gibt es eine unter diesen, die besser (sprich schwerer in unserem Fall) als T ist, wird diese das aktuelle T und gehe zu 2

4) T ist das Ergebnis

}

und unser Simulated-Annealing Algor. von Seite 156

Müsste doch auch funktionieren, oder? nur dass die etwas schwerer zum Veranschaulichen ist.

Seid ihr auch der Meinung, dass das stimmern könnte?

[Merlin]

Ich machs mal mit dem 2-Opt-Verfahren:

1) Wähle eine beliebige Anfangstour T={(i1, i2), (i2,i3), ... , (i(n),i1)};
sei i(n+1) = i1

2) Setze Z = { {ip, ip+1), (iq, iq+1) } c T | 1 <= p, q<=n && p+1 < q }

3) Für alle Kantenpaare {(ip, ip+1),(iq,iq+1)} aus Z :

Falls ci(p)i(p+1) + ci(q)i(q+1) > ci(p)i(q) + ci(p+1)i(q+1)

setze T = (T \ {ip, ip+1), (iq, iq+1) } ) u {(ip,iq), (ip+1,iq+1)

gehe zu 2)

4) T ist das Ergebnis


Bei Punkt 2 würde aber immer nur in dem Fall ein Pfad entstehen, der sich vom vorherigen unterscheidet, wenn es noch sich überkreuzende Kanten gibt.
Dies belegt, dass also nicht immer ein Pfad entsteht, der sich vom vorigen unterscheidet.
Ist das ganze Verfahren dann falsch, welches ich gefunden habe?
Vielleicht sollt man gerade deswegen auf das r-Opt Verfahren wechseln...

[reddi]

ist bei den übungen das r-opt verfahren schlussendlich richtig gewesen?