及或樹的搜索策略_搜索的完備性及效率

1、可解節(jié)點的遞歸定義為：可解節(jié)點的遞歸定義為：l終葉節(jié)點是可解節(jié)點，直終葉節(jié)點是可解節(jié)點，直接和本原問題相關(guān)連；接和本原問題相關(guān)連；l非終葉節(jié)點含有非終葉節(jié)點含有“或或”子子節(jié)點時，只要子節(jié)點中有節(jié)點時，只要子節(jié)點中有一個是可解節(jié)點，該非終一個是可解節(jié)點，該非終葉節(jié)點便為可解節(jié)點；葉節(jié)點便為可解節(jié)點；l非終葉節(jié)點含有非終葉節(jié)點含有“與與”子子節(jié)點時，只有子節(jié)點全為節(jié)點時，只有子節(jié)點全為可解節(jié)點時，該非終葉節(jié)可解節(jié)點時，該非終葉節(jié)點才是可解節(jié)點。點才是可解節(jié)點。注意：注意：終葉節(jié)點一定是端節(jié)點，終葉節(jié)點一定是端節(jié)點，但端節(jié)點不一定是終葉節(jié)點。但端節(jié)點不一定是終葉節(jié)點。由可解子節(jié)點來確定先輩節(jié)點是由

2、可解子節(jié)點來確定先輩節(jié)點是否為可解節(jié)點的過程稱為否為可解節(jié)點的過程稱為可解標(biāo)可解標(biāo)示過程示過程。由不可解子節(jié)點來確定先輩節(jié)點由不可解子節(jié)點來確定先輩節(jié)點是否為可解節(jié)點的過程稱為是否為可解節(jié)點的過程稱為不可不可解標(biāo)示過程解標(biāo)示過程。不可解節(jié)點的定義為：不可解節(jié)點的定義為：關(guān)于可解節(jié)點的三個條件全關(guān)于可解節(jié)點的三個條件全部不滿足的節(jié)點，稱為不可解部不滿足的節(jié)點，稱為不可解節(jié)點；節(jié)點； 1,niiih xc x yh y 1min,iii nh xc x yh y 1max,iii nh xc x yh y 例：設(shè)有如圖所示與例：設(shè)有如圖所示與/或樹，包括兩棵解樹，一棵由或樹，包括兩棵解樹，一棵由S

3、, A, t1, t2組成，另一棵組成，另一棵由由S, B, D, G, t4, t5組成。在與組成。在與/或樹中，邊上的數(shù)字是該邊的代價，或樹中，邊上的數(shù)字是該邊的代價，t1, t2 , t3, t4, t5為終葉節(jié)點，代價為為終葉節(jié)點，代價為0，E, F是端節(jié)點，代價為是端節(jié)點，代價為 。試計算解樹代價。試計算解樹代價。希望樹希望樹1min,iii nc x yh y h(A)=c(A, B)+h(B)+c(A, C)+h(C) =(1+3)+(1+3)=8hA(S0)=8+1=9h(D)=7，hD(S0)=8S0的右子樹的右子樹是希望樹是希望樹對希望樹的端節(jié)點對希望樹的端節(jié)點E擴展擴展兩層后得到的與兩層后得到的與/或樹或樹h(G)=7h(H)=6h(E)=7h(D)=11hD(S0)=12S0的左子樹是希望樹的左子樹是希望樹hA(S0)=9h(L)=2，h(M)=6，h(B)=3，h(A)=8，hA(S0)=9終葉節(jié)點終葉節(jié)點L和和B都是可解節(jié)點都是可解節(jié)點C無法判斷是否可無法判斷是否可解節(jié)點解節(jié)點A和和S0也無法判斷也無法判斷Ch(N)=2，h(P)=7，h(C)=3，