Python，查看并加速A *算法 [英] Python, review and speed up A* algorithm

问题描述

我实现了A *算法，以查找网格世界中两点之间的最短路径.对于较大的路径长度，该算法将花费很长时间.我首先想知道我的实现是否正确，是否可以进行任何优化?

I have implemented an A* algorithm to find the shortest path between two points in a grid world. For large path lengths the algorithm takes a very long time. I was first wondering if my implementation is correct, and if any optimization could take place?

aStar算法的参数是您的当前位置以及您希望作为(x,y)元组行进的位置.

The arguments for the aStar algorithm, are the current position of you and the position you desire to travel to as (x,y) tuples.

节点的Node.value是行进方向(NSEW)，getAdjacentNodes()返回与我们可以行进到的节点直接相邻的节点列表.

The Node.value of a node is a direction to travel (NSEW), getAdjacentNodes() returns a list of nodes directly adjacent to this one that we can travel to.

#Perform an A* search to find the best path to the dirt
  def aStar(self, current, end):
    openSet = set()   #Set of explorable nodes
    openHeap = []     #All paths heap, lowest cost on top
    closedSet = set() #Best path so far
    curNode = Node(0, current, self.manHatDist(current, end))
    openSet.add(curNode)
    openHeap.append((curNode.cost,curNode))
    while openSet:
      curNode = heapq.heappop(openHeap)[1]
      if curNode.pos == end:
          return self.getDirections(curNode)
      openSet.remove(curNode)
      closedSet.add(curNode)
      for tile in self.getAdjacentNodes(curNode.pos):
         if tile not in closedSet:
             tile.parent = curNode
             tile.cost = self.manHatDist(curNode.pos, end) + self.euclidDist(curNode.pos, current) + curNode.cost
             if tile not in openSet:
                 openSet.add(tile)
                 heapq.heappush(openHeap, (tile.cost,tile))
    return []

  #Get the moves made to get to this endNode
  def getDirections(self, endNode):
    moves = []
    tmpNode = endNode
    while tmpNode.parent is not None:
      moves.append(tmpNode.value)
      tmpNode = tmpNode.parent
    moves.reverse()
    return moves

节点类

# Node class for A* search
class Node:
  def __init__(self, value, pos, cost):
    self.pos = pos
    self.cost = cost
    self.value = value
    self.parent = None

  def __lt__(a, b):
    if(a.cost < b.cost):
      return 1
    return 0

  def __gt__(a, b):
    if(a.cost > b.cost):
      return 1
    return 0

编辑-这是getAdjacentNodes方法

  #Return all possible moves from given tile as Node objects
  def getAdjacentNodes(self, curPos):
    allMoves = ['North','South','East','West']
    posMoves = []
    for direction in allMoves:
      if(self.canMove(direction, curPos)):
        posMoves.append(Node(direction, self.getLocIfMove(curPos, direction), 0))
    return posMoves

EDIT2-分析结果

EDIT2 - Profiling result

配置文件结果粘贴链接

推荐答案

在我看来，这是错误的:

This looks wrong to me:

for tile in self.getAdjacentNodes(curNode.pos):
    if tile not in closedSet:
        tile.parent = curNode
        tile.cost = self.manHatDist(curNode.pos, end) + self.euclidDist(curNode.pos, current) + curNode.cost
        if tile not in openSet:
            openSet.add(tile)
            heapq.heappush(openHeap, (tile.cost,tile))

第一个问题.新图块的成本计算如下:

First problem. The computation of the cost of the new tile is:

self.manHatDist(curNode.pos, end) + self.euclidDist(curNode.pos, current) + curNode.cost

但应该是:

curNode.cost
- self.manHatDist(curNode.pos, end)
+ self.euclidDist(curNode.pos, tile.pos)
+ self.manHatDist(tile.pos, end)

(如果您比较聪明地表示搜索节点的方式，可以避免在计算新图块的成本时将其减去，但我会留给您.)

(You could avoid the subtraction in the computation of the cost of the new tile if you were cleverer about the way you represent the search nodes, but I will leave that to you.)

第二个问题.发现tile不在closedSet中之后，您立即假定到达tile的最佳方法是通过curNode.但是tile是否已经在openSet中?如果是这样，可能还有另一条到达tile的路线，比通过curNode的路线要好.*因此，这段代码应显示为:

Second problem. Having discovered that tile is not in closedSet, you immediately assume that the best way to get to tile is via curNode. But isn't it possible that tile is already in openSet? If so, there might be another route to tile that's better than the one via curNode.* So this code ought to read:

for tile in self.getAdjacentNodes(curNode.pos):
    if tile not in closedSet:
        cost = (curNode.cost
                - self.manHatDist(curNode.pos, end)
                + self.euclidDist(curNode.pos, tile.pos)
                + self.manHatDist(tile.pos, end))
        if tile not in openSet or cost < tile.cost:
            tile.parent = curNode
            tile.cost = cost
            openSet.add(tile)
            heapq.heappush(openHeap, (cost,tile))

我不能说这是否可以解决您的性能问题.但这可能会带来更好的结果.

I can't say if this will solve your performance problems. But it might give better results.

*如果self.euclidDist(curNode.pos, tile.pos)始终为1，就不可能有更短的路径.但是，既然如此，为什么还要麻烦euclidDist方法呢?

* There couldn't be a shorter route if self.euclidDist(curNode.pos, tile.pos) is always 1. But if that's the case, why bother with the euclidDist method?

这篇关于Python，查看并加速A *算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！