vorige nächste

Ein Weg aus der Sackgasse wird gesucht


Die Unmöglichkeit die großen Probleme nicht mit vollständigen oder greedy Verfahren lösen zu können, heißt aber nun nicht, dass man in charismatischer Gottergebenheit beruhigt die Hände in den Schoß legen kann, weil man sowieso nichts machen kann. Hier beginnt die eigentliche Arbeit des Informatikers: nach anderen erfolgreichen Strategien zu suchen, um diese Probleme bewältigen.

Ein recht erfolgreicher Weg führt von der Strategie ...

(Die Formulierungen der Bedingungen sind jeweils auf das tsp bezogen)

es wird bei jeder Entscheidung der Weg expandiert, der die geringste Länge aufweist (allein so wäre es greedy) und dann, wenn ein vollständiger Weg gefunden wurde, werden andere noch offene Wege solange versucht, bis sie entweder selbst eine Lösung und damit eine bessere darstellen oder verworfen werden, weil sie länger werden

... über ...

es wird bei jeder Entscheidung der Weg expandiert, der in der Summe aus seiner Länge und einem Schätzwert für die Restlänge minimal ist

... zu ...

man verfolgt von all den Wegen wirklich nur den mit minimaler Länge überhaupt weiter.

... zu einem in vielen Fällen sehr erfolgreichen Verfahren.

Ein anderer Ansatz zur Lösung verfolgt mit den Evolutionären Algorithmen eine grundsätzlich andere Suchstragie.

Es ist eine Strategie, die wir am Anfang unseres Kurses nur ganz nebenbei erwähnt haben, eigentlich nur der Vollständigkeit halber, und dann gleich wieder verworfen haben. Es ist der Ansatz von zufälliger Suche!


Bomze schreibt zu Branch and Bound:

Branch-and-bound stellt die wesentlichste Methode zur exakten Lösung von diskreten Optimierungsproblemen dar. Die Grundidee dabei ist eine partielle Enumeration des zulässigen Bereichs. Dabei versucht man schrittweise Probleme mit einem kleineren zulässigen Bereich zu lösen, die dann ganze Teile des zulässigen Bereichs als mögliche Lösungen ausschließen. Für den speziellen Fall von binären Variablen bezeichnet man derartige Verfahren auch als implizite Enumeration.