2

私の本には、幅優先検索用の次の疑似コードがあります。

function breadth_first_search:
    begin
        open := [Start]
        closed := [];
        while open != [] do
            begin
                remove leftmost state from open, call it X;
                    if X is a goal then return SUCCESS
                        else begin
                            generate children of X;
                            put X on closed;
                            discard children of X if already on open or closed;
                            put remaining children on right end of open;
                        end
            end
       return FAIL;
    end

これらの疑似コードの指示に従って、同様のアルゴリズムを自分で実装しました。私の質問は、ソリューション パスを維持するように変更する最も簡単な方法は何ですか?

解決策にたどり着くことができるということを単純に知ることは、解決策にたどり着くまでの遷移のリストを持つことほど役に立ちません。

4

2 に答える 2

6

Parent[childNode] = currentNode各ノードをキューに入れるときに設定します ( を設定した場合) Visible[Node] = 1。

次に、必要なノードから開始して配列を再帰的に検索し、配列に表示されるParent各ノードをParentパスに追加します。Parent[root]でnilあり、再帰はそこで停止します。

于 2009-10-13T19:59:15.750 に答える
3

ツリー構造を変更する可能性はありますか? その場合は、各ノード/リーフにポインターを追加してparent、解決策を見つけたら、親ポインターをルートまでたどります。

于 2009-10-13T20:01:47.310 に答える