在 A 星中回溯 [英] Backtracking in A star

问题描述

蓝墙

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

Green highlighted cells = open list

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

Red Highlighted cells = closed list

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

Hello, can anyone tell me how can i implement backtracking in a a star search algorithm? I've implemented the a star search according to wiki, but it does not backtrack, what i mean by backtrack is that the open list(green cells) contains 2,0 and 3,3 as shown in the picture, upon reaching 2,0 the current node would "jump" to 3,3 since the cost is now more than 3,3 and continue the search from there, how can it be done so that it would backtrack from 2,0->2,1->2,2... all the way back to 3,3 and start the search from there?

推荐答案

你的图像就像二维网格图

但是您的文字建议使用 graph 方法，这有点令人困惑.

But your text suggest graph approach which is a bit confusing.

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

您在那里获得了过多的 cost=100，因此您无法回溯路径.您必须增加或减少每个步骤的成本，并仅填充靠近最后填充单元格的单元格.这可以通过在大地图上递归或通过扫描整个地图或小地图上最后填充数字的边界框来完成.

You got too much of cost=100 in there and therefore you can not backtrack the path. You have to increase or decrease cost on each step and fill only cells that are near last filled cells. That can be done by recursion on big maps or by scanning whole map or bounding box for last filled number on small maps.

• 在此处查找我的 C++ A* 实现

回溯

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

Can be done by scanning neighbors of start/end cells after A* filling moving always to the smallest/biggest cost

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

In this example start filling from (2,0) until (3,3) is hit and then backtrack from (3,2) cost=8 to the smallest cost (always cost-1 for incremental filling). If you need the path in reverse order then start filling from (3,3) instead ...

加速

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

Sometimes double filling speed up the process so: Start filling from both ends and stop when they join. To recognize which cell is filled from which point you can use positive and negative values, or some big enough ranges for costs.

这篇关于在 A 星中回溯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！