Optimale Suche

Optimale Suche

Der A*-Algorithmus

Ablauf

Schritt 1: Setze den Startknoten s (das Ausgangsproblem auf die OPEN-Liste)

Schritt 2: Ist die OPEN-Liste leer, beende den Algorithmus ohne Ergbnis

Schritt 3: Wähle den minimalen Knoten n bzgl. f aus der OPEN-Liste. Entferne n aus der OPEN-Liste und setzte ihn auf die CLOSED-Liste

Schritt 4: Ist n ein Zielknoten, endet A* erfolgreich. Man erzielt die Lösung, wenn man den Pfad von n zu s zurückverfolgt

Schritt 5: Andernfalls expandiere n. Erzeuge alle Nachfolger von n mit einem Verweis zurück zu n.

Für jeden Nachfolger n':

• Existiert n' noch nicht in der OPEN- oder CLOSED-Liste, schätzte f(n')=g(n')+h'(n').
• Steht n' bereits in der OPEN- oder CLOSED-Liste, muss der Verweis entlang des Pfades überarbeitet, um das Minimum von g(n') zu erhalten.
• Falls n' auf der CLOSED-Liste gegeben ist und die Verweise modifiziert sind, öffne n' wieder, d.h. entferne ihn aus der CLOSED-Liste und setzt ihn zurück auf die OPEN-Liste.

Schritt6: Gehe zu Schritt 2.

Berechnung der Gesamtkosten f

Die Gesamtkosten f(i) für einen Knoten i im Suchraum werden gebildet durch g(i) und h(i).

f(i)=g(i)+h(i)

"g" repräsentiert die Kosten vom Wurzelknoten des Suchbaum bis zu dem aktuellen Knoten i.

"h" repräsentiert die Kosten vom Knoten i zum optimalen Blattknoten "unterhalb von" i. Wenn "h" nicht bekannt muss ein Schätzer h' gewählt werden.

Wahl des Schätzer h' für TSP

Ein möglicher Schätzer h' für ein TSP ist der "minimale aufspannende Baum"(MST) der noch verbleibenden Punkte PLUS die zwei kürzesten Kanten um den MST mit dem bereits festgelegten Segment zu verbinden.

h'=Länge(MST)+Länge(kürzeste Verbindung 1)+ Länge(kürzeste Verbindung 2)

Beispiel

Im folgenden wird für f(i) folgende Formel verwendet:

f(i)=g(i)+h'(i) mit h'=Länge(MST)+Länge(kürzeste Verbindung 1)+ Länge(kürzeste Verbindung 2)

Die schwarzen Kanten repräsentieren das bereits festgelegte Segment, die roten Kanten den MST und die gestrichelten Kanten die kürzesten Verbindungen.

Gegeben sein folgendes TSP:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Ausgangsproblem:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

OPEN 1

CLOSED

1.Schritt : Konten 1 wird expandiert (Ausgangspunkt A).

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

f(2)=1+3+2+2=8

f(3)=2+4+1+1=8

f(4)=4+4+1+2=11

f(5)=5+6+1+1=13

OPEN 2 3 4 5

CLOSED 1

2. Schritt: Knoten 2 wird expandiert, da er ein Minimum von f aufweist und auf der OPEN-Liste steht. (Ausgangspunkt C)

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

f(6)=3+1+2+2=8

f(7)=4+5+1+2=12

f(8)=5+2+1+4=12

OPEN 3 4 5 6 7 8

CLOSED 1 2

3. Schritt : Knoten 6 wird expandiert, da er ein Minimum von f aufweist und auf der OPEN-Liste steht. (Ausgangspunkt B)

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

f(9)=5+0+1+2=8

f(10)=8+0+1+5=14

Länge(MST)=0, da kein MST aufgespannt werden kann.

OPEN 3 4 5 7 8 9 10

CLOSED 1 2 6

4. Schritt : Knoten 9 ist ein Blattknoten und für f minimal in der OPEN-Liste, also die Lösung.