1

我试图在具有特定起点和终点的迷宫中寻找最短路径，当在表格中的某些单元格中您无法通过时，迷宫被构建为 2D 表格（行和列）（“墙” )，到目前为止一切顺利，A* 算法运行良好，当特定单元格的“权重”比其他单元格更好时，问题就开始了。例如，采用 3*3 迷宫：

  • 起点1*1
  • 终点3*3
  • 1*3 的单元格比其他单元格的权重更好，这意味着如果最终你有相等的溃败，你最好通过这个单元格

因此，通过 A*，它甚至不会让 1*3 单元格了解它具有更好的权重！

这个问题有解决方案吗？

谢谢！

4

1 回答 1

4

创建代表您的迷宫的图形G=(V,E)。

为图中的边创建一个带有权重函数的新加权图：

w(u,v) = 1                if v is "not important"
         1-1/(n+1)        if v is important.
(n is the total number of vertices/cells in your maze).

现在，请注意，通过v的路径比不通过它的路径“更好”（更短），但仍然更短（在距离上）路径总是受到青睐。

您现在可以将 A* 与修改后的启发式函数一起使用：

h'(v) = h(v)*[1-1/(n+1)]  [where h(v) is the original admissible heuristic you had]

注意：忽略评论，如果你有一个可接受的启发式函数，Dijsktra 的算法不如 A*，而且看起来你有。

于 2014-02-16T13:24:57.147 回答