人工智能與或圖搜索課件

2.1與或圖(AND/ORGraph)的搜索為嚴格描述AND/OR圖，我們先推廣弧的概念。在有向圖中的弧是從一個父親節(jié)點指向它的兒子節(jié)點的。在AND/OR圖中使用的弧叫做超弧，一個超弧可以把一個父親節(jié)點和k個兒子節(jié)點同時連接起來，這樣的弧也叫做k連弧，在AND/OR圖中，k連弧用弧線連接起來。當k=1

時，k連弧退化成通常的有向圖中的弧。

2.1與或圖(AND/ORGraph)的搜索為嚴格描述1k連弧一般的弧k連弧一般的弧2n7n6n3n0n1n4n2n5n8與或圖n7n6n3n0n1n4n2n5n8與或圖3n5n1n3n6n7n8n5n0n7n8n4n0三個解圖n5n7n8n4n0n5n1n3n6n7n8n5n0n7n8n4n0三個解圖n54在定義中假定AND/OR圖不含回路，即是說，圖中不存在一個節(jié)點的后裔也是這個節(jié)點的祖先的情形。不含回路保證了節(jié)點間具有部分序關系，從而保證了下面定義的合理性。設N是AND/OR圖G的目標節(jié)點集合，從圖中任意一個節(jié)點n出發(fā)到N的一個解圖是AND/OR圖G的一個子圖，用G’表示，遞歸定義如下：如果n是N中的一個節(jié)點，則G’只包括n.如果n有一條從n出發(fā)的k連弧ai,這個k連弧連接的兒子節(jié)點是{n1,n2,...,nk},則解圖G’由節(jié)點n,k連弧ai,和由n1,n2,...,nk出發(fā)的解圖構成。否則，G沒有從n出發(fā)到N的解圖。在定義中假定AND/OR圖不含回路，即是說，圖中不存在一個5與或圖設從節(jié)點n到目標節(jié)點集合N的費用用c(n,N)表示，則c(n,N)定義如下：如果n是N中的一個節(jié)點，則c(n,N)=0，如果n有一條從n出發(fā)的k連弧ai,這個k連弧連接的兒子節(jié)點是{n1,n2,...,nk},則解圖G’由節(jié)點n,k連弧ai,和由n1,n2,...,nk出發(fā)的解圖構成。這時，解圖G’的費用定義為c(n,N)=c(ai)+c(n,n1)+…+c(n,nk),其中c(ai)是k連弧ai的費用.否則，G沒有從n出發(fā)到N的解圖。設其費用為無窮大∞.。例如，如果假定k連弧的費用是k,則圖3.4所示的AND/OR圖的兩個解圖中，左圖的費用是8，右圖的費用是7。與或圖設從節(jié)點n到目標節(jié)點集合N的費用用c(n,N)表示，62.2與或圖的啟發(fā)式搜索AND/OR圖的啟發(fā)搜索過程AO*1.建立一個只由根節(jié)點s構成的搜索圖G,設從s出發(fā)的解圖的費用為q(s)=h(s),如果s是目標節(jié)點，用SOLVED標記s.2.untils被標上SOLVED,do:3.begin4.通過跟蹤從s出發(fā)的有標記的超弧計算候選解圖G’(這些標記在后面的步驟11中給出)5.在G’中選一個不是目標節(jié)點的葉節(jié)點n,6.擴展節(jié)點n,產(chǎn)生節(jié)點n的所有兒子{n1,n2,...,nk},并把這些兒子連到圖G上,對于每一個不曾在G中出現(xiàn)的兒子nj,設q(nj)=h(nj),如果這些兒子節(jié)點中的某些節(jié)點是目標節(jié)點,則把這些節(jié)點標記為SOLVED.2.2與或圖的啟發(fā)式搜索AND/OR圖的啟發(fā)搜索過程AO*77.建立一個由n構成的單元素集合S.8.直到S變空,do:9.begin10.從S中刪除其兒子節(jié)點不在S中的節(jié)點,記此節(jié)點為m.按以下步驟修改m的費用q(m),對于每一個從m出發(fā)的指向節(jié)點集合{ni1,ni2,...,nik}超弧ai，計算qi(m)=c(ai)+q(ni1)+…+q(nik),這里的q(nij)或者是在本循環(huán)內部的前面步驟計算出的值，或者是在步驟6中指定的值。設q(m)是所有qi(m)的最小者，標記實現(xiàn)這個最小值的超弧，如果本次標記與以前的標記不同，擦去以前的標記，如果這些超弧指向的所有兒子節(jié)點都標記了SOLVED,則把m也標上SOLVED.12.如果m標記了SOLVED或者m修改后的費用與以前的費用不同，則把m通過標記的超弧連接的父親節(jié)點加入到S中，13end14.end7.建立一個由n構成的單元素集合S.8算法分為兩個階段1.4-6步.自頂向下的產(chǎn)生候補解圖,并擴展候補解圖的過程.2.7-12,自底向上修正費用值,標記弧及的過程.例H(n0)=3,H(n1)=2,H(n2)=4,H(n3)=4,H(n4)=1,H(n5)=1,H(n6)=2,H(n7)=0,H(n8)=0,算法分為兩個階段9n1n5n41215,n0n1n5n451n2,4n7,03,n04n8,0n6,25,n0n1n5n451n2,4n7,0n8,0n6,2n3,422一次循環(huán)后二次循環(huán)后三次循環(huán)后四次循環(huán)后圖3.5AO*搜索算法的例子n1n5n41213,n0n34n24n1n5n41215,n0n1n5n451n2,4n7,0105,n0n5n41n7,0n8,02搜索得到的解圖5,n0n5n41n7,0n8,02搜索得到的解圖112.3博弈樹的搜索

窮盡的極大極小過程。

兩個游戲者分別為MAX和MIN,MAX想取得高的分數(shù)，而MIN想取得低的分數(shù)，把整個棋的狀態(tài)以及所有可能的移動都用一個有與或圖表示出來，對于某一游戲者求出他的解圖，就是為游戲者制定的贏的策略。

Nim游戲，桌子上有7枚硬幣，由MAX和MIN兩個人分別把一堆硬幣分成不相等的兩堆，誰不能繼續(xù)做下去，誰就算輸，為MAX制定一個贏的策略。

知識表示，二元組《s,p》,其中s為一集合，表示桌面上各堆的硬幣數(shù)，p表示對當前狀態(tài)應該移動的游戲者。例如

（2，3，2，MAX）

表示現(xiàn)在桌面上有3堆硬幣，分別為2，3，2個，此時應掄到MAX移動。2.3博弈樹的搜索

窮盡的極大極小過程。

兩個游121113固定深度的極大極小過程。

實際的游戲的狀態(tài)空間是非常大的，例如國際象棋有10120個狀態(tài)，要想把所有狀態(tài)都列出來，實際上是做不到的，改進的處理方法是在當前狀態(tài)下把游戲擴展到某一固定的深度，對這個深度的樹的葉節(jié)點進行狀態(tài)估值，然后分別逐層地以取極大和取極小的方式上傳，最終給出對游戲者移動的最佳建議

例；九宮游戲

估值函數(shù)：MAX所能占據(jù)的行，列和對角線數(shù)-

MAX所能占據(jù)的行，列和對角線數(shù)

如果MAX贏，為無窮大如果MIN贏，為05-4=1固定深度的極大極小過程。

實際的游戲的狀態(tài)空間是非常大14兩步棋的例子SJIHGFEDABCMAX取極大值MIM取極小值MAX(-2)(-2)(0)(0)(-6)(9)(-4)(-3)(-4)(-2)(-6)MAX的移動兩步棋的例子SJIHGFEDABCMAX取極大值MIM取極小15過程MINMAX:算法分為兩個階段,第一階段用寬度優(yōu)先產(chǎn)生給定深度內的所有節(jié)點,然后對所有葉節(jié)點進行狀態(tài)估值.第二階段自低向上倒推估計值,一層取極小,一層去極大.直至求出初始節(jié)點的估值.過程MINMAX:16MINMAX6-5=1,5-5=0,6-5=1,

5-5=0,4-5=-15-6=-1,5-5=0,5-6=-1,6-6=0,4-6=-25-4=16-4=2MINMAX6-5=1,5-5=0,6-5=1,5-17人工智能與或圖搜索18Alpha-beta過程

在固定深度的極大極小過程中，對于一個給定的節(jié)點，需要先擴展到給定的深度，然后對葉節(jié)點進行估值，在一層一層地向上返回值，決定最佳移動。為提高效率，我們可以按深度優(yōu)先方式，從左邊開始，先對最左分支擴展到給定深度，定出極大和極小的取值界限，即alpha值和beta值，然后一邊擴展一邊估值，并把估值同alpha值和beta值相比較，這樣就可以省掉許多節(jié)點的估值，當然這些節(jié)點也不必產(chǎn)生了，因此提高了算法的效率，這就是Alpha-beta過程。Alpha-beta過程

在固定深度的極大極小過程中，19人工智能與或圖搜索20Alpha-beta剪枝的原則

1。在任一個MIN節(jié)點，如果發(fā)現(xiàn)了其beta值小于或者等于它的一個MAX祖先節(jié)點的alpha值，則可以剪枝

2。在任一個MAX節(jié)點下，如果發(fā)現(xiàn)了其alpha值大于或者等于它的一個MIN祖先節(jié)點的bata值，則可以剪枝Alpha-beta剪枝的原則

1。在任一個MIN節(jié)點，21253120333MAXMINMAX02253120333MAXMINMAX0222MIN圖3.8alpha-beta剪枝過程05-333-3022-30-23541-30689-3MAX最佳移動β=0α=0β=0α=0α=0α=1β=-3β=1α=6α=1MIN圖3.8alpha-beta剪枝過程232.1與或圖(AND/ORGraph)的搜索為嚴格描述AND/OR圖，我們先推廣弧的概念。在有向圖中的弧是從一個父親節(jié)點指向它的兒子節(jié)點的。在AND/OR圖中使用的弧叫做超弧，一個超弧可以把一個父親節(jié)點和k個兒子節(jié)點同時連接起來，這樣的弧也叫做k連弧，在AND/OR圖中，k連弧用弧線連接起來。當k=1

時，k連弧退化成通常的有向圖中的弧。

2.1與或圖(AND/ORGraph)的搜索為嚴格描述24k連弧一般的弧k連弧一般的弧25n7n6n3n0n1n4n2n5n8與或圖n7n6n3n0n1n4n2n5n8與或圖26n5n1n3n6n7n8n5n0n7n8n4n0三個解圖n5n7n8n4n0n5n1n3n6n7n8n5n0n7n8n4n0三個解圖n527在定義中假定AND/OR圖不含回路，即是說，圖中不存在一個節(jié)點的后裔也是這個節(jié)點的祖先的情形。不含回路保證了節(jié)點間具有部分序關系，從而保證了下面定義的合理性。設N是AND/OR圖G的目標節(jié)點集合，從圖中任意一個節(jié)點n出發(fā)到N的一個解圖是AND/OR圖G的一個子圖，用G’表示，遞歸定義如下：如果n是N中的一個節(jié)點，則G’只包括n.如果n有一條從n出發(fā)的k連弧ai,這個k連弧連接的兒子節(jié)點是{n1,n2,...,nk},則解圖G’由節(jié)點n,k連弧ai,和由n1,n2,...,nk出發(fā)的解圖構成。否則，G沒有從n出發(fā)到N的解圖。在定義中假定AND/OR圖不含回路，即是說，圖中不存在一個28與或圖設從節(jié)點n到目標節(jié)點集合N的費用用c(n,N)表示，則c(n,N)定義如下：如果n是N中的一個節(jié)點，則c(n,N)=0，如果n有一條從n出發(fā)的k連弧ai,這個k連弧連接的兒子節(jié)點是{n1,n2,...,nk},則解圖G’由節(jié)點n,k連弧ai,和由n1,n2,...,nk出發(fā)的解圖構成。這時，解圖G’的費用定義為c(n,N)=c(ai)+c(n,n1)+…+c(n,nk),其中c(ai)是k連弧ai的費用.否則，G沒有從n出發(fā)到N的解圖。設其費用為無窮大∞.。例如，如果假定k連弧的費用是k,則圖3.4所示的AND/OR圖的兩個解圖中，左圖的費用是8，右圖的費用是7。與或圖設從節(jié)點n到目標節(jié)點集合N的費用用c(n,N)表示，292.2與或圖的啟發(fā)式搜索AND/OR圖的啟發(fā)搜索過程AO*1.建立一個只由根節(jié)點s構成的搜索圖G,設從s出發(fā)的解圖的費用為q(s)=h(s),如果s是目標節(jié)點，用SOLVED標記s.2.untils被標上SOLVED,do:3.begin4.通過跟蹤從s出發(fā)的有標記的超弧計算候選解圖G’(這些標記在后面的步驟11中給出)5.在G’中選一個不是目標節(jié)點的葉節(jié)點n,6.擴展節(jié)點n,產(chǎn)生節(jié)點n的所有兒子{n1,n2,...,nk},并把這些兒子連到圖G上,對于每一個不曾在G中出現(xiàn)的兒子nj,設q(nj)=h(nj),如果這些兒子節(jié)點中的某些節(jié)點是目標節(jié)點,則把這些節(jié)點標記為SOLVED.2.2與或圖的啟發(fā)式搜索AND/OR圖的啟發(fā)搜索過程AO*307.建立一個由n構成的單元素集合S.8.直到S變空,do:9.begin10.從S中刪除其兒子節(jié)點不在S中的節(jié)點,記此節(jié)點為m.按以下步驟修改m的費用q(m),對于每一個從m出發(fā)的指向節(jié)點集合{ni1,ni2,...,nik}超弧ai，計算qi(m)=c(ai)+q(ni1)+…+q(nik),這里的q(nij)或者是在本循環(huán)內部的前面步驟計算出的值，或者是在步驟6中指定的值。設q(m)是所有qi(m)的最小者，標記實現(xiàn)這個最小值的超弧，如果本次標記與以前的標記不同，擦去以前的標記，如果這些超弧指向的所有兒子節(jié)點都標記了SOLVED,則把m也標上SOLVED.12.如果m標記了SOLVED或者m修改后的費用與以前的費用不同，則把m通過標記的超弧連接的父親節(jié)點加入到S中，13end14.end7.建立一個由n構成的單元素集合S.31算法分為兩個階段1.4-6步.自頂向下的產(chǎn)生候補解圖,并擴展候補解圖的過程.2.7-12,自底向上修正費用值,標記弧及的過程.例H(n0)=3,H(n1)=2,H(n2)=4,H(n3)=4,H(n4)=1,H(n5)=1,H(n6)=2,H(n7)=0,H(n8)=0,算法分為兩個階段32n1n5n41215,n0n1n5n451n2,4n7,03,n04n8,0n6,25,n0n1n5n451n2,4n7,0n8,0n6,2n3,422一次循環(huán)后二次循環(huán)后三次循環(huán)后四次循環(huán)后圖3.5AO*搜索算法的例子n1n5n41213,n0n34n24n1n5n41215,n0n1n5n451n2,4n7,0335,n0n5n41n7,0n8,02搜索得到的解圖5,n0n5n41n7,0n8,02搜索得到的解圖342.3博弈樹的搜索

窮盡的極大極小過程。

兩個游戲者分別為MAX和MIN,MAX想取得高的分數(shù)，而MIN想取得低的分數(shù)，把整個棋的狀態(tài)以及所有可能的移動都用一個有與或圖表示出來，對于某一游戲者求出他的解圖，就是為游戲者制定的贏的策略。

Nim游戲，桌子上有7枚硬幣，由MAX和MIN兩個人分別把一堆硬幣分成不相等的兩堆，誰不能繼續(xù)做下去，誰就算輸，為MAX制定一個贏的策略。

知識表示，二元組《s,p》,其中s為一集合，表示桌面上各堆的硬幣數(shù)，p表示對當前狀態(tài)應該移動的游戲者。例如

（2，3，2，MAX）

表示現(xiàn)在桌面上有3堆硬幣，分別為2，3，2個，此時應掄到MAX移動。2.3博弈樹的搜索

窮盡的極大極小過程。

兩個游351136固定深度的極大極小過程。

實際的游戲的狀態(tài)空間是非常大的，例如國際象棋有10120個狀態(tài)，要想把所有狀態(tài)都列出來，實際上是做不到的，改進的處理方法是在當前狀態(tài)下把游戲擴展到某一固定的深度，對這個深度的樹的葉節(jié)點進行狀態(tài)估值，然后分別逐層地以取極大和取極小的方式上傳，最終給出對游戲者移動的最佳建議

例；九宮游戲

估值函數(shù)：MAX所能占據(jù)的行，列和對角線數(shù)-

MAX所能占據(jù)的行，列和對角線數(shù)

如果MAX贏，為無窮大如果MIN贏，為05-4=1固定深度的極大極小過程。

實際的游戲的狀態(tài)空間是非常大37兩步棋的例子SJIHGFEDABCMAX取極大值MIM取極小值MAX(-2)(-2)(0)(0)(-6)(9)(-4)(-3)(-4)(-2)(-6)MAX的移動兩步棋的例子SJIHGFEDABCMAX取極大值MIM取極小38過程MINMAX:算法分為兩個階段,第一階段用寬度優(yōu)先產(chǎn)生給定深度內的所有節(jié)點,然后對所有葉節(jié)點進行狀態(tài)估值.第二階段自低向上倒推估計值,一層取極小,一層去極大.直至求出初始節(jié)點的估值.過程MINMAX:39MINMAX6-5=1,5-5=0,6-5=1,

5-5=0,4-5=-15-6=-1,5