A星回溯
Backtracking in A star
蓝墙
绿色突出显示的单元格 = 打开列表
红色突出显示的单元格 = 关闭列表
你好，谁能告诉我如何在星搜索算法中实现回溯？
我已经根据 wiki 实现了星号搜索，但它没有回溯，回溯的意思是打开列表（绿色单元格）包含 2,0 和 3,3，如图所示，达到 2 时， 0 当前节点将 "jump" 到 3,3 因为成本现在超过 3,3 并从那里继续搜索，如何才能完成以便从 2,0->2,1 回溯->2,2...一直回到 3,3 并从那里开始搜索？
您可以从两个节点跟随后向指针，直到到达共同祖先 (0,2)，然后打印从 (2,0) 跟随时访问的节点，然后打印从 (2,0) 跟随时访问的节点(3,3)，反向印刷。
要在A*搜索树中找到两个节点的共同祖先，只需维护这两个"current nodes"，并跟随g-cost较高者的backpointer，直到两个当前节点在同一个地方。
值得一提的是，这是一件很奇怪的事情。 A*不是基于栈的遍历，所以不会回溯。
你的图片像二维网格图
但是您的文字建议使用 graph 方法，这有点令人困惑。
- 对于二维网格地图，路径上单元格之间的成本必须不同
你那里的 cost=100 太多了，因此你无法回溯路径。您必须增加或减少每一步的成本，并且只填充靠近最后填充的单元格的单元格。这可以通过在大地图上递归或在小地图上扫描整个地图或边界框以查找最后填充的数字来完成。
- 看这里找我的C++ A* implementation
回溯
可以通过在 A* 填充后始终移动到 smallest/biggest 成本
后扫描 start/end 单元格的邻居来完成
在这个例子中，从 (2,0) 开始填充，直到 (3,3) 被击中，然后 backtrack 从 (3,2) cost=8 到最小成本（增量填充总是 cost-1）。如果您需要相反顺序的路径，则从 (3,3) 开始填充而不是 ...
加速
有时双重填充会加快这个过程：从两端开始填充，并在它们加入时停止。要识别从哪个点填充了哪个单元格，您可以使用正值和负值，或者一些足够大的成本范围。
蓝墙
绿色突出显示的单元格 = 打开列表
红色突出显示的单元格 = 关闭列表
你好，谁能告诉我如何在星搜索算法中实现回溯？ 我已经根据 wiki 实现了星号搜索，但它没有回溯，回溯的意思是打开列表（绿色单元格）包含 2,0 和 3,3，如图所示，达到 2 时， 0 当前节点将 "jump" 到 3,3 因为成本现在超过 3,3 并从那里继续搜索，如何才能完成以便从 2,0->2,1 回溯->2,2...一直回到 3,3 并从那里开始搜索？
您可以从两个节点跟随后向指针，直到到达共同祖先 (0,2)，然后打印从 (2,0) 跟随时访问的节点，然后打印从 (2,0) 跟随时访问的节点(3,3)，反向印刷。
要在A*搜索树中找到两个节点的共同祖先，只需维护这两个"current nodes"，并跟随g-cost较高者的backpointer，直到两个当前节点在同一个地方。
值得一提的是，这是一件很奇怪的事情。 A*不是基于栈的遍历，所以不会回溯。
你的图片像二维网格图
但是您的文字建议使用 graph 方法，这有点令人困惑。
- 对于二维网格地图，路径上单元格之间的成本必须不同
你那里的 cost=100 太多了，因此你无法回溯路径。您必须增加或减少每一步的成本，并且只填充靠近最后填充的单元格的单元格。这可以通过在大地图上递归或在小地图上扫描整个地图或边界框以查找最后填充的数字来完成。
- 看这里找我的C++ A* implementation
回溯
可以通过在 A* 填充后始终移动到 smallest/biggest 成本
后扫描 start/end 单元格的邻居来完成在这个例子中，从 (2,0) 开始填充，直到 (3,3) 被击中，然后 backtrack 从 (3,2) cost=8 到最小成本（增量填充总是 cost-1）。如果您需要相反顺序的路径，则从 (3,3) 开始填充而不是 ...
加速
有时双重填充会加快这个过程：从两端开始填充，并在它们加入时停止。要识别从哪个点填充了哪个单元格，您可以使用正值和负值，或者一些足够大的成本范围。