了解 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。 A
可能是指针或索引值，甚至可能是
的名称 parent。它是什么完全取决于您的实施。
pseudo-code 正在使用 'null' 表示没有 parent。

所以第 3 行是说到达起始节点不需要任何费用，而且它没有 parent。

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

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

了解 FRINGE 搜索伪代码

Understanding FRINGE Search pseudocode

c++

graph-algorithm

pseudocode

path-finding