FRINGE検索擬似コードの理解

Question

FRINGE検索アルゴリズムの擬似コードで1行の解釈に問題があります。行は、次のコードでは第3位である：私はその構文が言っていることを把握することはできませんhttps://en.wikipedia.org/wiki/Fringe_search

：

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の記事から取りました。助けてくれてありがとう！

Answer 1

コードを少し調べると、Cエントリに（g、link_to_parent）が含まれていることがわかります。

• 'g'は、そのノードでのg（x）の値です。 g（x）は、最初のノードから現在のノードへの の検索パスのコストです。

• 'link_to_parent'はあなたを親に戻すものです。
  ポインタ、おそらくは
  親のインデックス値、あるいはおそらく名前。それは正確にあなたの実装に依存します。
  擬似コードでは、「null」を使用して親なしを示しています。

だから、3行目は、開始ノードに到達するコストはなく、親は存在しないと言っています。

C自体はノードのペア（g、parent_link）へのマッピングです。

C（キャッシュ）の実装方法はあなた次第ですが、Cのインデックスはnodeと同義であり、そのノードの内容は（g、way_to_indicate_parent）であるロジックを保持する必要があります。