为什么我的 a* 算法不走最短路线？

Question

我的 a* 算法并不总是采用最短路径。

在这张图中，机器人必须穿越到黑色方块，河流和树木是障碍物。黑线是它走过的路径，这显然不是最短路径，因为它不应该下降。

这是我的 a* 代码和我正在使用的启发式方法：

def HeuristicCostEstimate(start, goal):
    (x1, y1) = start
    (x2, y2) = goal
    return abs(x1 - x2) + abs(y1 - y2)

def AStar(grid, start, goal):
    entry = 1
    openSet = []
    heappush(openSet,(1, entry, start))
    cameFrom = {}
    currentCost = {}
    cameFrom[tuple(start)] = None
    currentCost[tuple(start)] = 0
    while not openSet == []:
        current = heappop(openSet)[2]
        print(current)
        if current == goal:
            break

        for next in grid.Neighbours(current):
            newCost = currentCost[tuple(current)] + grid.Cost(current, next)
            if tuple(next) not in currentCost or newCost < currentCost[tuple(next)]:
                currentCost[tuple(next)] = newCost
                priority = newCost + HeuristicCostEstimate(goal, next)
                entry +=1
                heappush(openSet,(priority, entry, next))
                cameFrom[tuple(next)] = current

    return cameFrom, current

http://pastebin.com/bEw8x0Lx

感谢您的帮助！并随时要求我澄清任何事情。

编辑：通过返回 0 删除试探法解决了这个问题。这表明问题出在我的启发式上。有人知道是什么原因造成的吗？

Answer 1

A* 并不总能保证找到最短路径。虽然没有启发式 (h(n) = 0) 确实会找到最短路径（它成为 Dijkstra 算法），但这并不意味着使用任何启发式都会找到最短路径。添加启发式以加快搜索速度，但代价是在某些情况下您找不到最短路径。

要了解发生了什么，请记住启发式是对目标实际距离的估计。如果预测是完美的，则该图基本上是预先计算好的。考虑以下情况。

如果你的启发式比实际成本低，最短路径会被发现。
如果启发式等于实际成本，则所有最短路径都是本质上是预先计算的，并且会找到最短路径没有任何不必要的探索。
如果启发式有时大于实际成本，那么A* 不保证找到最短路径，但搜索时间可能比启发式低估要快。

看来您的启发式算法低估了成本。也可能是您的邻居生成器或成本计算器有问题。

进一步阅读：http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Answer 2

将您的启发式更改为 (x1-x2)^2 + (y1-y2)^2，您应该会发现它会生成更准确的路径。

为什么我的 a* 算法不走最短路线？

Why doesn't my a* algorithm take the shortest route?

python

algorithm

a-star

shortest-path