2

C# を使用して宣教師と人食い人種に関するプロジェクトを行っています。幅優先検索と深さ優先検索の 2 つの検索アルゴリズムを使用しました。幅優先検索を使用して、プログラムはルートからレベル 12 の結果を見つけます。しかし、深さ優先検索を使用すると、解決策が見つからず、コンピューターがハングします。グラフのサイクルに入ると思います。私の質問は、宣教師と人食い人種の問題を解決するために深さ優先検索を使用できないかということです。

幅優先探索のコードは

public State getSolutionStatesBFS(State StartState, State EndState) 
        {
            State CurState = new State();
            ArrayList visited = new ArrayList();
            addStateToAgenda(StartState, true);
            while (searchAgenda.Count > 0) {
                CurState = (State)searchAgenda.Dequeue();

              if (CurState.Equals(EndState)) {
                    break;
              } else {
                  if (!isVisited(CurState, visited))
                  {
                      generateSucessors(CurState, true);
                      visited.Add(CurState);
                  }
              }

            }
            return CurState;
        }

深さ優先検索のコードは次のとおりです。

public State getSolutionStatesDFS(State StartState, State EndState)
        {
            State CurState = new State();
            ArrayList visited = new ArrayList();
            addStateToAgenda(StartState, false);
            while (searchAgendaS.Count > 0)
            {
                CurState = (State)searchAgendaS.Pop();

                if (CurState.Equals(EndState))
                {
                    break;
                }
                else
                {
                    if(!isVisited(CurState,visited))
                    {
                        generateSucessors(CurState, false);
                    }
                }
            }
            return CurState;
        }
4

2 に答える 2

2

コードを見て答えを伝えるのは難しいです。ただし、私の経験によると、DFS 検索では完全な解決策は得られません。コードが何らかの無限ループ (dfs で一般的) に陥っている可能性が高いか、(isVisited をチェックしているため)、最終目標に到達していない可能性があります。

于 2013-02-10T23:01:05.397 に答える
1

だから私の質問は、宣教師と人食い人種の問題を解決するために深さ優先探索を使用できないかということです。

はい、それは間違いなく可能です。このサイトを見てください：http: //www.aiai.ed.ac.uk/~gwickler/missionaries.html

あなたの問題がどこにあるのか見分けるのが難しいコードが与えられています。

于 2012-08-01T13:19:20.770 に答える