############################# Suchalgorithmen in Python ############################# Der in diesem Abschnitt beschriebene Python Code ist im Modul `searchalgos.py `_ zusammengefasst. Die Klasse Knoten =================== 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: * *uniqueID*: eindeutiger Bezeichner eines Knotens * *name*: Der Name des Zustands, den der Knoten repräsentiert * *predecessors*: Eine Liste aller Knoten des Pfades vom Startknoten (inklusive) zum aktuellen Knoten (exklusiv). * *cost*: Die akkumulierten Kosten, die auf dem Pfad vom Startknoten zum akuellen Knoten entstanden. Die Klasse ``node`` wird von den im Folgenden beschriebenen Algorithmen `Breitensuche`_, `Tiefensuche`_ und `Uniform Cost Search`_ benutzt. Breitensuche =============== 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: * **adj**: Ein verschachteltes Dictionary, dessen Keys die möglichen Zustände sind. Die Values sind Dictionaries, dessen Keys mögliche Folgezustände und dessen Values die Kosten für die Aktion, die in diesen Folgezustand führt, darstellen. * **start**: Ist der Name (String) des Startzustands * **suche**: Ist der Name (String) des Folgezustands * **verbose**: kann ``=True`` für die Ausgabe von zusätzlichen Informationen zum Baumaufbau gesetzt werden. 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 Tiefensuche ============== 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: * **adj**: Ein verschachteltes Dictionary, dessen Keys die möglichen Zustände sind. Die Values sind Dictionaries, dessen Keys mögliche Folgezustände und dessen Values die Kosten für die Aktion, die in diesen Folgezustand führt, darstellen. * **startnode**: Ist der Startknoten (Objekt der Klasse node) dessen Attribut ``name`` den Startzustand enthält. * **suche**: Ist der Name (String) des Folgezustands * **nodeCount**: Zählt die bisher erzeugten Knoten und entspricht der ``uniqueID`` des *startnode*. * **verbose**: kann ``=True`` für die Ausgabe von zusätzlichen Informationen zum Baumaufbau gesetzt werden. 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 Uniform Cost Search ===================== 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: * **adj**: Ein verschachteltes Dictionary, dessen Keys die möglichen Zustände sind. Die Values sind Dictionaries, dessen Keys mögliche Folgezustände und dessen Values die Kosten für die Aktion, die in diesen Folgezustand führt, darstellen. * **start**: Ist der Name (String) des Startzustands * **suche**: Ist der Name (String) des Folgezustands * **verbose**: kann ``=True`` für die Ausgabe von zusätzlichen Informationen zum Baumaufbau gesetzt werden. 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 Hilfsfunktionen ===================== Die Funktion ``schonbesucht(knoten,name)`` testet, ob der Zustand ``name`` schon in den Vorgängern des Knoten ``knoten`` enthalten ist. Übergeben werden der Funktion: * **knoten**: Ein Objekt der Klasse ``node`` dessen Vorgänger auf Übereinstimmung mit dem Zustand ``name`` getestet werden sollen. * **name**: Der Name des Zustands (String), der getestet werden soll. 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: * **liste**: Liste von node-Objekten, in welche der Knoten eingefügt werden soll. * **knoten**: Knoten (node-Objekt), der in die Liste eingeordnet werden soll. 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 Anwendung der Suchalgorithmen auf Navigationsbeispiel ======================================================== Mit dem folgenden Programm können die oben vorgestellten Suchalgorithmen angewandt werden. Hierfür wird ein Navigationsbeispiel definiert. Die Suchalgorithmen müssen einen Weg von einer Start- zu einer Zielstadt finden. Die *Straßenkarte* ist als verschachteltes Dictionary implementiert, dessen Struktur den Vorgaben des Übergabeparameter ``adj`` der oben beschriebenen Suchalgorithmen entspricht. :: if __name__=="__main__": streetMap=dict({'frankfurt':{'wuerzburg':111,'mannheim':85}, 'wuerzburg':{'frankfurt':111,'stuttgart':140,'ulm':183,'nuernberg':104}, 'nuernberg':{'wuerzburg':104,'muenchen':170,'ulm':171,'mannheim':230,'bayreuth':75,'passau':220}, 'mannheim':{'frankfurt':85,'karlsruhe':67,'nuernberg':230}, 'karlsruhe':{'mannheim':67,'stuttgart':64,'basel':191}, 'stuttgart':{'karlsruhe':64,'wuerzburg':140,'ulm':107}, 'ulm':{'stuttgart':107,'wuerzburg':183,'nuernberg':171,'muenchen':123,'memmingen':55}, 'muenchen':{'ulm':123,'nuernberg':170,'rosenheim':59,'memmingen':115,'passau':189}, 'memmingen':{'muenchen':115,'ulm':55,'zuerich':184}, 'basel':{'zuerich':85,'karlsruhe':191,'bern':91}, 'bern':{'basel':91,'zuerich':120}, 'zuerich':{'basel':85,'bern':120,'memmingen':184}, 'rosenheim':{'muenchen':59,'salzburg':81,'innsbruck':93}, 'innsbruck':{'rosenheim':93,'landeck':73}, 'landeck':{'innsbruck':73}, 'salzburg':{'rosenheim':81,'linz':126}, 'linz':{'passau':102,'salzburg':126}, 'passau':{'linz':102,'nuernberg':220,'muenchen':189}, 'bayreuth':{'nuernberg':75}, }) FROM="frankfurt" TO="muenchen" print "-"*40+" Breitensuche "+"-"*40 found = breitensuche(streetMap,FROM,TO) print "Found ",found.name print "Total cost: ",found.cost print "Node ID: ",found.uniqueID print "on path " for a in found.predecessors: print a.name,a.cost print print "-"*40+" Tiefensuche "+"-"*40 FROMNODE=node(FROM,0) found = tiefensuche(streetMap,FROMNODE,TO,verbose=True) print "Found ",found.name print "Total cost: ",found.cost print "Node ID: ",found.uniqueID print "on path " for a in found.predecessors: print a.name,a.cost print print "-"*40+" Uniform Cost Search "+"-"*40 found = uniformCostSearch(streetMap,FROM,TO) print "Found ",found.name print "Total cost: ",found.cost print "Node ID: ",found.uniqueID print "on path " for a in found.predecessors: print a.name,a.cost Durch die Eingabe von ``FROM="frankfurt"`` und ``TO="stuttgart"`` wird der Unterschied zwischen Breitensuche und Uniform Cost Search ersichtlich. Durch die Eingabe von ``FROM="frankfurt"`` und ``TO="muenchen"`` wird ersichtlich, dass die Tiefensuche für derartige Beispiele ungeeignet ist.