食人族和傳教士使用IDDFS和GreedyBFS

三個食人族和三個傳教士必須過河。他們的船隻能容納兩個人。如果食人族比傳教士人數多，傳教士就會陷入困境（我不會描述結果）。每個傳教士和每個食人族都可以划船。六個人怎麼能穿過這條河？食人族和傳教士使用IDDFS和GreedyBFS

我找不到使用IDDFS（迭代加深深度優先搜索）和GreedyBFS（貪心最佳優先搜索）解決此問題的算法。關於如何解決這個問題的想法也會讓我開心。

編輯：

我發現了一個算法IDDFS對維基：

IDDFS(root, goal) 
{ 
    depth = 0 
    repeat 
    { 
    result = DLS(root, goal, depth) 
    if (result is a solution) 
     return result 
    depth = depth + 1 
    } 
} 


DLS(node, goal, depth) 
{ 
    if (depth == 0 and node == goal) 
    return node 
    else if (depth > 0) 
    for each child in expand(node) 
     DLS(child, goal, depth-1) 
    else 
    return no-solution 
}

但我不能找出擴大（節點）DLS（）應該是在完成我的問題。這是我的節點類別：

public class Node{ 
    //x-no of missionaries 
    //y-no of cannibals 
    //z-position of boat 
    int x,y; 
    boolean z; 
    Node(int x,int y,boolean z){ 
     this.x=x; 
     this.y=y; 
     this.z=z; 
    } 
    public int getM(){ 
     return this.x; 
    } 
    public int getC(){ 
     return this.y; 
    } 
    public boolean getB(){ 
     return this.z; 
    } 
    public void setM(int x){ 
     this.x=x; 
    } 
    public void setC(int y){ 
     this.y=y; 
    } 
    public void setB(boolean z){ 
     this.z=z; 
    } 

}

我將不勝感激任何幫助。

來源

2012-03-24 user1217380

您是否在努力研究如何通過搜索來探索狀態空間，或者瞭解最佳路徑的標準應該是什麼？ – 2012-03-24 11:29:16

*「六個人怎麼能過河？」*如果你的意思是'活着或半消化'，那麼問題很簡單！ ;） – 2012-03-24 11:32:28

它通常不是搜索方法，而是您對問題的表示。這個問題中所有可能的行爲和狀態是什麼？另外請注意，人們可以登上河流的任何一邊，而不僅僅是他們開始的一側。 – 2012-03-24 11:33:29

如何解決它沒有算法？你的模型很小，可以在沒有任何編程的情況下解決，前兩個食人族去另一邊，然後他們中的一個用船背上另一個食人族到另一邊，現在有3個食人族在另一邊，其中一個背部和兩個傳教士去對方（現在2 c和2 m在另一邊）。在這個時間裏有一個c帶着一個m回來（2c和2m在第一位），再次2m到另一邊（另一邊3m用一個c），再次在另一邊的唯一c回來並且在另一側攜帶兩個c（另一側爲2c和3m），同樣一個c回來並且將最新的c移動到另一側。

如何用DFS等算法來模擬它？創建一個有向圖，有2^6個職位（{1,2,3,4,5,6}的所有可能的子集），如果你可以通過使用可用的移動從一個位置移動到另一個位置，它們是相互關聯的。一些節點是死的節點（導致一側產生更多食人族的節點），您將從您的圖中刪除這些節點，然後您的任務是檢查是否有方法從節點0 {}到節點63 {1,2 ，3,4,5,6}，這可以通過BFS，DFS等多種方式解決。

來源

2012-03-24 11:47:46

爲了使用您提到的算法，您需要弄清楚問題的狀態空間是什麼。 A 狀態是對問題情況（無論是開始情況，最終情況還是中間情況）的完整描述。訣竅是在一個狀態中包含足夠的信息，以便能夠確定狀態是否是問題的解決方案，如果不是，則接下來要做什麼。在你的情況下，表示狀態的一種可能的方式是使用三個變量：整數m表示有多少傳教士在河的起點，整數c表示有多少食人族在起跑線上，並且布爾型號b告訴船在哪一側。給定（m，c，b）的值，您可以確定您可以採取哪些可能的操作，以及可以採取哪些其他狀態。你提到的算法實際上是用於搜索這樣一組連接狀態的算法。

來源

2012-03-24 11:50:57

食人族和傳教士使用IDDFS和GreedyBFS

回答

相關問題