Seite 1 von 1
Verfasst: Mittwoch 28. Januar 2009, 08:25
von BlackJack
@meh11: Und noch ein bisschen Kritik: `masterDict` ist ein schlechter Name. Der sagt nichts darüber aus, *was* da drin gespeichert wird. So etwas wie `open_nodes` oder `known_nodes` wäre da besser. `openHeap` würde ich auch umbenennen, damit der Name der Datenstruktur aus dem Namen verschwindet.
Da Tupel nicht so "selbstbeschreibend" sind, wäre ein Kommantar was in `openHeap` und `masterDict` eigentlich gespeichert wird, ganz nett.
Die ``while``-Schleife ist vielleicht einen Tick schneller wenn Du einfach ``while openHeap:`` schreibst.
Auf Abkürzungen sollte man verzichten. Betrifft zum Beispiel `o` und `curr`. Von letzterem werden im weiteren Verlauf anscheinend alle Elemente verwendet, da könnte man auch alle an Namen binden und das Programm damit verständlicher machen.
Verfasst: Mittwoch 28. Januar 2009, 09:49
von meh11
Habs masterDict genannt, weil in Game Programming Gems 1 etwas von einer masterNodeList oder so stand... Aber knownNodes hört sich gut an, ich benenne den Kram mal um und ändere die Kommentare.
Zur while Schleife:
Bei 9000 Aufrufen auf einem 6*5 Feld war deine Version schneller. Wenn ich das richtig interpretiere dann wird durch mein != [] bei jedem Aufruf von useAstar() ein unnötiges leeres Array erzeugt, richtig?
Verfasst: Mittwoch 28. Januar 2009, 10:35
von cofi
Da du dich gegen die pythonische Bennenung sträubst, lies doch mal [wiki]PEP 8 (Übersetzung)[/wiki]
oder das Orginal
http://www.python.org/dev/peps/pep-0008/
Verfasst: Mittwoch 28. Januar 2009, 11:48
von meh11
Tatsächlich habe ich schonmal Guido Rossums Style Guide gelesen, aber es ist vermutlich keine schlechte Idee das ganze mal aufzufrischen.
Ich hoffe das hier ist besser:
Code: Alles auswählen
from Edge2 import Edge
from heapq import heappush, heappop
def useAStar(start, goal):
""" A*: -Uses a Hash knownNodes for fast access to edges with smallest
cost to their nodes
-knownNodes is used as closed list and provides fast access to
opened nodes, using nodes' ids as key
-Uses a Heap openNodes as fast priority queue
-openNodes is sorted by F and H
-openNodes is slow when edges are inserted, so instead it
makes use of the nodes' ids and knownNodes to retain edges
-Nodes' ids are precomputed for sake of speed
"""
nID = start.id
openNodes = [(0, 0, nID)] # heap holds (f, h, terminalNode's id)
knownNodes = {nID:(0, 0, Edge(None, start, 0))} # hash holds (f, h, edge)
while openNodes:
popped = heappop(openNodes)
openID = popped[2]
openF, openH, openEdge = knownNodes[openID]
if popped[0] > openF: # *can* be faster, if the same open nodes occurs
continue # then his children tests will be skipped... remove?
# if goal found -> reconstruct path
if openEdge.terminalNode is goal:
path = []
n = goal
while n is not None:
path.append(n)
n = knownNodes[n.id][2].initialNode
path.reverse()
return path
# add children to openHeap
for edge in openEdge.terminalNode.outgoingEdges:
g = openF - openH + edge.weight
nID = edge.terminalNode.id
if nID in knownNodes:
knownItem = knownNodes[nID]
if g >= knownItem[0] - knownItem[1]:
continue
h = knownItem[1]
else:
h = edge.terminalNode.heurFunc(goal)
f = g + h
knownNodes[nID] = (f, h, edge)
heappush(openNodes, (f, h, nID))
return []
Weitere Ideen wie mans schneller bekommt oder Erklärungen warum meins langsamer ist als andere Implemenationen sind willkommen.
Verfasst: Sonntag 15. März 2009, 12:11
von meh11
Okay, eine Kleinigkeit ist mir eingefallen: Wenn ich vom Ziel zum Start hin suche, dann spar ich mir das path.reverse() beim Rekonstruieren des Weges.