gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:09:07 24 4
gpt4 key购买 nike

我的 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 删除启发式解决了这个问题。这表明问题出在我的启发式上。谁知道可能是什么原因造成的?

最佳答案

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

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

  • 如果您的启发式算法低于实际成本,则最短路径会被发现。

  • 如果启发式等于实际成本,则所有最短路径都是本质上是预先计算的,并且会找到最短路径没有任何不必要的探索。

  • 如果启发式有时大于实际成本,则 A*不保证找到最短路径,但搜索时间可能比启发式低估要快。

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

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

关于python - 为什么我的 a* 算法不走最短路线?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35802241/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com