EINFÜHRUNG |
Viele wichtige algorithmische Lösungsverfahren haben ihren Ursprung in der Praxis des täglichen Lebens, so auch das Backtracking. Wie du bereits erfahren hast, wählt der Computer einen Spielzug aus den Möglichkeiten der erlaubten Züge und verfolgt ihn konsequent weiter. Gerät er in eine Sackgasse, so nimmt er die vorhergehenden Züge systematisch zurück. Diese Lösungsstrategie heisst im täglichen Leben auch Versuch und Irrtum (trial and error). Es ist bekannt, dass sie nicht immer optimal ist. Besser wäre es, den nächsten Zug möglichst günstig im Bezug auf die Zielsetzung zu wählen [mehr... In der Informatik nennt man dies eine heuristische Suche]. |
GRAPH MIT ZYKLEN |
Beim Durchlaufen eines Graphen kann es sein, dass du nach einigen Schritten wieder im gleichen Zustand ankommst. Denke dabei zum Beispiel an das U-Bahn-Netz einer grossen Stadt, wo die Stationen eine verflochtene Struktur aufweisen. Willst du in dieser Stadt von A nach B fahren, so gibt es mehrere Möglichkeiten, und du kannst leicht auch in Zyklen herumfahren. Als Vorbereitung auf solche Navigationsaufgaben betrachtest du einen Graphen mit 5 Knoten, bei dem jeder Knoten mit jedem anderen verbunden ist.
def getNeighbours(node): return range(0, node) + range(node + 1, 5) def search(node): global nbSolution visited.append(node) # node marked as visited # Check for solution if node == targetNode: nbSolution += 1 print nbSolution, ". Route:", visited # don't stop to get all solutions for neighbour in getNeighbours(node): if neighbour not in visited: # Check if already visited search(neighbour) # recursive call visited.pop() startNode = 0 targetNode = 4 nbSolution = 0 visited = [] search(startNode)
|
MEMO |
|
Durch Prüfen, ob ein Nachbar bereits besucht wurde, kann man das Backtracking auch auf Graphen mit Zyklen anwenden. Vergisst du diese Prüfung, so wird sich dein Programm "aufhängen", was zu einem bösen Laufzeitfehler führt, da der Funktionsaufrufspeicher überläuft. |
KÜRZESTER WEG, NAVIGATIONSSYSTEME |
Das Auffinden eines Weges von einem Startort A zu einem Zielort B ist im täglichen Leben omnipräsent. Da oft viele Wege von A nach B (nicht nur nach Rom) führen, besteht meist noch die zusätzliche Aufgabe, den bezüglich eines bestimmten Kriteriums (Weglänge, Fahrzeit, Strassenqualität, Sehenswürdigkeiten, Kosten, usw.) optimalen Weg zu finden [mehr... Das Auffinden des kürzesten Wegs gemäss einer Streckenbewertung gehört zu den klassischen Algorithmen. Eine elegante Lösung wurde bereits 1959 vom berühmten Informatiker E. W. Dijkstra angegeben.]. In deinem Programm geht es nur um das Grundsätzliche. Darum wählst du ein Ortsnetz mit nur 6 Orten, die du als U-Bahn-Stationen in einer fiktiven Stadt auffassen kannst. Die Knoten des Graphen werden mit dem Namen der Stationen identifiziert. (Die Anfangsbuchstaben sind A, B, C, D, E, F, die Stationen könnten auch mit diesen Buchstaben oder mit Knotennummern identifiziert werden.) Die Angabe der Nachbarstationen ist eine Zuordnung eines Stationsnamens zu einer Liste von Namen, wozu sich ein Dictionary hervorragend eignet, das als Schlüssel (key) den Stationsnamen und als Wert (value) die Liste der Nachbarstationen hat. Statt einer Funktion getNeighbours() wird direkt das Dictionary neighbours verwendet. Analog werden die Distanzen zwischen den Stationen ebenfalls in einem Dictionary distances abgespeichert, das als Schlüssel die zwei verbundenen Stationen und als Wert die Distanz hat. Um dies Stationen in einer GameGrid einzutragen, gibt es zudem noch ein Dictionary locations mit den Zellenkoordinaten (Locations) der Stationen. Der zentrale Teil deines Programms ist eine genaue Wiederholung des oben verwendeten Backtracking-Algorithmus. Darüber hinaus benötigst du einige Hilfsfunktionen zur grafischen Darstellung.
from gamegrid import * neighbours = { 'Althaus':['Bellevue', 'Dom', 'Enge', 'Friedhof'], 'Bellevue':['Althaus', 'City', 'Dom'], 'City':['Bellevue', 'Dom', 'Friedhof'], 'Dom':['Althaus', 'Bellevue', 'City', 'Enge', 'Friedhof'], 'Enge':['Althaus', 'Dom'], 'Friedhof':['Althaus', 'City', 'Dom']} distances = { ('Althaus', 'Bellevue'):5, ('Althaus', 'Dom'):9, ('Althaus', 'Enge'):6, ('Althaus', 'Friedhof'):15, ('Bellevue', 'City'):3, ('Bellevue', 'Dom'):13, ('City', 'Dom'):4, ('City', 'Friedhof'):3, ('Dom', 'Enge'):2, ('Dom', 'Friedhof'):12} locations = { 'Althaus':Location(2, 0), 'Bellevue':Location(0, 1), 'City':Location(1, 3), 'Dom':Location(4, 2), 'Enge':Location(5, 0), 'Friedhof':Location(3, 4)} def getNeighbourDistance(station1, station2): if station1 < station2: return distances[(station1, station2)] return distances[(station2, station1)] def totalDistance(li): count = 0 for i in range(len(li) - 1): count += getNeighbourDistance(li[i], li[i + 1]) return count def drawGraph(): getBg().clear() getBg().setPaintColor(Color.blue) for station in locations: location = locations[station] getBg().fillCircle(toPoint(location), 10) startPoint = toPoint(location) getBg().drawText(station, startPoint) for s in neighbours[station]: drawConnection(station, s) if s < station: distance = distances[(s, station)] else: distance = distances[(station, s)] endPoint = toPoint(locations[s]) getBg().drawText(str(distance), getDividingPoint(startPoint, endPoint, 0.5)) refresh() def drawConnection(startStation, endStation): startPoint = toPoint(locations[startStation]) endPoint = toPoint(locations[endStation]) getBg().drawLine(startPoint, endPoint) def search(station): global trackToTarget, trackLength visited.append(station) # station marked as visited # Check for solution if station == targetStation: currentDistance = totalDistance(visited) if currentDistance < trackLength: trackLength = currentDistance trackToTarget = visited[:] for s in neighbours[station]: if s not in visited: # if all are visited, recursion returns search(s) # recursive call visited.pop() # station may be visited by another path def init(): global visited, trackToTarget, trackLength visited = [] trackToTarget = [] trackLength = 1000 drawGraph() makeGameGrid(7, 5, 100, None, "sprites/city.png", False) setTitle("City Guide") addStatusBar(30) show() init() startStation = "" while not startStation in locations: startStation = inputString("Start station") targetStation = "" while not targetStation in locations: targetStation = inputString("Target station") search(startStation) setStatusText("Shortest way from " + startStation + " to " + targetStation + ": " + str(trackToTarget) + " Length = " + str(trackLength)) for i in range(len(trackToTarget) - 1): s1 = trackToTarget[i] s2 = trackToTarget[i + 1] getBg().setPaintColor(Color.black) getBg().setLineWidth(3) drawConnection(s1, s2) refresh()
|
MEMO |
|
Die Suche nach dem kürzesten Weg in einem Graphen gehört zu den Grundaufgaben der Informatik. Die hier gezeigte Lösung mit Backtracking führt zwar zum Ziel, ist aber sehr rechenintensiv. Es gibt viel bessere Lösungsalgorithmen, die auch davon Gebrauch machen, dass man nicht alle Wege systematisch absuchen muss. (Der berühmteste heisst Dijkstra-Algorithmus.) Es ist beispielsweise wenig wahrscheinlich, dass der kürzeste Weg von einem nördlich gelegenen Startort zu einem südlich gelegenen Zielort über eine weit entfernte Station nördlich des Startorts führt. |
DREIKRÜGEPROBLEM |
Seit vielen Jahrhunderten findet man in Kinderbüchern und Zeitschriften Denksportaufgaben, bei denen eine vorgegebene Menge durch Abmessen (Umgiessen, Wägen, usw.) in bestimmte Teilmengen aufgeteilt werden soll. Das seit dem 17. Jahrhundert bekannte Dreikrügeproblem wird dem französischen Mathematiker Bachet de Méziriac zugeschrieben und lautet wie folgt:
Gemäss der Aufgabenstellung geht es also nicht nur darum, eine Lösung zu finden, was du wahrscheinlich auch mit ein bisschen Gedankenspielerei zu Stande bringst, sondern alle Lösungen zu suchen, um daraus die kürzeste zu bestimmen. Ohne Computer ist dies sehr anstrengend. Man nennt die Suche nach allen Lösungen auch Erschöpfende Suche. Wieder gehst du gemäss der vorher erprobtem Lösungsstrategie mit Backtracking vor. Zuerst erfindest du eine geeignete Datenstruktur für die Spielzustände. Du verwendest dazu eine Liste mit einem Zahlentripel, das den aktuellen Füllzustand der drei Krüge beschreibt. [1, 4, 3] soll heissen, dass der 8-Liter-Krug gegenwärtig 1 Liter, der 5-Liter-Krug 4 Liter und der 3-Liter-Krug 3 Liter enthält. Du kannst die Spielzustände wiederum als Knoten in einem Graphen modellieren und das Umgiessen als Übergang von einem Knoten zu einem seiner Nachbarknoten auffassen. Es ist hier, wie in vielen anderen Beispielen, nicht sinnvoll, den ganzen Spielbaum zu Beginn aufzubauen. Vielmehr bestimmst du die Nachbarknoten eines Knotens node in der Funktion getNeighbours(node) erst dann, wenn du sie im Laufe des Spiels tatsächlich benötigst. Dabei gehst du von folgender Überlegung aus: Unabhängig davon, welche Menge sich in den Krügen befindet, gibt es für das Umgiessen grundsätzlich 6 Möglichkeiten: Man nimmt einen der Krüge und giesst seinen ganzen Inhalt oder soviel wie Platz vorhanden ist in einen der zwei anderen Krüge. In getNeighbours() sammelst du daher in der Liste neighbours die Nachbarknoten für diese 6 Fälle. Die Funktion transfer(state, source, target) hilft dir dabei herauszufinden, welches der Nachbarzustand zu einem bestimmten Zustand state und gegebenen Krugnummern source und target beim Umgiessen von source nach target ist. Dabei werden die Kruggrössen (maximaler Inhalt) und die darin bereits enthaltenen Mengen berücksichtigt. def transfer(state, source, target): # Assumption: source, target 0..2, source != target s = state[:] # clone if s[source] == 0 or s[target] == capacity[target]: return s # source empty or target full free = capacity[target] - s[target] if s[source] <= free: # source has enough space in target s[target] += s[source] s[source] = 0 else: # target is filled-up s[target] = capacity[target] s[source] -= free return s def getNeighbours(node): # returns list of neighbours neighbours = [] t = transfer(node, 0, 1) # from 0 to 1 if t not in neighbours: neighbours.append(t) t = transfer(node, 0, 2) # from 0 to 2 if t not in neighbours: neighbours.append(t) t = transfer(node, 1, 0) # from 1 to 0 if t not in neighbours: neighbours.append(t) t = transfer(node, 1, 2) # from 1 to 2 if t not in neighbours: neighbours.append(t) t = transfer(node, 2, 0) # from 2 to 0 if t not in neighbours: neighbours.append(t) t = transfer(node, 2, 1) # from 2 to 1 if t not in neighbours: neighbours.append(t) return neighbours def search(node): global nbSolution visited.append(node) # Check for solution if node == targetNode: nbSolution += 1 print nbSolution, ". Route:", visited, ". Length:", len(visited) for s in getNeighbours(node): if s not in visited: search(s) visited.pop() capacity = [8, 5, 3] startNode = [8, 0, 0] targetNode = [4, 4, 0] nbSolution = 0 visited = [] search(startNode) print "Done. Find the best solution!"
|
MEMO |
|
Die Lösungen werden in das Ausgabefenster ausgeschrieben. Damit du unvoreingenommen an das Problem heran gehst und vielleicht versuchst, zuerst eine eigene Lösung mit Papier und Bleistift zu finden, werden sie hier nicht gezeigt. Immerhin sei verraten, dass es 16 Lösungen gibt und für den l längsten 16 Umgiessvorgänge nötig sind. |
AUFGABEN |
|
ZUSATZSTOFF |
CITY-NAVIGATION MIT MAUSUNTERSTÜTZUNG |
In einem professionellen Programm spielt die Benutzeroberfläche eine zentrale Rolle. Dabei muss sich der Programmierer weniger von programmtechnischen Überlegungen leiten lassen, sondern sich vielmehr in die Situation des unvoreingenommenen Anwenders versetzen, der mit möglichst wenig Aufwand und mit natürlicher menschlicher Logik das Programm verwendet. Man spricht dabei auch vom Benutzerinterface, das heutzutage meist eine grafische Benutzeroberfläche mit Mausbedienung umfasst. Der Aufwand für die Entwicklung des Benutzerinterfaces kann ein beträchtlicher Teil des Gesamtaufwands eines Informatikprojekts ausmachen. Für Navigationssysteme werden immer mehr berührungsempfindliche Bildschirme (touch screens) verwendet, die sich aber bezüglich der Programmlogik wenig von einer Mausbedienung unterscheiden. Daher wirst du hier die City-Navigation auf Mausbedienung umstellen, so dass der Benutzer Start- und Zielort mit einem Mausklick auswählen kann. Vom Programm abgegebene Informationen werden einerseits in die Titelzeile und andererseits in die Statusbar geschrieben. Der Mausklick löst einen Event aus, der im Callback pressEvent() abgearbeitet wird. Diese registrierst du in makeGameGrid() mit dem benannten Parameter mousePressed. Dabei musst du berücksichtigen, dass sich das Programm in zwei unterschiedlichen Zuständen befinden kann, je nachdem ob der Benutzer als nächste Aktion die Startstation anklickt oder ob er dies bereits getan hat und als nächstes die Zielstation wählen muss. Für diese Zustandsumschaltung genügt eine boolesche Variable (ein Flag) isStart, die dann True ist, wenn als nächstes die Startstation zu wählen ist. Das Programm soll so aufgebaut sein, dass der Benutzer die Wegsuche mehrmals durchführen kann, ohne dass er das Programm neu starten muss. Das Programm muss daher programmintern wieder in einen wohldefinierten Anfangszustand zurückgesetzt werden. Man spricht von der Initialisierung, die am besten mit einer Funktion init() durchgeführt wird. Da bei Programmstart gewisse Initialisierungen automatisch durchgeführt werden, ist es keineswegs trivial, das laufende Programm durch eine eigene Funktion immer wieder in einen wohldefinierten Anfangszustand zurückzusetzen. Initialisierungsfehler sind darum weit verbreitete, gefährliche und schwierig aufzufindende Programmierfehler, da sich oft das Programm bei der Erprobung richtig und erst später im Einsatz falsch verhält.
from gamegrid import * neighbours = { 'Althaus':['Bellevue', 'Dom', 'Enge', 'Friedhof'], 'Bellevue':['Althaus', 'City', 'Dom'], 'City':['Bellevue', 'Dom', 'Friedhof'], 'Dom':['Althaus', 'Bellevue', 'City', 'Enge', 'Friedhof'], 'Enge':['Althaus', 'Dom'], 'Friedhof':['Althaus', 'City', 'Dom']} distances = { ('Althaus', 'Bellevue'):5, ('Althaus', 'Dom'):9, ('Althaus', 'Enge'):6, ('Althaus', 'Friedhof'):15, ('Bellevue', 'City'):3, ('Bellevue', 'Dom'):13, ('City', 'Dom'):4, ('City', 'Friedhof'):3, ('Dom', 'Enge'):2, ('Dom', 'Friedhof'):12} locations = { 'Althaus':Location(2, 0), 'Bellevue':Location(0, 1), 'City':Location(1, 3), 'Dom':Location(4, 2), 'Enge':Location(5, 0), 'Friedhof':Location(3, 4)} def getNeighbourDistance(station1, station2): if station1 < station2: return distances[(station1, station2)] return distances[(station2, station1)] def totalDistance(li): count = 0 for i in range(len(li) - 1): count += getNeighbourDistance(li[i], li[i + 1]) return count def drawGraph(): getBg().clear() getBg().setPaintColor(Color.blue) for station in locations: location = locations[station] getBg().fillCircle(toPoint(location), 10) startPoint = toPoint(location) getBg().drawText(station, startPoint) for s in neighbours[station]: drawConnection(station, s) if s < station: distance = distances[(s, station)] else: distance = distances[(station, s)] endPoint = toPoint(locations[s]) getBg().drawText(str(distance), getDividingPoint(startPoint, endPoint, 0.5)) refresh() def drawConnection(startStation, endStation): startPoint = toPoint(locations[startStation]) endPoint = toPoint(locations[endStation]) getBg().drawLine(startPoint, endPoint) def search(station): global trackToTarget, trackLength visited.append(station) # station marked as visited # Check for solution if station == targetStation: currentDistance = totalDistance(visited) if currentDistance < trackLength: trackLength = currentDistance trackToTarget = visited[:] for s in neighbours[station]: if s not in visited: # if all are visited, recursion returns search(s) # recursive call visited.pop() # station may be visited by another path def getStation(location): for station in locations: if locations[station] == location: return station return None # station not found def init(): global visited, trackToTarget, trackLength visited = [] trackToTarget = [] trackLength = 1000 drawGraph() def pressEvent(e): global isStart, startStation, targetStation mouseLoc = toLocationInGrid(e.getX(), e.getY()) mouseStation = getStation(mouseLoc) if mouseStation == None: return if isStart: isStart = False init() setTitle("Click on destination station") startStation = mouseStation getBg().setPaintColor(Color.red) getBg().fillCircle(toPoint(mouseLoc), 10) else: isStart = True setTitle("Once again? Click on starting station.") targetStation = mouseStation getBg().setPaintColor(Color.green) getBg().fillCircle(toPoint(mouseLoc), 10) search(startStation) setStatusText("Shortest route from " + startStation + " to " + targetStation + ": " + str(trackToTarget) + " Length = " + str(trackLength)) for i in range(len(trackToTarget) - 1): s1 = trackToTarget[i] s2 = trackToTarget[i + 1] getBg().setPaintColor(Color.black) getBg().setLineWidth(3) drawConnection(s1, s2) getBg().setLineWidth(1) refresh() isStart = True makeGameGrid(7, 5, 100, None, "sprites/city.png", False, mousePressed = pressEvent) setTitle("City Guide. Click on starting station.") addStatusBar(30) show() init()
|
MEMO |
|
Der algorithmische Teil mit dem Backtracking bleibt praktisch unverändert. Das Benutzerinterface mit der Maussteuerung ist trotz guter Unterstützung durch Callbacks ziemlich aufwendig. Die Verwendung von global führt in Python leicht zu Initialisierungsfehlern, da globale Variablen in Funktionen erzeugt werden können und man später vergisst, ihren Wert zurückzusetzen. |
ROUTING-ALGORITHMUS VON DIJKSTRA |
|
Bereits 1959 veröffentlichte der berühmte niederländische Informatiker Edsger W. Disjkstra in einem dreiseitigen Artikel einen Algorithmus, um in einem Graphen sehr effizient und elegant den kürzesten Weg von einem Anfangsknoten A zu einem Endknoten B zu finden. Die Strategie ist es, nicht einfach alle möglichen Wege von A zu B zu suchen und davon den kürzesten zu bestimmen, sondern gezielt zu versuchen, von A nach B zu gelangen, indem man Wege absucht, die von einem bestimmten Knoten zu demjenigen weiterführen, der am nächsten liegt. (Einen solchen Algorithmus nennt man auch "gierig" (engl. greedy), da man bereits während der Ausführung noch einer optimalen Lösung sucht.) Am einfachsten lässt sich der Algorithmus am bereits oben verwendeten Beispiel der Bahnstationen erläutern. Die Stationen haben wie oben einen Namen und eine Position und das Bahnnetz wird durch die direkten Verbindungen und ihre Distanzen beschrieben, d.h. jede Station hat eine Anzahl von Nachbarstationen mit bekannten Verbindungsdistanzen. Diese Angaben verändern sich während des Programmablaufs nicht. Für den Routing-Algorithmus von Dijkstra benötigt jede Station drei Statusinformationen, die während des Programmablaufs angepasst werden.
Zu Beginn sind alle Stationen temporär, die aktuelle Distanz wir auf einen sehr grossen Wert gesetzt (z.B. 1000, eingetragen als oo (unendlich)) und der Name des Vorgängers ist leer. Dann fragt man nach dem Startstation und setzt dessen Distanz auf 0.
Nach Ende des Durchlaufs haben alle Stationen einen Vorgängerknoten (ausser eine Station ist gar nicht von der Startstation aus erreichbar). Den kürzesten Weg zu einer beliebig wählbaren Endstation findet man, indem man rückwärts von der Endstation die Vorgängerstationen durchläuft. In der Implementierung mit Python werden Nachbarn, Verbindungsdistanzen und Locations in Dictionaries neighbours, distances, locations gespeichert. Für den sich ändernden Stationszustand wird ebenfalls ein Dictionary stations mit dem Stationsnamen als Key definiert. Der Value ist eine Liste mit den Daten gemäss a,b,c, auf die man mit den Indizes 0, 1, 2 zugreifen kann. Zur Demonstration musst du nach Eingabe der Startstation eine beliebige Taste drücken, um den Algorithmus schrittweise auszuführen. Beobachte, wie die Werte der Stationen gemäss a, b, c laufend angepasst werden. Zuletzt wirst du nach einer Endstation gefragt und die kürzeste Route von der Startstation zur Endstation wird eingezeichnet und ausgeschrieben. Du nimmst es in Kauf, dass das Programm durch die grafische Ausgabe etwas aufwendiger wird. Dafür könnte das Programm mit wenig Mehraufwand bereits als professionelle Anwendung verwendet werden. from gpanel import * from sys import exit neighbours = { 'Althaus':('Bellevue', 'Dom', 'Enge', 'Friedhof'), 'Bellevue':('Althaus', 'City', 'Dom'), 'City':('Bellevue', 'Dom', 'Friedhof'), 'Dom':('Althaus', 'Bellevue', 'City', 'Enge', 'Friedhof'), 'Enge':('Althaus', 'Dom'), 'Friedhof':('Althaus', 'City', 'Dom')} distances = { # keys are ordered alphabetically ('Althaus', 'Bellevue'):5, ('Althaus', 'Dom'):3, ('Althaus', 'Enge'):6, ('Althaus', 'Friedhof'):15, ('Bellevue', 'City'):3, ('Bellevue', 'Dom'):13, ('City', 'Dom'):4, ('City', 'Friedhof'):3, ('Dom', 'Enge'):2, ('Dom', 'Friedhof'):12} locations = { 'Althaus':(5, 9), 'Bellevue':(1, 7), 'City':(3, 3), 'Dom':(9, 5), 'Enge':(11, 9), 'Friedhof':(7, 1)} stations = { # temporary or permanent, # distance to start station (1000 if infinite), # previous station (emtpy if not yet set) 'Althaus':['temporary', 1000, ''], 'Bellevue':['temporary', 1000, ''], 'City':['temporary', 1000, ''], 'Dom':['temporary', 1000, ''], 'Enge':['temporary', 1000, ''], 'Friedhof':['temporary', 1000, '']} def getNeighbourDistance(station1, station2): if station1 < station2: # compare alphabetically return distances[(station1, station2)] return distances[(station2, station1)] def drawGraph(): image("sprites/city.png", 0, 0) lineWidth(2) setColor("black") for station in locations: move(locations[station]) circle(0.4) # draw station as circle for neighbour in neighbours[station]: drawConnection(station, neighbour) # draw connecting lines # fill with color to indicate temporary or permanent for station in locations: if stations[station][0] == "temporary": setColor("yellow") elif stations[station][0] == "permanent": setColor("green") pt = locations[station] move(pt) fillCircle(0.38) # show station indentifier setColor("black") text(pt[0] - 0.15, pt[1] - 0.15, station) # show distance to start station and previous station dist = stations[station][1] dist = "oo" if dist == 1000 else str(dist) # 1000->infinite sign text(pt[0] - 0.5, pt[1] + 0.5, dist + "(" + stations[station][2] + ")") repaint() def drawConnection(start, end): ptStart = locations[start] ptEnd = locations[end] line(ptStart, ptEnd) distance = getNeighbourDistance(start, end) text(getDividingPoint(ptStart, ptEnd, 0.5), str(distance)) def getTemporaryNeighbours(station): li = [] for n in neighbours[station]: if stations[n][0] == "temporary": li.append(n) return li def getNearestTemporaryStation(): minstation = None min = 1000 for n in stations: if stations[n][0] == "temporary" and stations[n][1] <= min: min = stations[n][1] minstation = n return minstation def updateStations(station): stations[station][0] = "permanent" # make station permanent currentDist = stations[station][1] for n in getTemporaryNeighbours(station): newDist = currentDist + getNeighbourDistance(station, n) dist = stations[n][1] if newDist < dist: stations[n][1] = newDist stations[n][2]= station makeGPanel(Size(700, 500)) enableRepaint(False) window(0, 14, 0, 10) title("Shortest Path (Dijkstra Algorithm)") font(Font("Arial", Font.PLAIN, 20)) addStatusBar(30) drawGraph() startStation = "" setStatusText("Select start station") while not startStation in locations: startStation = inputString("Start station", False) if startStation == None: dispose() exit() stations[startStation][1] = 0 drawGraph() steps = 0 setStatusText("Press any key to step through algorithm...") # Perform Dijkstra algorithm while True: if getKeyWait(): currentStation = getNearestTemporaryStation() if currentStation == None: break updateStations(currentStation) drawGraph() steps += 1 setStatusText("Step #" + str(steps) + " - continue...") setStatusText("Algorithm finished.") targetStation = "" while not targetStation in locations: targetStation = inputString("Target station", False) if targetStation == None: dispose() exit() # Build track station = targetStation path = [station] while station != startStation: station = stations[station][2] path.append(station) track = path[::-1] # reverse lineWidth(4) setColor("red") trackLength = 0 for i in range(len(path) - 1): n1 = track[i] n2 = track[i + 1] trackLength += getNeighbourDistance(n1, n2) line(locations[n1], locations[n2]) setStatusText("Shortest route from " + startStation + " to " + targetStation + ": " + str(track) + " Length = " + str(trackLength)) repaint() |
AUFGABEN |
|
