食人族和傳教士與力量

Question

我需要一些幫助，我們的教授給我們的數學任務。任何建議都會有幫助。 問題是：

有N個食人族和M missinaries。所有傳教士都有一個強度屬性，可以是1或任何正整數。強度表示他可以擊退多少食人族。

基本上有兩條河，有兩條船，你必須把所有的人轉移到另一邊，而不讓食人族吃傳教士。

你會爲此編寫一個程序嗎？轉移分組算法是什麼？

感謝預期，

馬克。

Answer 1

將您的問題建模爲州graph。

在這裏，一狀態是（{L，R} ^Ñ，{L，R}^米，{L，R}）其中：

• 首先n條目：一個用於每個傳教士 - 他在哪裏：左江的/右岸
• 接下來，m項：一個是他是每個canibal-：河流的左/右銀行
• 最後條目是船

這些是你的頂點 - 你也應該修剪無效的狀態 - 傳教士的力量在一個（或更多）方面是不夠的。計算每個狀態很容易。

您的邊緣：

E = { (S1,S2) | Can move in one boat ride from S1 to S2 } 

所有剩下要做的 - 使用一些shortest path algorithm來找到最短路徑：到(R,R,...,R)(L,L,....,L)。

您可以使用BFS這個任務，甚至bi-directional search - 或知情算法（admissible heuristic）如A* Algorithm。

PS。 '圖'只是概念上的，實際上你會有一個函數next:S->2^S，給定一個狀態 - 返回這個狀態的所有有效繼承者（說明你可以使用S圖上的一條邊來得到它們）。這將允許您在運行中「生成圖形」。

你next(S)功能應該是這樣的（高級別僞代碼，不優化）：

next(S): 
    let x be the bank where the boat is, and y the other bank 
    for each person p1 on bank x: 
     S' = S where boat and p1 moved from x to y 
     if S' is valid according to strength limitations, yield S' 
     for each p2 != p1 on bank x: 
     S' = S where boat and p1 and p2 moved from x to y 
     if S' is valid according to strength limitations, yield S'