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

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

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

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

設(shè)N=3, k=2, 則給定的問題可用下圖表示, 圖中L和R表示左岸和右岸, B=1或0分別表示有船或無船。 約束條件是: 兩岸上M≥C, 船上M+C≤2。

我們采用產(chǎn)生式系統(tǒng)來解決這一問題。由于傳教士與野人的總數(shù)目是一常數(shù), 所以只要表示出河的某一岸上的情況就可以了, 為方便起見, 我們選擇傳教士與野人開始所在的岸為所要表示的岸, 并稱其為左岸, 另一岸稱為右岸。但顯然僅用描述左岸的三元組描述就足以表示出整個情況, 因此必須十分重視選擇較好的問題表示法。以后的討論還可以看到高效率的問題求解過程與控制策略有關(guān), 合適的控制策略可縮小狀態(tài)空間的搜索范圍, 提高求解的效率。

因而問題的初始狀態(tài)是(3 3 1), 目標(biāo)狀態(tài)是(0 0 0)。

(1) 綜合數(shù)據(jù)庫: 用三元組表示, 即 (ML, CL, BL), 其中0≤ML, CL≤3, BL∈{0, 1} 此時問題述簡化為 (3, 3, 1)? (0, 0, 0) N=3的M-C問題, 狀態(tài)空間的總狀態(tài)數(shù)為4×4×2=32, 根據(jù)約束條件的要求, 可以看出只有20個合法狀態(tài)。再進一步分析后, 又發(fā)現(xiàn)有4個合法狀態(tài)實際上是不可能達(dá)到的。因此實際的問題空間僅由16個狀態(tài)構(gòu)成。下表列出分析的結(jié)果:

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

(0 0 1)達(dá)不到 (0 0 0) 　　　　

(0 1 1)???????? (0 1 0) 　　　

(0 2 1)????? ?(0 2 0) 　　　　

(0 3 1)?????? (0 3 0)達(dá)不到 　　　　

(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)達(dá)不到 (3 0 0) 　　　　

(3 1 1)????? (3 1 0) 　　　　

(3 2 1)???? ?(3 2 0) 　　　　

(3 3 1)????? (3 3 0)達(dá)不到 　 　　

(2) 規(guī)則集合: 由擺渡操作組成。該問題主要有兩種操作: pmc操作(規(guī)定為從左岸劃向右岸)和qmc操作(從右岸劃向左岸)。每次擺渡操作, 船上人數(shù)有五種組合, 因而組成有10條規(guī)則的集合。下面定義的規(guī)則前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) 初始和目標(biāo)狀態(tài): 即(3, 3, 1)和(0, 0, 0)。

和八數(shù)碼游戲的問題一樣, 建立了產(chǎn)生式系統(tǒng)描述之后, 就可以通過控制策略, 對狀態(tài)空間進行搜索, 求得一個擺渡操作序列, 使其實現(xiàn)目標(biāo)狀態(tài)。 　　在討論用產(chǎn)生式系統(tǒng)求解問題時, 有時引入狀態(tài)空間圖的概念很有幫助。狀態(tài)空間圖是一個有向圖, 其節(jié)點可表示問題的各種狀態(tài)(綜合數(shù)據(jù)庫), 節(jié)點之間的弧線代表一些操作(產(chǎn)生式規(guī)則), 它們可把一種狀態(tài)導(dǎo)向另一種狀態(tài)。這樣建立起來的狀態(tài)空間圖, 描述了問題所有可能出現(xiàn)的狀態(tài)及狀態(tài)和操作之間的關(guān)系, 因而可以較直觀地看出問題的解路徑及其性質(zhì)。實際上只有問題空間規(guī)模較小的問題才可能作出狀態(tài)空間圖, 例如N=3的M-C問題,的其狀態(tài)空間圖如下圖所示, 此時采用的控制策略為順序選取規(guī)則。由于每個擺渡操作都有對應(yīng)的逆操作, 即pmc對應(yīng)qmc, 所以該圖也可表示成具有雙向弧的形式。 從狀態(tài)空間圖看出解序列相當(dāng)之多, 但最短解序列只有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次擺渡操作構(gòu)成。若給定其中任意兩個狀態(tài)分別作為初始和目標(biāo)狀態(tài), 就立即可找出對應(yīng)的解序列來。在一般情況下, 求解過程就是對狀態(tài)空間搜索出一條解路徑的過程。

以上這個例子說明了建立產(chǎn)生式系統(tǒng)描述的過程, 這也就是所謂問題的表示。對問題表示的好壞, 往往對求解過程的效率有很大影響。一種較好的表示法會簡化狀態(tài)空間和規(guī)則集表示, 例如八數(shù)碼問題中, 如用將牌移動來描述規(guī)則, 則8塊將牌就有32條的規(guī)則集, 顯然用空格走步來描述就簡單得多。又如M-C問題中, 用3×2的矩陣給出左、右岸的情況來表示一種狀態(tài)當(dāng)然可以, 但顯然僅用描述左岸的三元組描述就足以表示出整個情況。 　　如果我們用micro-PROLOG的SIMPLE語法來進行編程以實現(xiàn)求解乘渡的方案, 則根據(jù)你給出的詢問是which(或all)還是is能給出全部擺渡方案或一個擺渡方案。下面的程序由于M-C關(guān)系的第一個語句用了回溯控制“/”, 所以實際上只能得出一個乘渡方案。

下面我們進行程序設(shè)計:

我們把滿足條件的狀態(tài)稱為安全狀態(tài), 首先要定義出安全狀態(tài), 通過對問題的分析, 不難得出只有滿足以下條件之一的狀態(tài)才是安全的(以左岸為例): 　　　　1. 傳教士與野人的數(shù)目相等;

2. 傳教士都在左岸;

3. 傳教士都不在左岸。

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

從一個狀態(tài)到另一狀態(tài)的轉(zhuǎn)換, 通過關(guān)系Rule來完成, 它有兩個句子, 分別描述了從左岸到右岸和從右岸到左岸的狀態(tài)轉(zhuǎn)換。Rule的兩個變元都是三元組, 第一個三元組表示當(dāng)前狀態(tài), 第二個三元組是得到的下一個滿足條件的狀態(tài)。

關(guān)系M-C通過調(diào)用Rule來求解出傳教士與野人的過河方案, 它有四個變元, 第一個變元是當(dāng)前狀態(tài), 調(diào)用時用初始狀態(tài)代入, 第二個變元是目標(biāo)狀態(tài), 第三個變元是一個中間變量, 它以表的形式記錄到目前為止所達(dá)到的狀態(tài), 調(diào)用的初始值是只含初始狀態(tài)一個元素的表, 第四個變元也是一個表, 求解結(jié)束時, 它以逆序形式得到解的路徑。

希望通過結(jié)構(gòu)化知識，提高學(xué)習(xí)效率，讓你的工作時間更值錢，賺錢更高效！------------《 數(shù)據(jù)分析筆記》