傳教士與野人過河問題

360公司 2012年校園招聘會筆試題算法題

傳教士和野人問題(Missionaries   and   Cannibals)  

這是一個經常在有關讨論人工智能的書籍中見到的問題,   其描述是這樣的:   

　　有N個傳教士和N個野人來到河邊渡河,   河岸有一條船,   每次至多可供k人乘渡。問傳教士為了安全起見,   應如何規劃擺渡方案,   使得任何時刻,   河兩岸以及船上的野人數目總是不超過傳教士的數目(否則不安全,   傳教士有可能被野人吃掉)。即求解傳教士和野人從左岸全部擺渡到右岸的過程中,   任何時刻滿足M(傳教士數)≥C(野人數)和M+C≤k的擺渡方案。

　　我們此處舉例   ,   隻讨論N為3、k為2的乘渡問題,   這樣傳教士和野人問題的描述就具體為如下:   

　　三個傳教士與三個野人來到河邊,   有一條船可供一人或兩人乘渡,   問題是如何用這條船渡河才能使得河的任一岸上野人的數目總不超過傳教士的數目(當然,   如果某一岸上隻有野人而沒有傳教士是允許的)。

　　我們用一個三元組(m   c   b)來表示河岸上的狀态,   其中m、c分别代表某一岸上傳教士與野人的數目,   b=1表示船在這一岸,   b=0則表示船不在。   

　　設N=3,   k=2,   則給定的問題可用下圖表示,   圖中L和R表示左岸和右岸,   B=1或0分别表示有船或無船。         

限制條件是:   兩岸上M≥C,   船上M+C≤2。   

　　我們采用産生式系統來解決這一問題。由于傳教士與野人的總數目是一常數,   是以隻要表示出河的某一岸上的情況就可以了,   為友善起見,   我們選擇傳教士與野人開始所在的岸為所要表示的岸,   并稱其為左岸,   另一岸稱為右岸。但顯然僅用描述左岸的三元組描述就足以表示出整個情況,   是以必須十分重視選擇較好的問題表示法。以後的讨論還可以看到高效率的問題求解過程與控制政策有關,   合适的控制政策可縮小狀态空間的搜尋範圍,   提高求解的效率。因而問題的初始狀态是(3   3   1),   目标狀态是(0   0   0)。 

　　(1)   綜合資料庫:   用三元組表示,   即   (ML,   CL,   BL),   其中0≤ML,   CL≤3,   BL∈{0,   1}   

此時問題述簡化為   (3,   3,   1)®   (0,   0,   0)             

N=3的M-C問題,   狀态空間的總狀态數為4×4×2=32,   根據限制條件的要求,   可以看出隻有20個合法狀态。再進一步分析後,   又發現有4個合法狀态實際上是不可能達到的。是以實際的問題空間僅由16個狀态構成。下表列出分析的結果:   

　　　　(ML,   CL,   BL)   (ML,   CL,   BL)   

　　　　(0   0   1)達不到   (0   0   0)   

　　　　(0   1   1)   (0   1   0)   

　　　　(0   2   1)   (0   2   0)   

　　　　(0   3   1)   (0   3   0)達不到   

　　　　(1   0   1)不合法   (1   0   0)不合法   

　　　　(1   1   1)   (1   1   0)   

　　　　(1   2   1)不合法   (1   2   0)不合法   

　　　　(1   3   1)不合法   (1   3   0)不合法   

　　　　(2   0   1)不合法   (2   0   0)不合法   

　　　　(2   1   1)不合法   (2   1   0)不合法   

　　　　(2   2   1)   (2   2   0)   

　　　　(2   3   1)不合法   (2   3   0)不合法   

　　　　(3   0   1)達不到   (3   0   0)   

　　　　(3   1   1)   (3   1   0)   

　　　　(3   2   1)   (3   2   0)   

　　　　(3   3   1)   (3   3   0)達不到   　   

　　(2)   規則集合:   由擺渡操作組成。該問題主要有兩種操作:   pmc操作(規定為從左岸劃向右岸)和qmc操作(從右岸劃向左岸)。每次擺渡操作,   船上人數有五種組合,   因而組成有10條規則的集合。下面定義的規則前5條為pmc操作(從左岸劃向右岸),   後5條為qmc操作(從右岸劃向左岸)。   

　　　　if   (ML,   CL,   BL=1)   then   (ML-1,   CL,   BL-1);   (p10操作)   

　　　　if   (ML,   CL,   BL=1)   then   (ML,   CL-1,   BL-1);   (p01操作)   

　　　　if   (ML,   CL,   BL=1)   then   (ML-1,   CL-1,   BL-1);   (p11操作)   

　　　　if   (ML,   CL,   BL=1)   then   (ML-2,   CL,   BL-1);   (p20操作)   

　　　　if   (ML,   CL,   BL=1)   then   (ML,   CL-2,   BL-1);   (p02操作)   

　　　　if   (ML,   CL,   BL=0)   then   (ML+1,   CL,   BL+1);   (q10操作)   

　　　　if   (ML,   CL,   BL=0)   then   (ML,   CL+1,   BL+1);   (q01操作)   

　　　　if   (ML,   CL,   BL=0)   then   (ML+1,   CL+1,   BL+1);   (q11操作)   

　　　　if   (ML,   CL,   BL=0)   then   (ML+2,   CL,   BL+1);   (q20操作)   

　　　　if   (ML,   CL,   BL=0)   then   (ML,   CL+2,   BL+1);   (q02操作)           

　　(3)   初始和目标狀态:   即(3,   3,   1)和(0,   0,   0)。和八數位遊戲的問題一樣,   建立了産生式系統描述之後,   就可以通過控制政策,   對狀态空間進行搜尋,   求得一個擺渡操作序列,   使其實作目标狀态。   

　　在讨論用産生式系統求解問題時,   有時引入狀态空間圖的概念很有幫助。狀态空間圖是一個有向圖,   其節點可表示問題的各種狀态(綜合資料庫),   節點之間的弧線代表一些操作(産生式規則),   它們可把一種狀态導向另一種狀态。這樣建立起來的狀态空間圖,   描述了問題所有可能出現的狀态及狀态和操作之間的關系,   因而可以較直覺地看出問題的解路徑及其性質。實際上隻有問題空間規模較小的問題才可能作出狀态空間圖,   例如N=3的M-C問題,的其狀态空間圖如下圖所示,   此時采用的控制政策為順序選取規則。由于每個擺渡操作都有對應的逆操作,   即pmc對應qmc,   是以該圖也可表示成具有雙向弧的形式。           

從狀态空間圖看出解序列相當之多,   但最短解序列隻有4個,   例如   

　　(p11、q10、p02、q01、p20、q11、p20、q01、p02、q01、p02)、   

　　(p11、q10、p02、q01、p02、q11、p20、q01、p02、q10、p11)、   

　　(p02、q01、p02、q01、p20、q11、p20、q01、p02、q01、p02)、   

　　(p02、q01、p02、q01、p20、q11、p20、q01、p02、q10、p11),   

均由11次擺渡操作構成。若給定其中任意兩個狀态分别作為初始和目标狀态,   就立即可找出對應的解序列來。在一般情況下,   求解過程就是對狀态空間搜尋出一條解路徑的過程。   

　　以上這個例子說明了建立産生式系統描述的過程,   這也就是所謂問題的表示。對問題表示的好壞,   往往對求解過程的效率有很大影響。一種較好的表示法會簡化狀态空間和規則集表示,   例如八數位問題中,   如用将牌移動來描述規則,   則8塊将牌就有32條的規則集,   顯然用空格走步來描述就簡單得多。又如M-C問題中,   用3×2的矩陣給出左、右岸的情況來表示一種狀态當然可以,   但顯然僅用描述左岸的三元組描述就足以表示出整個情況。   

　　如果我們用micro-PROLOG的SIMPLE文法來進行程式設計以實作求解乘渡的方案,   則根據你給出的詢問是which(或all)還是is能給出全部擺渡方案或一個擺渡方案。下面的程式由于M-C關系的第一個語句用了回溯控制“/”,   是以實際上隻能得出一個乘渡方案。             

下面我們進行程式設計:   

　　我們把滿足條件的狀态稱為安全狀态,   首先要定義出安全狀态,   通過對問題的分析,   不難得出隻有滿足以下條件之一的狀态才是安全的(以左岸為例):   

　　　　1.   傳教士與野人的數目相等;   

　　　　2.   傳教士都在左岸;   

　　　　3.   傳教士都不在左岸。   

　　safe關系的三個句子分别定義了這三種不同的情況,   其中safe的第一個變元表示傳教士的數目,   第二個變元表示野人的數目。   

從一個狀态到另一狀态的轉換,   通過關系Rule來完成,   它有兩個句子,   分别描述了從左岸到右岸和從右岸到左岸的狀态轉換。Rule的兩個變元都是三元組,   第一個三元組表示目前狀态,   第二個三元組是得到的下一個滿足條件的狀态。   

　　關系M-C通過調用Rule來求解出傳教士與野人的過河方案,   它有四個變元,   第一個變元是目前狀态,   調用時用初始狀态代入,   第二個變元是目标狀态,   第三個變元是一個中間變量,   它以表的形式記錄到目前為止所達到的狀态,   調用的初始值是隻含初始狀态一個元素的表,   第四個變元也是一個表,   求解結束時,   它以逆序形式得到解的路徑。