第3章 圖搜索與問題求解作業(yè)講解

《第3章 圖搜索與問題求解作業(yè)講解》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第3章作業(yè)題參考答案2.綜述圖搜索的方式和策略。答：用計算機來實現(xiàn)圖的搜索，有兩種最基本的方式：樹式搜索和線式搜索。樹式搜索就是在搜索過程中記錄所經(jīng)過的所有節(jié)點和邊。線式搜索就是在搜索過程中只記錄那些當前認為是處在所找路徑上的節(jié)點和邊。線式搜索的基本方式又可分為不回溯和可回溯的的兩種。圖搜索的策略可分為：盲目搜索和啟發(fā)式搜索。盲目搜索就是無向?qū)У乃阉?。樹式盲目搜索就是窮舉式搜索。而線式盲目搜索，對于不回溯的就是隨機碰撞式搜索，對于回溯的則也是窮舉式搜索。啟發(fā)式搜索則是利用“啟發(fā)性信息”引導的搜索。啟發(fā)式搜索又可分為許多不同的策略，如全

2、局擇優(yōu)、局部擇優(yōu)、最佳圖搜索等。5.（供參考）解：引入一個三元組(q0,q1,q2)來描述總狀態(tài)，開狀態(tài)為0，關狀態(tài)為1，全部可能的狀態(tài)為：Q0=(0,0,0);Q1=(0,0,1);Q2=(0,1,0)Q3=(0,1,1);Q4=(1,0,0);Q5=(1,0,1)Q6=(1,1,0);Q7=(1,1,1)。翻動琴鍵的操作抽象為改變上述狀態(tài)的算子，即F＝{a,b,c}a:把第一個琴鍵q0翻轉一次b:把第二個琴鍵q1翻轉一次c:把第三個琴鍵q2翻轉一次問題的狀態(tài)空間為<{Q5},{Q0Q7},{a,b,c}>問題的狀態(tài)空間圖如下頁所示

3、：從狀態(tài)空間圖，我們可以找到Q5到Q7為3的兩條路徑，而找不到Q5到Q0為3的路徑，因此，初始狀態(tài)“關、開、關”連按三次琴鍵后只會出現(xiàn)“關、關、關”的狀態(tài)。（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，0）（1，1，1）acabacabcbbc6.解：用四元組(f、w、s、g)表示狀態(tài)，f代表農(nóng)夫，w代表狼，s代表羊，g代表菜，其中每個元素都可為0或1，用0表示在左岸，用1表示在右岸。初始狀態(tài)S0：(0,0,0,0)目標狀態(tài)：(1,1,1,1)不合法的狀態(tài):(1,0,0,*),(1,*,

4、0,0),(0,1,1,*),(0,*,1,1)操作集F={P1，P2，P3，P4，Q1，Q2，Q3，Q4}操作符條件動作p1f=0，w=0，s和g相異f=1，w=1p2f=0，s=0，f=1，s=1p3f=0，g=0，w和s相異f=1，g=1q0f=1，s和g相異，w和s相異f=0q1f=1，w＝1，s和g相異f=0，w＝0q2f=1，s＝1，f=0，s＝0q3f=1，g＝1，w和s相異f=0，g＝0方案有兩種：p2→q0→p3→q2→p2→q0→p2p2→q0→p1→q2→p3→q0→p212一棵解樹由S0,A,D,t1,t2,t

5、3組成；另一棵解樹由S0,B,E,t4,t5組成。左邊的解樹：按和代價：g(D)=4,g(A)=7,g(S0)=12按最大代價：g(D)=2,g(A)=5,g(S0)=10右邊的解樹：按和代價：g(E)=2,g(B)=11,g(S0)=18按最大代價：g(E)=2,g(B)=7,g(S0)=14按和代價計算，左邊的解樹為最優(yōu)解樹；按最大代價計算，仍然是左邊的解樹為最優(yōu)解樹。因此，左邊的解樹為最優(yōu)解樹。此題需注意：代價最小的為最優(yōu)解樹。所以，不管是按和代價，還是按最大代價，都是左邊的樹是最優(yōu)解樹。14.傳教士與野人問題：傳教士（M）與野

6、人（C）數(shù)目均為五人，渡船（B）最多可乘3人，請定義一個啟發(fā)函數(shù)，并給出相應的搜索樹。解：定義啟發(fā)函數(shù)h（n）=0;h（n）=M+C;h（n）=M+C-2B只有h（n）=M+C-2B可滿足h（n）≤h*（n），是滿足A*條件的。分兩種情況來討論：先考慮船在左岸的情況，如果不考慮限制條件，至少需要[（M+C-3）/2]*2+1次，其中分子上的“-3”表示剩下的3個留待最后一次運過去。除以2是因為一個來回可以運過去2人，需（M+C-3）/2個來回，而來回數(shù)不能是小數(shù)，所以要取整。一個來回是兩次，所以“*2”，而最后的“+1”，則表示將剩下

7、的3個運過去需要一次擺渡?；喓鬄椋篬（M+C-3）/2]*2+1=M+C-2再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個人將船運往左岸，因此，對于狀態(tài)（M，C，0），需要的擺渡數(shù)，相當于船在左岸的（M+1，C，1）或（M，C+1，1），所以需要的最少擺渡數(shù)為M+C+1-2+1=M+C。綜合條件，需要的最少擺渡數(shù)為M+C-2B。當加上限制條件時，最優(yōu)的擺渡次數(shù)只能大于等于該擺渡數(shù)。所以該啟發(fā)函數(shù)是滿足A*條件的。搜索圖如下：（5，5，1）（5，4，0）（5，3，0）（5，2，0）（4，4，0）（5，3，1）（5，4，1

8、）（5，1，0）（3，3，0）（5，0，0）（5，2，1）（4，4，1）（5，1，1）15.補充1：代價樹如下圖所示：分別給出寬度優(yōu)先及深度優(yōu)先搜索策略下的搜索過程和解。其中，F(xiàn)、I、J、L是目標節(jié)點。寬度優(yōu)先搜索過程：