2

我正在使用 C# 做关于传教士和食人族的项目。我使用了两种搜索算法，即广度优先搜索和深度优先搜索。使用广度优先搜索，程序从根开始查找第 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 回答