キューから親ノードを取得し、アクセスされているかどうかを確認し、アクセスされていない場合は子を生成してキューにプッシュし、ループを繰り返して、キュー内のキューから次の親ノードを取得するコードがあります。 FIFOファッション。残念ながら、目標の状態に到達していないようです。BFSの実装方法に構造的に問題がありますか?DFS検索を作成するために、キューの代わりにスタックを使用して、これとまったく同じコードで目的の出力を取得しました。「q」をキュー(FIFO)データ構造に変更することは、文字通り、このコードに加えた唯一の変更です。追加する必要があるものは他にありますか?親/子はタプルとして保存されるため、その作業はすべて無視してかまいません。問題が発生している場所ではないようです。また、isGoalStateがTrueに評価される前にプログラムが中断するため、コードは tも問題に貢献しているようです。isGoalStateは、特定の状態の座標がBFSが見つける必要のある「目標」と一致するかどうかをテストします。getSuccessorsは、タプルのリストを返します。各タプルは、ノードの子を表します。
while q:
parent = q.pop()
print "parent: " + str(parent)
print str(q)
if parent[0] in visited: continue
visited.append(parent[0])
if problem.isGoalState(parent[0]):
pathList.append(parent[0])
while actionMap[parent] is not None:
actionList.append(actionMap[parent])
try:
pathList.append(parentMap[parent])
except KeyError:
break
parent = parentMap.get(parent, None)
actionList.reverse()
children = problem.getSuccessors(parent[0])
if children != []:
for child in children:
q.push(child)
parentMap[child] = parent
actionMap[child] = child[1]