食人族和傳教士與力量

-1

我需要一些幫助，我們的教授給我們的數學任務。任何建議都會有幫助。問題是：食人族和傳教士與力量

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

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

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

感謝預期，

馬克。

來源

2013-10-10 Mátray Márk

你嘗試過什麼......憑直覺我首先證明了一個場景，甚至可解。 –

這個問題並不清楚，因爲如果力量參數沒有定義，那麼我可以給每個傳教士分配'N'強度，因此我不需要算法。我可以使用for循環在河對岸傳送一個傳教士和一個食人族 – azmuhak

讓我們希望M傳教力量的總和至少爲N.否則，他們不會在河邊。如果任何傳教士的力量大於2，可能沒有解決辦法。（4個食人族; 2個傳教士強項1和3）。 –

將您的問題建模爲州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'

來源

2013-10-10 15:41:42 amit

食人族和傳教士與力量

回答

相關問題