Appearance
EF Informatik 27
Aktuelles Thema
Probe am Mittwoch, 4. November
python
import math
class Node:
def __init__(self, name, h):
self.name = name
self.h = h
self.closed = False
def __repr__(self):
return self.name
class Graph:
def __init__(self):
self.nodes = []
self.edges = []
def addNode(self, name, h):
newNode = Node(name, h)
self.nodes.append(newNode)
return newNode
def createMatrix(self):
n = len(self.nodes)
for i in range(n):
self.edges.append([-1] * n)
def getEdge(self, node1, node2):
if node1 not in self.nodes:
return
if node2 not in self.nodes:
return
index1 = self.nodes.index(node1)
index2 = self.nodes.index(node2)
return self.edges[index1][index2]
def addEdge(self, node1, node2, cost):
if node1 not in self.nodes:
return
if node2 not in self.nodes:
return
index1 = self.nodes.index(node1)
index2 = self.nodes.index(node2)
self.edges[index1][index2] = cost
self.edges[index2][index1] = cost
# Sucht alle Nachbarknoten von node
def findNeighbours(self, node):
neighbours = []
for candidate in self.nodes:
if self.getEdge(node, candidate) != -1:
neighbours.append(candidate)
return neighbours
class ListEntry:
def __init__(self, node, cost, predecessor):
self.node = node
self.cost = cost
self.predecessor = predecessor
def __lt__(self, other):
return self.cost < other.cost
def __repr__(self):
return (
"("
+ str(self.node)
+ ", "
+ str(self.cost)
+ ", "
+ str(self.predecessor)
+ ")"
)
g = Graph()
A = g.addNode("Saarbrücken", 222)
C = g.addNode("Frankfurt", 96)
D = g.addNode("Ludwigshafen", 108)
E = g.addNode("Karlsruhe", 140)
B = g.addNode("Kaiserslautern", 158)
F = g.addNode("Heilbronn", 87)
Z = g.addNode("Würzburg", 0)
g.createMatrix()
g.addEdge(A, B, 70)
g.addEdge(B, C, 103)
g.addEdge(C, Z, 116)
g.addEdge(B, D, 53)
g.addEdge(D, Z, 183)
g.addEdge(A, E, 145)
g.addEdge(E, F, 84)
g.addEdge(F, Z, 102)
SIMPLE = 0
DIJKSTRA = 1
ASTAR = 2
# openList: Liste aller zu bearbeitenden Knoten: (Knoten, Kosten, Vorgänger)
def findPath(g, start, destination, algorithm):
openList = []
closedList = []
# Startknoten in Open List einfügen
if algorithm == ASTAR:
startCost = start.h
else:
startCost = 0
openList.append(ListEntry(start, startCost, None))
while True:
# Dijkstra und A*: Liste sortieren
if algorithm != SIMPLE:
openList.sort()
# Zwischenstand ausgeben
print("=======")
print(openList)
print("---")
print(closedList)
# erster Knoten aus Open List nehmen
current = openList.pop(0)
closedList.append(ListEntry(current.node, current.cost, current.predecessor))
current.node.closed = True
# Wenn der Zielknoten in die ClosedList kommt, ist der Algorithmus beendet
if current.node == destination:
return closedList
# alle Nachbarknoten von current suchen
neighbours = g.findNeighbours(current.node)
for neighbour in neighbours:
if not neighbour.closed:
# Kosten zum neighbour berechnen
cost = g.getEdge(current.node, neighbour)
# bisherige Kosten aus OpenList + Kosten zum Nachbarn
totalCost = current.cost + cost
ok = False
for item in openList:
# neighbour ist schon in OpenList
if item.node == neighbour:
# neue Kosten sind kleiner als bisherige
if totalCost < item.cost:
# neue Kosten und Vorgänger eintragen
item.cost = totalCost
item.predecessor = current.node
ok = True
if not ok:
openList.append(ListEntry(neighbour, totalCost, current.node))
path = findPath(g, A, Z, DIJKSTRA)
print(path)Noten und Bewertung GYM4
Programm GYM4