3.1答:深度優先搜尋與廣度優先搜尋的區別在於:
在對節點n進行擴充套件時,其後繼節點在open表中的存放位置不同。廣度優先搜尋是將後繼節點放入open表的末端,而深度優先搜尋則是將後繼節點放入open表的前端。廣度優先搜尋是一種完備搜尋,即只要問題有解就一定能夠求出,而深度優先搜尋是不完備搜尋。
在不要求求解速度且目標節點的層次較深的情況下,廣度優先搜尋優於深度優先搜尋;在要求求解速度且目標節點的層次較淺的情況下,深度優先搜尋優於廣度優先搜尋。
廣度優先的正例:積木問題;深度優先的正例:郵遞員問題,反例:西洋棋。
3.2答:衡量標準為:這組子狀態中有沒有目標狀態,如果有,則選擇該節點並且搜尋成功;若沒有,則按照某種控制策略從已生成的狀態中再選擇乙個狀態作為當前狀態重複搜尋過程。
3.3答:(1)廣度優先搜尋:該程式必須找到解,並且最好是最優解;
(2)廣度優先搜尋:醫生要根據病人的各種病狀判斷病人的病;
(3)深度優先搜尋:該程式要求一定要找到目標路徑;
(4)深度優先搜尋:該程式要求找到最優解;
(5)廣度優先搜尋:不能確定它們是否等同,既不能確定它們是否有等同解。
3.4答:對於四皇后問題,如果放乙個皇后的耗散值為1的話,則任何乙個解的耗散值都是4。
因此如果h是對該耗散值的估計,是沒有意義的。對於像四皇后這樣的問題,啟發函式應該是對找到解的可能性的評價。利用乙個位置放皇后後,消去的對角線的長度來進行評價。
3.5答:定義h1=m+c-2b,其中m,c分別是在河的左岸的傳教士人數和野人人數。
b=1表示船在左岸,b=0表示船在右岸。也可以定義h2=m+c。h1是滿足a*條件的,而h2不滿足。
要說明h2=m+c不滿足a*條件是很容易的,只需要給出乙個反例就可以了。比如狀態(1, 1, 1),h2=m+c=1+1=2,而實際上只要一次擺渡就可以達到目標狀態,其最優路徑的耗散值為1。所以不滿足a*的條件。
下面我們來證明h1=m+c-2b是滿足a*條件的。
我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件,也就是說,船一次可以將三人從左岸運到右岸,然後再有乙個人將船送回來。
這樣,船乙個來回可以運過河2人,而船仍然在左岸。而最後剩下的三個人,則可以一次將他們全部從左岸運到右岸。所以,在不考慮限制條件的情況下,也至少需要擺渡次。
其中分子上的"-3"表示剩下三個留待最後一次運過去。除以"2"是因為乙個來回可以運過去2人,需要個來回,而"來回"數不能是小數,需要向上取整,這個用符號表示。而乘以"2"是因為乙個來回相當於兩次擺渡,所以要乘以2。
而最後的"+1",則表示將剩下的3個運過去,需要一次擺渡。
化簡有:
再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸,需要乙個人將船運到左岸。
因此對於狀態(m,c,0)來說,其所需要的最少擺渡數,相當於船在左岸時狀態(m+1,c,1)或(m,c+1,1)所需要的最少擺渡數,再加上第一次將船從右岸送到左岸的一次擺渡數。因此所需要的最少擺渡數為:(m+c+1)-2+1 。
其中(m+c+1)的"+1"表示送船回到左岸的那個人,而最後邊的"+1",表示送船到左岸時的一次擺渡。化簡有:(m+c+1)-2+1=m+c。
綜合船在左岸和船在右岸兩種情況下,所需要的最少擺渡次數用乙個式子表示為:m+c-2b。其中b=1表示船在左岸,b=0表示船在右岸。
由於該擺渡次數是在不考慮限制條件下,推出的最少所需要的擺渡次數。因此,當有限制條件時,最優的擺渡次數只能大於等於該擺渡次數。所以該啟發函式h是滿足a*條件的。
3.6答:在搜尋期間改善h函式,是一種動態改變h函式的方法。
像改進的a*演算法中,對next中的節點按g值的大小選擇待擴充套件的節點,相當於令這些節點的h=0,就是動態修改h函式的一種方法。
由定理2:若h(n)滿足單調限制,則由a*所擴充套件的節點序列,其f值是非遞減的,即f(ni)≤f(nj)),當h滿足單調條件時,a*所擴充套件的節點序列,其f是非遞減的。對於任何節點i,j,如果j是i的子節點,則有f(i)≤f(j)。
利用該性質,我們可以提出另一種動態修改h函式的方法:f(j)=max(f(i), f(j))
以f(j)作為節點j的f值。f值的改變,隱含了h值的改變。當h不滿足單調條件時,經過這樣修正後的h具有一定的單調性質,可以減少重複節點的可能性。
3.7答:
像這種型別的問題,由於涉及到城市距離或旅行費用,所以利用代價樹廣度優先搜尋求解。為此,首先必須將旅行交通圖轉換為代價樹,轉換方法為:從初始節點a開始,把與它直接相鄰的節點作為他的後繼節點,對其他節點也作同樣的擴充套件,但若乙個節點以作為某節點的前驅節點,則它就不能再作為該結點的後繼結點。
另外,圖中節點除了初始節點a之外,其它的節點都有可能在代價樹中多次出現,為了區分它們的多次出現,分別用下標1,2…標出。但他們卻是圖中的同乙個節點。設估價函式f(n)=d(n)+w(n),其中d(n)為狀態的深度,w(n)為城市間的距離。
代價樹如下所示:
acebda
定義h1=n*k,其中n是還未走過的城市數,k是還未走過的城市間距離的最小值。 h2=,其中n是還未走過的城市數,ki是還未走過的城市間距離中n個最小的距離。 顯然這兩個h函式均滿足a*條件。
3.8答:可定義h為:h=b右邊的w的數目
設j節點是i節點的子節點,則根據走法不同,h(i)-h(j)的值和c(i, j)分為如下幾種情況:
(1)b或w走到了相鄰的乙個空格位置,此時: h(i)-h(j)=0, c(i,j)=1;
(2)w跳過了1或2個w,此時 h(i)-h(j)=0, c(i,j)=1或2;
(3)w向右跳過了乙個b(可能同時包含乙個w),此時: h(i)-h(j)=-1, c(i,j)=1或2;
(4)w向右跳過了兩個b,此時: h(i)-h(j)=-2, c(i,j)=2;
(5)w向左跳過了乙個b(可能同時包含乙個w),此時: h(i)-h(j)=1, c(i,j)=1或2;
(6)w向左跳過了兩個b,此時: h(i)-h(j)=2, c(i,j)=2;
(7)b跳過了1或2個b,此時 h(i)-h(j)=0, c(i,j)=1或2;
(8)b向右跳過了乙個w(可能同時包含乙個b),此時: h(i)-h(j)=1, c(i,j)=1或2;
(9)b向右跳過了兩個w,此時: h(i)-h(j)=2, c(i,j)=2;
(10)b向左跳過了乙個w(可能同時包含乙個b),此時: h(i)-h(j)=-1, c(i,j)=1或2;
(11)b向左跳過了兩個w,此時: h(i)-h(j)=-2, c(i,j)=2;
縱上所述,無論是哪一種情況,具有:h(i)-h(j)≤c(i,j)。且容易驗證h(t)=0,所以該h是單調的。
由於h滿足單調條件,所以也一定有h(n)≤h*(n),即滿足a*條件。
3.9答:
3.10答:
(1)余一棋的弈法如下:兩棋手可以從5個錢幣堆中輪流拿走乙個、兩個或三個錢幣,揀起最後乙個錢幣者算輸。試通過博弈證明,後走的選手必勝,並給出乙個簡單的特徵標記來表示取勝策略。
為了方便起見,用((ab)()())這樣的表表示乙個狀態。這樣得到搜尋圖如下:
(2)八數碼問題空格:up,left,down,right
3.11答:
(1)與/或圖的解圖:那些可解結點的子圖,包含一結點到目的結點集的、連通的可解結點的子圖。在問題的完整的隱含圖中擴充套件生成出包含初始結點和目的結點集合的連通的明顯子圖。
(2)演算法ao*:必須對當前已生成出的與或圖中的所有結點實施其每解點是否為可解結點的標註過程,如果起始結點被標註為可解的,則搜尋過程可成功地結束;如果起始結點還不能被標註為可解的,則應當繼續擴充套件生成結點(盡可能地記錄,所有生成的結點中,哪些結點被標註了可解的,以便減少下一次標註過程的工作量);同樣地,對不可解結點也同樣如此。
利用結點的可解/不可解性質,能從搜尋圖中刪去可解結點的任何不可解結點的子結點;同樣地,能刪去不可解結點的所有的子結點(搜尋這些被刪除的結點是沒有意義的,而只會降低搜尋的效率)。兩個主要過程的反覆:
自上而下的圖生長過程,並通過跟蹤有標記的連線符尋找乙個候選區域性解圖
自下而上的估價函式值的修正、連線符的標記和solved的標註過程
(3)3.12答:此題要求按照課中例題的方式,給出演算法,以下是每個迴圈結束時的搜尋圖。
上面這種做法比較簡單,也可以如下做:
3.13答:略
3.14答:博弈搜尋通常被限制在一定的範圍,搜尋的目標是確定一步好的走法(好棋),等對手回手後,再繼續搜尋。
因此,博弈搜尋過程總是由當前狀態向目標狀態搜尋,而不是由目標狀態向當前狀態搜尋。這類博弈的例項有西洋跳棋等。
3.15答:8———
3.16答: 見上圖
3.17答:略
3.18答:α-β剪裁演算法.
α剪裁-若極小層的β<=α(先輩層)則中止這個min以下的搜尋.
β剪裁-若極大層的α>β(先輩層)則中止這個max以下的搜尋
演算法如下:
double alphabeta( int depth, double alpha, double beta, position p);
if( t3.19-3.22 答:略
第三章鋼結構連線習題解答
第三章習題解答 1.解 q235鋼 1 採用側面角焊縫 最小焊腳尺寸 角鋼肢背處最大焊腳尺寸 角鋼肢尖處最大焊腳尺寸 角鋼肢尖和肢背都取 查表3 2得 所需焊縫計算長度 焊縫的實際長度為 取240。取140。2 採用三面圍焊縫,取 正面角焊縫承擔的內力為 側面角焊縫承擔的內力為 所需焊縫計算長度 焊...
材料力學習題解答第三章
3 1求圖中所示杆各個橫截面上的應力,已知橫截面面積a 400mm2。解a 題3 1a 圖 解b 題3 1b 圖 3 2圖中為變截面杆,如果橫截面面積a1 200mm2,a2 300mm2,a3 400mm2,求杆內各橫截面上的應力。解a 題3 2a 圖 解b 題3 2b 圖 3 3 圖標桿繫結構中...
第三章習題
單選題 1 培訓需求分析就是採用科學的方法弄清的內容不包括 a誰最需要培訓 b為什麼培訓 c培訓什麼 d誰來培訓 2 現代培訓活動的首要環節是 a培訓需求分析 b培訓規劃的制定 c培訓組織與實施 d培訓效果的評估 3 對於從事低層次工作的新員工的培訓需求分析,通常採用 來確定其在工作中需要的各種技能...