Übungsaufgabe 00857 B0401

aktuelle Lösung(2) = {K}{C,G,U}{H,M}=Nachbarlösung(1) , da akzeptiert worden

f(akt) = 1 , Zielfunktion Summe der gemeinsamen Kanten pro Klasse (hier wegen C-U)

Nachbarlösung = {G,K}{C,U}{H,M} , C wurde bereits bei Z1 erfolgreich (akzeptiert) "vernachbarschaftet" , drum ist nun nach Aufgabenstellung (lexografische Ordnung) G dran, wurde in die erste Klasse verschoben (hätte auch in 3 landen können).

f(neu) = 1 , immer nur noch C-U, wieder 1 deshalb

Δf = 0 , f(neu) - f(alt)=1-1=0

T_2 = 0,5 * T_1 = 0,5 * 20 = 10 (Temperatur sinkt nach jeder Akzeptanz)

Akzeptanzbestimmung über p_2 nun erforderlich, da Δf>= 0
p_2 = e ^ ( -Δf / T_2) = e ^(0 / 10)= e^0 = 1
R >= p nicht erfüllt (kein Rückfall zu IT_SA , damit auch keine neue Nachbarschaftslösung notwendig) , also Lösung akzeptiert
--> Temperatur sinkt in T_3 wieder, weil eine Lösung akzeptiert wurde

R ist vorgegeben, nur von Relevanz falls Δf > 0

Akzeptanz,
es wird akzeptiert wenn Δf < 0 (Verbesserung der Lösung)
oder
wenn Δf >=0 und gleichzeitig R < p (oder R nicht größergleich p, Nachbarschaftsschleife)
--> also ja hier (Δf < 0 , R=0,78 < 1=p)

Ja, die Aufgabe entspricht der Übungsaufgabe 4.2. Lediglich die Zufallszahlen unterscheiden sich ab Zeile 9. Dadurch nimmt die Geschichte bei den gewählten Umfärbungen hier einen ungünstigen Verlauf! Im Gegensatz zu ÜA 4.2 wird das Optimum hier nicht erreicht.
Die erste Spalte beinhaltet die aktuelle Lösung. Von hier ausgehend wird eine Nachbarlösung erstellt, gemäß der lexikographischen Ordnung...
Der umgefärbte Knoten ist unterstrichen dargestellt. Dieser Schritt ist keineswegs eindeutig festgelegt! C hätte zum Beispiel in der ersten Zeile auch wie H und M gefärbt werden können statt wie G und U!
Auch deine Zielfunktion kann gegebenenfalls abweichen. Die angegebene Lösung ist von daher beispielhaft und nicht allgemeingültig!

Die Nachbarlösung steht in Spalte 3. Nach der in c) spezifizierten Zielfunktion ist der jeweilige Wert (zweite und vierte Spalte) der aktuellen und der Nachbarlösung jeweils 1: bei der aktuellen Lösung sind C und K, bei der Nachbarlösung C und U gleich gefärbt.
Die fünfte Spalte weist die Differenz der vierten und zweiten Spalte aus.
Die sechste Spalte steht für die Temperatur. Sie hat in der ersten Zeile noch ihren Anfangswert. Wird die Nachbarlösung akzeptiert, wird die Temperatur gemäß Aufgabenstellung halbiert (in der nächsten Zeile). Bei Nicht-Akzeptanz bleibt sie in der nächsten Zeile unverändert.
Die siebte Spalte berechnet sich aus der fünften und sechsten Spalte gemäß Formel auf Seite 53. In der achten Spalte steht eine vorgegebene Zufallszahl, mit der die siebte Spalte verglichen wird. Ist der Wert von p größer als R, dann wird die Nachbarlösung akzeptiert, sonst nicht. Das Ergebnis dieser Prüfung wird letztlich in der letzten Spalte vermerkt.

Jetzt also die zweite Zeile: In der ersten Zeile wurde C umgefärbt, die Lösung wurde akzeptiert. Die dritte Spalte der ersten Zeile ergibt jetzt die erste Spalte der zweiten Zeile. Jetzt muss nach Aufgabenstellung G umgefärbt werden, bis eine Lösung akzeptiert wird. Hier wurde G von der zweiten auf die erste Farbe umgefärbt (Möglich wäre auch die dritte Farbe gewesen!)
Dies stellt jetzt die Nachbarlösung dar. Nach wie vor haben C und U jeweils die gleiche Farbe, die Zielfkt. jeweils den Wert 1, die Differenz ist also wieder 0.
Da die Lösung der ersten Zeile akzeptiert wurde, wurde T halbiert.
Für p ergibt sich daraus 1, was größer ist als 0,78, daher wird die Lösung akzeptiert.

T halbiert sich wieder in der dritten Zeile, die dritte Spalte der zweiten Zeile wird zur ersten Spalte der dritten Zeile. Hier wird jetzt H umgefärbt. Jetzt haben neben C und U zusätzlich G und H die gleiche Färbung. Die vierte Spalte wird zu 2, die fünfte zu 1. Die sechste Spalte errechnet sich jetzt zu 0,819. Da R größer ist als 0,819, wird die Nachbarlösung nicht akzeptiert.

T ändert sich also für die nächste Zeile nicht, die erste Spalte bleibt auch unverändert. Die Auswertung der vierten Zeile verläuft ähnlich.

Die Umfärbung von H hat nichts eingebracht, die ursprüngliche Färbung wird beibehalten. Dies wird jetzt in Zeile 5 "berechnet". Dadurch verringert sich T jetzt wieder und es wird mit der Umfärbung von K weiter gemacht...

Oh, da war jemand schneller! Hab ich solange getextet?!

drei,

ich hätte noch eine Frage, jedoch kann ich nicht beurteilen, vielleicht wurde sie mit dem Ausdruck "lexikographischen Ordnung" auch schon beantwortet.
also für mich bedeutet das Wort gerade, dass da steht {C,G,U} statt {G,C,U}.
Meine Frage wäre jedoch gibt es eine Reihenfolge für die Alternativen/Nachbarlösungen?
Gerade in Aufgabe B0403 könnte man sich ja so durch logisches Denken einige "neins" sparen.
Jedoch Frage ich mich, ob das mit den "R's" dann noch so ist wie gewollt, also zumindest ist es nicht so wie in der Lösung.

Danke+Glg Aida

Die lexikographische Ordnung bezieht sich hier nur auf die Reihenfolge des Umfärbens. Erst wenn ein vorhergehender Knoten umgefärbt ist, darf ein nachfolgender Knoten umgefärbt werden.
Also erst C, dann G, dann H...
H hat schon die "richtige" Farbe, muss aber nach Aufgabenstellung umgefärbt werden. Hier gibt es keine Wahlmöglichkeit.

Für das Umfärben eines Knotens an sich ist keine zwingende Ordnung vorgegeben. Da bestehen Alternativen. So wie von @Weseb und mir oben angedeutet.

Eine einzig wahre Lösung gibt es also nicht.

In der Klausur wirst du keine so riesige Tabelle ausfüllen müssen, da lohnt es sich nicht, das passend "hinzubiegen".

Robin, ja verstanden, trotzdem könnte ich ja zwei Schritte vertauschen und dann passen die R's nicht mehr.
Weißt du was ich meine? Z.b. Übungsaufgabe 4.2 vertauschen von Zeile 3 und 4 bei vorgegebenen R's.

Glg Aida

robin schrieb:

Eine einzig wahre Lösung gibt es also nicht.

Zum Vergrößern anklicken....

Darum geht es, es gibt verschiedene Möglichkeiten die Aufgabe zu lösen, ein vorgegebener starrer Weg gibt es nur bei sehr strengen Regeln in welcher Reihenfolge die Nachbarschaftslösungen zu bestimmen sind, das ist hier nicht gegeben.

Meist ist das Aufgabenziel nicht die optimale Lösung zu finden (Simulated Annealing dürfte das auch nicht garantieren), sondern nur das Prinzip verstanden zu haben und damit umgehen zu können.

Ich glaube, dass ich es jetzt auch verstanden habe.
Danke für die guten, ausführlichen Erklärungen! 🙂(y) :thumbsup