深度第一搜索確實發現傳教士和食人族問題的解決狀態

Question

我正在使用C＃在傳教士和食人族上做我的項目。我使用了兩種搜索算法，即廣度優先搜索和深度優先搜索。使用廣度優先搜索，程序從根目錄找到第12級的結果。但使用深度首次搜索，它無法找到解決方案，這掛我的電腦。我認爲它在圖表中進入一個循環。所以我的問題是，我不能使用Depth首先搜索來解決傳教士和食人族的問題嗎？

代碼廣度優先搜索是

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），有可能你沒有達到最終目標。

Answer 2

所以我的問題是，我不能用深度優先搜索解決傳教士與食人族問題？

是的，這是deffinatly可能，看看這個網站： http://www.aiai.ed.ac.uk/~gwickler/missionaries.html

隨着給予其分不清哪裏您的問題是代碼。