我在解释FRINGE搜索算法的伪代码中的一行时遇到麻烦。在下面的代码行是#3:
init(start, goal)
fringe F = s
cache C[start] = (0, null)
flimit = h(start)
found = false
while (found == false) AND (F not empty)
fmin = ∞
for node in F, from left to right
(g, parent) = C[node]
f = g + h(node)
if f > flimit
fmin = min(f, fmin)
continue
if node == goal
found = true
break
for child in children(node), from right to left
g_child = g + cost(node, child)
if C[child] != null
(g_cached, parent) = C[child]
if g_child >= g_cached
continue
if child in F
remove child from F
insert child in F past node
C[child] = (g_child, node)
remove node from F
flimit = fmin
if reachedgoal == true
reverse_path(goal)
伪代码来自以下Wiki文章:https://en.wikipedia.org/wiki/Fringe_search
我不知道该语法在说什么。谢谢你的帮助!
最佳答案
仔细检查一下代码,发现C条目包含(g,link_to_parent)。哪里
从第一个节点到当前
指针或索引值,甚至可能是名称
parent 究竟是什么取决于您的实现。的
伪代码使用“null”表示没有父对象。
因此,第3行表示起始节点不花任何成本,也没有父节点。
C本身是节点到该对(g,parent_link)的映射。
如何实现C(缓存)取决于您,但是您需要保留逻辑,即C的索引与节点同义,并且该节点处的内容为(g,way_to_indicate_parent)。
关于c++ - 了解FRINGE搜索伪代码,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/37105067/