为什么我的a*算法不采用最短路径？

Question

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

在这张图片中,机器人必须穿过黑色方块,河流和树木都是障碍物.黑线是它所采用的路径,显然不是最短的路径,因为它不应该浸入.

http://imgur.com/GBoq9py

这是我的代码*和我正在使用的启发式:

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