資源描述：
《4-與或圖搜索》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、1與或圖搜索人工智能2主要內(nèi)容與或圖的概念與或樹搜索博弈樹搜索（重點）人工智能3與或圖的概念在上一章狀態(tài)空間搜索的問題中，一個問題可以有幾種求解方法，只要其中一種方法可以求解，則該問題就可以求解。即該節(jié)點的后繼節(jié)點之間是“或”的關(guān)系，即只要一個后繼節(jié)點能夠求解，則該節(jié)點也就可以求解了。從初始節(jié)點到目標節(jié)點之間，可以得到一條由節(jié)點序列組成的求解路徑但現(xiàn)實世界中，有時一個問題也可能需要求解幾個子問題，這些子問題必須全部求解，才可求解原始問題，即這些子問題之間是“與”的關(guān)系。這類問題可以用與或圖表示人工智能4與或圖的概念對于一個復(fù)雜問
2、題，直接求解往往比較困難。此時，可以通過下述方法進行簡化分解等價變換人工智能5分解把一個復(fù)雜問題分解為若干個較簡單的子問題，每個子問題又繼續(xù)分解為若干個更簡單的子問題，重復(fù)此過程，直到不需要再分解或者不能在分解為止。然后對每個子問題分別求解，最后把各子問題的解復(fù)合起來就得到了原問題的解。這時子節(jié)點間是“與”關(guān)系通常用一條弧把各邊連接起來構(gòu)成的圖稱為“與圖”若一節(jié)點有k個與關(guān)系子節(jié)點，則稱該節(jié)點有一個k-連接符…...K個人工智能6等價變換對于復(fù)雜問題，除了可用“分解”方法進行求解外，還可利用等價變換，把它變換為若干個較容易求解的
3、新問題，若新問題中有一個可解，則就得到了原問題的解問題的等價變換過程，也可用一個圖表示，稱為“或圖”…...人工智能7與或圖目標目標初始節(jié)點sabc與圖和或圖結(jié)合起來使用，此時的圖稱為“與或圖”，其中既有“與”節(jié)點，也有“或”節(jié)點后面介紹的更多的是“與或樹”人工智能8與或圖的其他概念本原問題不能在分解或變換，而且直接可解的子問題端節(jié)點與終止節(jié)點沒有子節(jié)點的節(jié)點稱為端節(jié)點本原問題對應(yīng)的節(jié)點稱為終止節(jié)點終止節(jié)點一定是端節(jié)點，端節(jié)點不一定是終止節(jié)點人工智能9與或圖的其他概念可解節(jié)點在與或樹中，滿足下列條件之一的稱為可解節(jié)點是一個終止節(jié)
4、點是一個“或”節(jié)點，且其子節(jié)點中至少有一個是可解節(jié)點是一個“與”節(jié)點，且其子節(jié)點全部是可解節(jié)點不可解節(jié)點不是可解節(jié)點的節(jié)點解樹由可解節(jié)點構(gòu)成，且由這些可解節(jié)點可推出初始節(jié)點（對應(yīng)于原始問題）為可解節(jié)點的子樹稱為解樹在解樹中一定包含初始節(jié)點人工智能10AO*算法也是一種啟發(fā)式搜索算法，與A*算法有些類似具體算法步驟（略）人工智能112.3博弈樹搜索博弈諸如下棋、打牌、戰(zhàn)爭等一類競爭性智能活動稱為博弈最簡單的一種博弈具有以下特征二人零和雙方對壘，輪流采取行動；對一方有利的對另一方必然不利；博弈結(jié)果只能有三種情況：A勝B敗、B勝A敗、
5、平局全信息對壘過程中，雙方都了解當前格局及過去的歷史非偶然雙方都是理智的分析決定自己的行動，不存在“碰運氣”的偶然因素人工智能12博弈樹在博弈過程中，任何一方都希望自己取得勝利。因此，在某一方當前有多個行動方案可供選擇時，他總是挑選對自己最有利而對對方最不利的那個方案行動。如果我們站在A方立場，則可供A選擇的若干方案之間是“或”關(guān)系，因為主動權(quán)在A方手里，他或者選擇這個方案，或者選擇另一個方案，完全由A決定但若B也有若干可供選擇的方案，則對A來說這些方案之間是“與”關(guān)系，因為這時主動權(quán)在B，這些可供選擇的方案中的任何一個都可能被
6、B選中，A必須考慮對自己最不利的情況的發(fā)生把上述博弈過程用圖表示出來，得到的是一棵“與／或”樹注意：該“與／或”樹是始終站在某一方（例如Ａ方）的立場上得出的，不能一會站在Ａ方立場，一會又站在Ｂ方立場人工智能13博弈樹的特點博弈的初始格局是初始節(jié)點在博弈樹中，“或”節(jié)點和“與”節(jié)點是逐層交替出現(xiàn)的己方擴展的節(jié)點之間是“或”關(guān)系對方擴展的節(jié)點之間是“與”關(guān)系雙方輪流擴展節(jié)點所有能使己方獲勝的終局都是本原問題，相應(yīng)的節(jié)點是可解節(jié)點；所有使對方獲勝的終局都是不可解節(jié)點人工智能14例—分錢幣問題有一堆數(shù)目為Ｎ的錢幣，由兩位選手輪流進行分堆
7、，要求每個選手每次只把其中某一堆分成數(shù)目不等的兩小堆，直到有一位選手無法把錢幣再分成不相等的兩堆時就得認輸人工智能15分錢幣問題 狀態(tài)空間圖及搜索解圖（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）對方先走我方必勝人工智能16對于較簡單的博弈問題，可以求出解圖，解圖代表了從開局到終局任何階段上的弈法，但這對于復(fù)雜的博弈問題是不可能實現(xiàn)的在博弈問題中，每個格局可供選
8、擇的行動方案有很多，因此會生成十分龐大的博弈樹。中國象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10161。假設(shè)1毫微秒走一步，約需10145年。西洋跳棋博弈樹約有1040個節(jié)點圍棋結(jié)論：不可能窮舉。試圖利用完整的博弈樹來進行分析是很困難的人工智能17博弈樹搜索可行的辦
