c# - 深度优先搜索确实找到了传教士和食人者问题的解决方案状态

Question

我正在使用 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;
        }

Answer 1

看到你的代码很难说出答案。然而，根据我的经验:DFS 搜索并不能提供完整的解决方案。您的代码很可能陷入某种无限循环(这在 dfs 中很常见)或者(因为您正在检查 isVisited)，您有可能没有达到最终目标。