Understanding FRINGE Search pseudocode

Question

I am having trouble interpreting one line in the pseudocode for the FRINGE search algorithm. The line is #3 in the following code:

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)

The pseudocode was taken from this wiki article: https://en.wikipedia.org/wiki/Fringe_search

I can't figure out what that syntax is saying. Thanks for any help!

Answer 1

A little examination of the code finds that a C entry contains (g, link_to_parent). Where

• 'g' is the value of g(x) at that node. g(x) is the cost of the search path from the first node to the current

• 'link_to_parent' is something that gets you back to the parent. A
  pointer perhaps or an index value or even perhaps the name of the
  parent. What it is exactly depends on your implementation. The
  pseudo-code is using 'null' to indicate no parent.

So line 3 is saying that the start node costs nothing to reach and it has no parent.

C itself is a mapping of node to the pair (g,parent_link).

How C (cache) is implemented is up to you but you need to retain the logic whereby the index of C is synonymous with node and the contents at that node are (g, way_to_indicate_parent).