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

Question

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

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

http://imgur.com/GBoq9py

这是我的 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