Der in diesem Abschnitt beschriebene Python Code ist im Modul searchalgos.py zusammengefasst.
Algorithmen, welche die Suche eines Pfades von einem Start- zu einem Zielzustand realisieren, bauen sequenziell einen Suchbaum auf. In diesem Baum repräsentieren die Knoten die Zustände und die Kanten die durch Aktionen ausgelösten Zustandsübergänge. Aktionen sind in der Regel mit Kosten verbunden. Die Wurzel des Suchbaums ist der Startzustand. Von diesem ausgehend wird der Baum mit neuen Knoten solange erweitert bis ein Zielzustand gefunden ist.
Es bietet sich an Knoten als Objekte einer Klasse node zu implementieren.:
class node(object):
def __init__(self,name,uID,pre=None,costInc=1):
self.uniqueID=uID
self.name=name
self.predecessors=[]
self.cost=0
if pre != None:
self.predecessors.extend(pre.predecessors)
self.predecessors.append(pre)
self.cost=pre.cost+costInc
Objekte der Klasse node haben folgende Instanzattribute:
Die Klasse node wird von den im Folgenden beschriebenen Algorithmen Breitensuche, Tiefensuche und Uniform Cost Search benutzt.
Die Breitensuche expandiert jeweils alle Knoten einer Ebene, bevor sie die Knoten der nächst tieferen Ebene expandiert. In jedem Schritt wird vor dem Expandieren getestet ob der Zustand des aktuellen Knoten gleich dem Ziel ist. In diesem Fall bricht der Algorithmus ab. In diesem Abschnitt wird eine nicht-rekursive Implementierung der Breitensuche vorgestellt.
Beim Aufruf werden dem Algorithmus folgende Parameter übergeben:
Der Rückgabewert ist False falls der Zielknoten (suche) nicht gefunden wird. Ansonsten wird der Zielknoten zurückgegeben. Der Zielknoten enthält alle Informationen der vollständigen Lösung, d.h. den Pfad vom Start- zum Zielknoten und die akkummulierten Pfadkosten.
Der Algorithmus benutzt die in Abschnitt Hilfsfunktionen beschriebene Funktion schonbesucht().
def breitensuche(adj, start, suche,verbose=False):
nodeCount=0
s=node(start,nodeCount)
queue = [ s ]
while len(queue) > 0:
aktiverKnoten = queue.pop(0)
if aktiverKnoten.name==suche:
return aktiverKnoten
if verbose:
print aktiverKnoten.name
if adj[aktiverKnoten.name]:
for andererKnoten in adj[aktiverKnoten.name].keys():
if schonbesucht(aktiverKnoten,andererKnoten):
continue
if verbose:
print " ",andererKnoten
nodeCount+=1
cost=adj[aktiverKnoten.name][andererKnoten]
s=node(andererKnoten,nodeCount,pre=aktiverKnoten,costInc=cost)
queue.append(s)
if verbose:
print [a.name for a in queue]
return False
Die Tiefensuche expandiert zunächst in jeder Ebene nur einen Knoten. In der jeweils nächsten Iteration wird einer der neu entstandenen Knoten ausgewählt und dieser expandiert. Dieser Prozess läuft entweder solange bis der Zielknoten gefunden ist, oder kein neuer, in diesem Pfad noch nicht vorhandener, Zustand erzuegt werden kann. In diesem Abschnitt wird eine rekursive Implementierung der Tiefensuche vorgestellt.
Beim Aufruf werden dem Algorithmus folgende Parameter übergeben:
Der Rückgabewert ist False falls der Zielknoten (suche) nicht gefunden wird. Ansonsten wird der Zielknoten zurückgegeben. Der Zielknoten enthält alle Informationen der vollständigen Lösung, d.h. den Pfad vom Start- zum Zielknoten und die akkummulierten Pfadkosten.
Der Algorithmus benutzt die in Abschnitt Hilfsfunktionen beschriebene Funktion schonbesucht().
def tiefensuche(adj, startnode, suche,nodeCount=0,verbose=False):
if startnode.name == suche:
return startnode
#startnode=node(start,nodeCount)
if adj[startnode.name]:
for andererKnoten in adj[startnode.name].keys():
if schonbesucht(startnode,andererKnoten):
continue
if verbose:
print " ",andererKnoten
nodeCount+=1
cost=adj[startnode.name][andererKnoten]
newnode=node(andererKnoten,nodeCount,pre=startnode,costInc=cost)
a = tiefensuche(adj,newnode,suche,nodeCount,verbose)
if a:
return a
return False
Dieser Algorithmus unterscheidet sich von der Breitensuche nur darin, dass die neu erzeugten Knoten nach den aufsteigenden Pfadkosten geordnet in die Liste der Knoten eingefügt werden. Dadurch wird gewährleistet, dass immer der erzeugte, aber noch nicht expandierte, Knoten mit den geringsten Pfadkosten als nächster expandiert wird. Damit ist die Uniform Cost Search optimal, auch im Fall ungleicher Kosten pro Aktion. Die Breitensuche ist nur dann optimal, wenn alle Aktionen die gleichen Kosten haben.
Beim Aufruf werden dem Algorithmus folgende Parameter übergeben:
Der Rückgabewert ist False falls der Zielknoten (suche) nicht gefunden wird. Ansonsten wird der Zielknoten zurückgegeben. Der Zielknoten enthält alle Informationen der vollständigen Lösung, d.h. den Pfad vom Start- zum Zielknoten und die akkummulierten Pfadkosten.
Der Algorithmus benutzt die in Abschnitt Hilfsfunktionen beschriebene Funktionen schonbesucht() und insertNodeSorted().
def uniformCostSearch(adj, start, suche,verbose=False):
nodeCount=0
s=node(start,nodeCount)
queue = [ s ]
while len(queue) > 0:
aktiverKnoten = queue.pop(0)
if aktiverKnoten.name==suche:
return aktiverKnoten
if verbose:
print aktiverKnoten.name
if adj[aktiverKnoten.name]:
for andererKnoten in adj[aktiverKnoten.name].keys():
if schonbesucht(aktiverKnoten,andererKnoten):
continue
if verbose:
print " ",andererKnoten
nodeCount+=1
cost=adj[aktiverKnoten.name][andererKnoten]
s=node(andererKnoten,nodeCount,pre=aktiverKnoten,costInc=cost)
insertNodeSorted(queue,s)
if verbose:
print [a.name for a in queue]
return False
Die Funktion schonbesucht(knoten,name) testet, ob der Zustand name schon in den Vorgängern des Knoten knoten enthalten ist. Übergeben werden der Funktion:
Der Rückgabewert ist False, falls der Zustand name noch nicht in den Vorgängern von knoten enthalten ist, sonst True.
def schonbesucht(knoten,name):
for s in knoten.predecessors:
if s.name==name:
return True
return False
Die Funktion insertNodeSorted(liste,knoten) fügt das node-Objekt knoten geordnet (nach aufsteigenden Pfadkosten) in die Knotenliste liste ein. Übergeben werden der Funktion:
Die Funktion gibt die erweiterte und geordnete Liste zurück.
def insertNodeSorted(liste,knoten):
i=0
for oldNode in liste:
if oldNode.cost>knoten.cost:
liste.insert(i,knoten)
return liste
else:
i=i+1
liste.insert(i,knoten)
return liste