algorithm - A星回溯

Question

蓝墙

绿色突出显示的单元格 = 打开列表

红色突出显示的单元格 = 关闭列表

你好，谁能告诉我如何在星搜索算法中实现回溯？我已经根据 wiki 实现了星号搜索，但它没有回溯，回溯的意思是打开列表(绿色单元格)包含 2,0 和 3,3，如图所示，达到 2 时， 0 当前节点将“跳转”到 3,3，因为成本现在超过 3,3 并从那里继续搜索，如何才能做到从 2,0->2,1-> 回溯2,2...一直回到 3,3 并从那里开始搜索？

Answer 1

你的图像就像二维网格 map

但是您的文字建议采用图形 方法，这有点令人困惑。

• 对于 2D 网格 map ，路径上单元格之间的成本必须不同

你那里的 cost=100 太多了，因此你无法回溯路径。您必须增加或减少每一步的成本，并且只填充靠近最后填充的单元格的单元格。这可以通过在大 map 上递归或在小 map 上扫描整个 map 或边界框以查找最后填充的数字来完成。

• 在这里寻找我的C++ A* implementation

回溯

可以通过在 A* 填充后始终移动到最小/最大成本后扫描开始/结束单元格的邻居来完成

在此示例中，从 (2,0) 开始填充，直到 (3,3) 被命中，然后从 回溯 (3,2) cost=8 到最小的成本(增量填充总是cost-1)。如果您需要相反顺序的路径，则从 (3,3) 开始填充而不是 ...

加速

有时双重填充会加快这个过程:从两端开始填充并在它们连接时停止。要识别从哪个点填充了哪个单元格，您可以使用正值和负值，或者一些足够大的成本范围。