回溯中的一颗明星 [英] Backtracking in A star

问题描述

蓝墙

凸显绿色电池=打开清单

Green highlighted cells = open list

红色突出显示单元=收盘行情一览

Red Highlighted cells = closed list

您好，谁能告诉我怎样才能实现回溯在AA星级搜索算法？ 我根据维基实施的搜星，但它并没有走回头路，我的意思是原路返回，开放清单（绿色细胞），包括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?

推荐答案

你的形象就像是2D网格图

your image is like 2d grid map

• 但你的文字提示图的做法，是一个有点混乱。
• 作为2D网格地图的费用必须是在细胞通路之间的不同
• 您有太多的成本= 100 在那里，所以你不能原路返回的路径
• 您必须增加或每一步降低成本，只填写正在接近最后的填充细胞的细胞
• 可以通过递归在大地图来完成
• 或通过扫描整个地图或边框上的小地图最后充满号
• 在这里寻找矿 C ++ A *实现

• but your text suggest graph approach which is a bit confusing.
• for 2D grid map the costs must be different between cells on path
• 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
• Look here for mine C++ A* implementation

回溯

• 可以通过扫描开始/结束单元的邻居后，A *灌装完成
• 一直移动到最小/最大的成本
• 
• 在这个例子中，从开始（2,0）填充，直到（3,3）被击中
• 然后从原路返回（3,2）的成本为8到最小的成本（总成本1增量填充）
• 如果您需要以相反的顺序的路径，然后开始从填充（3,3），而不是...

加速

• 有时双重填充加快这一进程
• 开始从两端尽显
• 在停止时，他们加入
• 来识别哪些单元填充从哪个角度你可以使用正值和负值，或者一些足够大范围的成本

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