Das deutsche Python-Forum

Code: Alles auswählen

def useAstar(self, start, goal):
        self.path = []
        currList = (start.HCost,0,Edge(None,start,0))
        self.openList = [currList]
        self.openHash = {}
        self.openHash[id(start)] = currList
        print self.openList
        self.closedList ={}
        print self.closedList
        while self.openList != []:
            currList = heappop(self.openList)
            nodeID = id(currList[2].terminalNode)
            if nodeID in self.closedList:
                continue
            self.closedList[nodeID] = currList
            del self.openHash[nodeID]
            if currList[2].terminalNode is goal:
                self.internalAstar_reconstructPath(start, goal)
                return self.path
            for edge in currList[2].terminalNode.outgoingEdges:
                self.internalAstar_checkEdge(edge, currList, goal)
            
    def internalAstar_reconstructPath(self,start,goal):
        print "found goal"
        node = goal
        while node != None:
            self.path.append(node)
            list = self.closedList[id(node)]
            node = list[2].initialNode
        self.path.reverse()
        return self.path

    def internalAstar_checkEdge(self, edge, currList, goal):
        nodeID = id(edge.terminalNode)
        if nodeID in self.closedList:
            closed = self.closedList[nodeID]
            if edge.weight + currList[1] < closed[1]:
                del self.closedList[nodeID]
                edge.terminalNode.checkInheritedHCost(edge)
                self.internalAstar_insert(edge, currList, nodeID)
            return
        if nodeID in self.openHash:
            opened = self.openHash[nodeID]
            if edge.weight + currList[1] < opened[1]:
                self.internalAstar_insert(edge, currList, nodeID)
            return
        edge.terminalNode.computeHCost(goal, edge)
        self.internalAstar_insert(edge, currList, nodeID)

    def internalAstar_insert(self, edge, currList, nodeID):
        gcost = currList[1]+edge.weight
        currList = (gcost+edge.terminalNode.HCost, gcost, edge)
        heappush(self.openList, currList)
        self.openHash[nodeID] = currList

Code: Alles auswählen

name = data['ways'][data['routes'][node][result[index+1]]['wayid']]['tags'].get('n', 'No name')

Code: Alles auswählen

         129489 function calls in 1.533 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.533    1.533 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 Edge2.py:2(__init__)
    39999    0.088    0.000    0.088    0.000 Node2.py:8(heurFunc)
        1    0.000    0.000    0.000    0.000 Search7.py:5(__init__)
        1    1.127    1.127    1.514    1.514 Search7.py:8(useAstar)
        1    0.019    0.019    1.533    1.533 astar2test.py:43(lol)
    44642    0.190    0.000    0.190    0.000 {_heapq.heappop}
    44641    0.109    0.000    0.109    0.000 {_heapq.heappush}
      200    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}

Code: Alles auswählen

         934205 function calls (934091 primitive calls) in 6.328 CPU seconds

Code: Alles auswählen

from Edge2 import Edge
from heapq import heappush, heappop

class Search():
    def __init__(self):
        pass
    
    def useAstar(self, start, goal):
        nID = start.id  # precomputed ids are faster
        openHeap = [(0, 0, nID)]
        masterDict = {nID:(0, 0, Edge(None, start, 0))} # using ID's instead
        while openHeap != []:                       # edges as key is faster
            o = heappop(openHeap)
            currID = o[2]
            curr = masterDict[currID]
            if o[0] > curr[0]:  # *can* be faster, if the same open nodes occurs
                continue    # then his children tests will be skipped... remove?
            if curr[2].terminalNode is goal:
                #reconstruct path
                path = []
                n = goal
                while n is not None:
                    path.append(n)
                    n = masterDict[n.id][2].initialNode
                path.reverse()
                return path
            # add children to openHeap
            for edge in curr[2].terminalNode.outgoingEdges:
                g = curr[0]-curr[1]+edge.weight # f-h+w
                nID = edge.terminalNode.id
                if nID in masterDict:
                    openItem = masterDict[nID]
                    if g >= openItem[0]-openItem[1]:
                        continue
                    h = openItem[1]
                else:
                    h = edge.terminalNode.heurFunc(goal)
                f = g+h
                masterDict[nID] = (f, h, edge)
                heappush(openHeap, (f, h, nID)) # pushing ids instead of edges
        return []                           # into the heap makes heappop faster

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 []