? 有N個傳教士和N個野人來到河邊渡河, 河岸有一條船, 每次至多可供k人乘渡。問傳教士為了安全起見, 應如何規(guī)劃擺渡方案, 使得任何時刻, 河兩岸以及船上的野人數(shù)目總是不超過傳教士的數(shù)目(否則不安全, 傳教士有可能被野人吃掉)炬搭。即求解傳教士和野人從左岸全部擺渡到右岸的過程中, 任何時刻滿足M(傳教士數(shù))≥C(野人數(shù))和M+C≤k的擺渡方案忍坷。
我們此處舉例 , 只討論N為3、k為2的乘渡問題, 這樣傳教士和野人問題的描述就具體為如下:
三個傳教士與三個野人來到河邊, 有一條船可供一人或兩人乘渡, 問題是如何用這條船渡河才能使得河的任一岸上野人的數(shù)目總不超過傳教士的數(shù)目(當然, 如果某一岸上只有野人而沒有傳教士是允許的)深胳。
我們用一個三元組(m c b)來表示河岸上的狀態(tài), 其中m绰疤、c分別代表某一岸上傳教士與野人的數(shù)目, b=1表示船在這一岸, b=0則表示船不在。
設N=3, k=2, 則給定的問題可用下圖表示, 圖中L和R表示左岸和右岸, B=1或0分別表示有船或無船舞终。 約束條件是: 兩岸上M≥C, 船上M+C≤2轻庆。
我們采用產生式系統(tǒng)來解決這一問題。由于傳教士與野人的總數(shù)目是一常數(shù), 所以只要表示出河的某一岸上的情況就可以了, 為方便起見, 我們選擇傳教士與野人開始所在的岸為所要表示的岸, 并稱其為左岸, 另一岸稱為右岸敛劝。但顯然僅用描述左岸的三元組描述就足以表示出整個情況, 因此必須十分重視選擇較好的問題表示法余爆。以后的討論還可以看到高效率的問題求解過程與控制策略有關, 合適的控制策略可縮小狀態(tài)空間的搜索范圍, 提高求解的效率。
因而問題的初始狀態(tài)是(3 3 1), 目標狀態(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)實際上是不可能達到的。因此實際的問題空間僅由16個狀態(tài)構成上陕。下表列出分析的結果:
(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) 規(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) 初始和目標狀態(tài): 即(3, 3, 1)和(0, 0, 0)。
和八數(shù)碼游戲的問題一樣, 建立了產生式系統(tǒng)描述之后, 就可以通過控制策略, 對狀態(tài)空間進行搜索, 求得一個擺渡操作序列, 使其實現(xiàn)目標狀態(tài)庶溶。 在討論用產生式系統(tǒng)求解問題時, 有時引入狀態(tài)空間圖的概念很有幫助煮纵。狀態(tài)空間圖是一個有向圖, 其節(jié)點可表示問題的各種狀態(tài)(綜合數(shù)據(jù)庫), 節(jié)點之間的弧線代表一些操作(產生式規(guī)則), 它們可把一種狀態(tài)導向另一種狀態(tài)懂鸵。這樣建立起來的狀態(tài)空間圖, 描述了問題所有可能出現(xiàn)的狀態(tài)及狀態(tài)和操作之間的關系, 因而可以較直觀地看出問題的解路徑及其性質。實際上只有問題空間規(guī)模較小的問題才可能作出狀態(tài)空間圖, 例如N=3的M-C問題,的其狀態(tài)空間圖如下圖所示, 此時采用的控制策略為順序選取規(guī)則醉途。由于每個擺渡操作都有對應的逆操作, 即pmc對應qmc, 所以該圖也可表示成具有雙向弧的形式矾瑰。 從狀態(tài)空間圖看出解序列相當之多, 但最短解序列只有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次擺渡操作構成。若給定其中任意兩個狀態(tài)分別作為初始和目標狀態(tài), 就立即可找出對應的解序列來潮孽。在一般情況下, 求解過程就是對狀態(tài)空間搜索出一條解路徑的過程揪荣。
以上這個例子說明了建立產生式系統(tǒng)描述的過程, 這也就是所謂問題的表示。對問題表示的好壞, 往往對求解過程的效率有很大影響往史。一種較好的表示法會簡化狀態(tài)空間和規(guī)則集表示, 例如八數(shù)碼問題中, 如用將牌移動來描述規(guī)則, 則8塊將牌就有32條的規(guī)則集, 顯然用空格走步來描述就簡單得多仗颈。又如M-C問題中, 用3×2的矩陣給出左、右岸的情況來表示一種狀態(tài)當然可以, 但顯然僅用描述左岸的三元組描述就足以表示出整個情況椎例。 如果我們用micro-PROLOG的SIMPLE語法來進行編程以實現(xiàn)求解乘渡的方案, 則根據(jù)你給出的詢問是which(或all)還是is能給出全部擺渡方案或一個擺渡方案挨决。下面的程序由于M-C關系的第一個語句用了回溯控制“/”, 所以實際上只能得出一個乘渡方案。
下面我們進行程序設計:
我們把滿足條件的狀態(tài)稱為安全狀態(tài), 首先要定義出安全狀態(tài), 通過對問題的分析, 不難得出只有滿足以下條件之一的狀態(tài)才是安全的(以左岸為例): 1. 傳教士與野人的數(shù)目相等;
2. 傳教士都在左岸;
3. 傳教士都不在左岸订歪。
safe關系的三個句子分別定義了這三種不同的情況, 其中safe的第一個變元表示傳教士的數(shù)目, 第二個變元表示野人的數(shù)目凰棉。
從一個狀態(tài)到另一狀態(tài)的轉換, 通過關系Rule來完成, 它有兩個句子, 分別描述了從左岸到右岸和從右岸到左岸的狀態(tài)轉換。Rule的兩個變元都是三元組, 第一個三元組表示當前狀態(tài), 第二個三元組是得到的下一個滿足條件的狀態(tài)陌粹。
關系M-C通過調用Rule來求解出傳教士與野人的過河方案, 它有四個變元, 第一個變元是當前狀態(tài), 調用時用初始狀態(tài)代入, 第二個變元是目標狀態(tài), 第三個變元是一個中間變量, 它以表的形式記錄到目前為止所達到的狀態(tài), 調用的初始值是只含初始狀態(tài)一個元素的表, 第四個變元也是一個表, 求解結束時, 它以逆序形式得到解的路徑。
希望通過結構化知識福压，提高學習效率掏秩，讓你的工作時間更值錢，賺錢更高效荆姆！------------《 數(shù)據(jù)分析筆記》
