nachdem einige Algorithmen programmiert wurden um das TSP im Gradientenverfahren zu lösen, sind wir am Tag der Deutschen Einheit auf folgende Konstellation von Punkten gestoßen.
Das Linke Bild unterscheidet sich aufgrund des Punktes 230x140, welcher an 30x40 align-en sollte. Dazu kommt, dass das "wipeAllMultiple()" 220x250 und 220x290 an 140x350 align-en sollte.
Leider konnte das wipeAllMultiple() nicht die 220x* Punkte align-en, da 230x140 gleichzeitig an einen anderen Root (30x40) aligned werden müsste.
Nun führt das Beispiel zu einer Korrektur des wipeAllMultiple() zu einem Ansatz mit Kandidaten-Management und Backtracking.
Im folgenden wird 230x140 als Punkt A bezeichnet. Der Punkt 220x140 als B und Punkt 220x290 als C.
Es ist nun so, dass A nur an 30 aligned, weil B und C an 140 aligned wurden. Jedoch ist in wipeAllMultiple() nicht vorgesehen, dass ein Punkt A gleichzeitig an andere Roots align-en kann, außer an dem "gegenüberliegenden/alternativen Root" (kurz: gR). Um ein Alignment an anderen Roots zu ermöglichen, ist es notwendig die Punkte des "ursprünglichen Roots" (kurz: uR) mit alternativen Roots (aR) zu vergleichen.
Es bietet sich aufgrund der Zweidimmensionalität an, die vier nächstliegenden Kanten (K(p), mit oBdA p=A) zu betrachten.
Es wird wie folgt vorgegangen:
- die Punkte P von uR (hier 370x30) werden bezüglich ihres Abstandes (seboehDist) zu gR sortiert. Dabei wird nur eine grobe Sortierung (gS) gemacht, welche nur das Alignement von p (aus P) berücksichtigt, welches aufgrund der aktuellen Situation an gR existiert. D.h. es werden keine vorherigen p_i an gR aligned, um das nächste Alignement des nächsten p_i+1 zu bestimmen.
- Entlang der gS wird nun p_s aus gS gewählt, welches am nächsten zu gR liegt, und das Alignement an gR (gA), sowie das Alignment an den alternativen vier Kanten K(p) bestimmt. Das Alignement an K(p) wird hier aA bezeichnet. Mit aA_i(p) als die Kante mit i'ten Abstand zu p.
- Das beste Alignement bA zwischen aA und gA wird für p gewählt.
- Herrscht nun eine lokale Verbesserung, so wird p als "auserwählt" an aA aligned. Herrscht keine lokale Verbesserung, so wird p als "Kandidat" an aA aligned. Kandidaten werden in weiteren Alignements nicht berücksichtigt. Sie sind für später.
- Es wird mit dem nächsten p aus gS fortgefahren, bis keine Punkte mehr in gS liegen.
- Nun ist es so, dass wir Auserwählte haben und Kandidaten haben. Es wird versucht per Backtracking die Kandidaten wieder an uR zu algin-en.
- Dabei werden die Kandidaten C grob an die ursprüngliche Hull-Edge-Kante uR (ursprünglicher Root ohne Punkte) sortiert cS.
- Für jeden c aus cS wird nun ein bester Partner bP für das Alignment an uR gesucht. Der Partner ist wiederum ein Punkt aus cS, welcher noch nicht verarbeitet wurde.
- Es wird die Korrelation zwischen c und bP bezüglich uR berechnet. D.h. es gibt drei Möglichkeiten c geht alleine an uR, c geht nicht an uR oder c geht mit bP an uR. Die beste Möglichkeit wird gewählt. Der Kandidat c und evtl auch bP werden nun als "auserwählt" markiert und an ihren besten Root aligned.
- Diese Schritte werden für c aus cS wiederholt.
So kann A an 30 align-en und gleichzeitig B und C an 140.
Der ausgewählte Konkurrent wird durch die Reihe mit allen vorhanden Kanten variiert.
Es besteht die Hoffnung, dass dadurch eine globales Ziel (die Minimierung) erreicht wird.
Sehen Sie das auch so?
Mit freundlichen Grüßen, Sebastian Böhmer, München, den 3.10.2016
Im Rahmen der Konvergenz des Candidaten-Systems, ist zu beachten, dass eine Lücke im originalen Navel/(auch Unternehmen) entsteht, welche nicht durch die Gesamtkosten betrachtet werden kann, sondern nur durch den zusätzlichen Aufwand des nächsten Mitarbeiters/Points. Es kann nicht in den Gesamtkosten betrachtet werden, da die Gesamtkosten immer sinken. Jedoch ist das Sinken mit zusätzlichem Aufwand des nächsten Mitarbeiters zum Erhalt des Unternehmens einhergehend. So, dass der zusätzliche Aufwand für die Konvergenz nicht ausgelassen werden kann.
AntwortenLöschen