我的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
谢谢你的帮助！随时请我澄清任何事情 .
编辑：通过返回0删除启发式解决此问题 . 这表明问题在于我的启发式 . 有谁知道可能导致它的原因？
1 回答
A *并不总能保证找到最短路径 . 虽然没有启发式（h（n）= 0）确实会找到最短路径（它变成Dijkstra算法），但这并不意味着任何启发式路径都会找到最短路径 . 添加启发式以加速此搜索，权衡是在某些情况下您将找不到最短路径 .
要了解最新情况，请记住启发式是对目标的实际距离的估计 . 如果预测是完美的，则图基本上是预先计算的 . 考虑以下情况 .
如果您的启发式算法低于实际成本，则会找到最短路径 .
如果启发式等于实际成本，则所有最短路径基本上都是预先计算的，并且可以找到最短路径而无需任何不必要的探索 .
如果启发式有时大于实际成本，则A *不能保证找到最短路径，但搜索时间可能比启发式低估时更快 .
你的启发式似乎低估了成本 . 也可能是你有错误的邻居生成或成本计算器 .
进一步阅读：http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html