Backtracking (Prinzip 1 )

so war es vorher 

Algorithmus 'Zum Ausgang'

solange nicht am Ausgang
      falls es ein angrenzendes, nicht markiertes Feld gibt
            bewege den Helden auf dieses Feld und markiere es
      sonst
            bewege den Helden zurück auf das zuletzt begangene Feld

Prinzip 

Der Algorithmus verfährt nach dem Prinzip

wenn möglich vorwärts, sonst rückwärts

Dieses Prinzip lässt sich auch bei vielen anderen Problemen anwenden.

 

Voraussetzungen:

• Das Problem lässt sich durch eine Folge von Entscheidungen lösen.
• Zu jedem Zeitpunkt stehen nur endlich viele Entscheidungen zur Wahl.
• Manchmal - aber nicht immer - ist sofort erkennbar, dass eine mögliche Entscheidung falsch ist.

 

Nicht jede falsche Entscheidung ist sofort als eine solche erkennbar. Es ist z.B. falsch, in eine Sackgasse einzubiegen. Das erkennt man aber erst später, nämlich wenn man merkt, dass es nicht weiter geht.

Man kann nun folgendermaßen eine zur Lösung führende Entscheidungsfolge aufbauen:

 

Algorithmus Backtracking:

solange Lösung noch nicht gefunden
      falls es jetzt eine noch nicht probierte, mögl. Entscheidung gibt
            falls diese nicht erkennbar falsch ist
                  verlängere die Entscheidungsfolge um diese Entscheidung
                  {'treffe die Entscheidung'}
      sonst
            entferne die letzte Entscheidung aus der Entscheidungsfolge
            {'nimm die zuletzt getroffene Entscheidung zurück'}

 

Beim Labyrinth ist die Zuordnung so:

• Entscheidung: Ein angrenzendes Feld, auf welches der Held bewegt wird. Je nachdem, wo sich der Held gerade befindet, gibt es bis zu vier mögliche Entscheidungen.
• Entscheidungsfolge: Eine Folge begangener, benachbarter Felder - also ein Weg - im Labyrinth.
• Erkennbar falsch ist eine Entscheidung, wenn sie auf ein bereits begangenes Feld führt.
• Lösung gefunden: aktuelles Feld ist der Ausgang.

Gib in den folgenden Situationen an, wieviele Entscheidungen prinzipiell möglich und wieviele davon erkennbar falsch sind.

Zahl der möglichen Entscheidungen?  
Zahl der erkennbar falschen Entscheidungen?  

Zahl der möglichen Entscheidungen?  
Zahl der erkennbar falschen Entscheidungen?  

Zahl der möglichen Entscheidungen?  
Zahl der erkennbar falschen Entscheidungen?  

Zahl der möglichen Entscheidungen?  
Zahl der erkennbar falschen Entscheidungen?  

Zahl der möglichen Entscheidungen?  
Zahl der erkennbar falschen Entscheidungen?  

Seite 4/10