0

キューから親ノードを取得し、アクセスされているかどうかを確認し、アクセスされていない場合は子を生成してキューにプッシュし、ループを繰り返して、キュー内のキューから次の親ノードを取得するコードがあります。 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]
4

1 に答える 1

0

さて、私の友人、ケースはクローズされています。DFS から BFS への変換フォームのどこかで、isGoalState 条件の while ループが完了した後に return ステートメントを省略しました。それは無駄に頭を悩ませることでした。

于 2012-10-14T23:14:34.950 に答える