c++ - 了解 FRINGE 搜索伪代码

Question

我无法解释 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)

伪代码取自这篇维基文章:https://en.wikipedia.org/wiki/Fringe_search

我不明白那个语法在说什么。感谢您的帮助!

Answer 1

稍微检查一下代码会发现 C 条目包含 (g, link_to_parent)。在哪里

• 'g' 是该节点处 g(x) 的值。 g(x) 是成本从第一个节点到当前节点的搜索路径

• “link_to_parent”可以让您回到父级。一个
  可能是指针或索引值，甚至可能是
  的名称 parent 。它是什么完全取决于您的实现。
  伪代码使用“null”表示没有父级。

所以第 3 行表示到达起始节点无需花费任何费用，并且它没有父节点。

C本身就是node到pair(g,parent_link)的映射。

C(缓存)的实现方式由您决定，但您需要保留 C 的索引与节点同义且该节点的内容为 (g, way_to_indicate_parent) 的逻辑。