我在解释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)。哪里

  • 'g'是该节点上g(x)的值。 g(x)是
    从第一个节点到当前
  • 的搜索路径
  • 'link_to_parent'是使您回到 parent 身边的东西。一种
    指针或索引值,甚至可能是名称
    parent 究竟是什么取决于您的实现。的
    伪代码使用“null”表示没有父对象。

  • 因此,第3行表示起始节点不花任何成本,也没有父节点。

    C本身是节点到该对(g,parent_link)的映射。

    如何实现C(缓存)取决于您,但是您需要保留逻辑,即C的索引与节点同义,并且该节点处的内容为(g,way_to_indicate_parent)。

    关于c++ - 了解FRINGE搜索伪代码,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/37105067/

    10-12 01:30
    查看更多