與或樹的搜索策略搜索的完備性與效率(編輯修改稿)
2025-03-08 07:17 本頁面
【文章內(nèi)容簡介】 搜索是 求代價最小的解樹求代價最小的解樹 的搜索方法。的搜索方法。 為求得代價最小的解樹，每次確定待擴(kuò)展節(jié)點時，需要為求得代價最小的解樹，每次確定待擴(kuò)展節(jié)點時，需要往前多看幾步，往前多看幾步， 計算擴(kuò)展這個節(jié)點可能要付出的代價，計算擴(kuò)展這個節(jié)點可能要付出的代價，并選擇代價最小的節(jié)點進(jìn)行擴(kuò)展并選擇代價最小的節(jié)點進(jìn)行擴(kuò)展 ?！ ? 像這樣根據(jù)代價決定搜索路線的方法稱為與像這樣根據(jù)代價決定搜索路線的方法稱為與 /或樹的有或樹的有序搜索，它是一種序搜索，它是一種 啟發(fā)式搜索啟發(fā)式搜索 策略。策略。解樹的代價計算方法通過計算解樹中節(jié)點的代價得到。若問題可解，由子節(jié)點代價推通過計算解樹中節(jié)點的代價得到。若問題可解，由子節(jié)點代價推算父節(jié)點代價，逐層上推，最終求出算父節(jié)點代價，逐層上推，最終求出 S的代價，即解樹的代價。的代價，即解樹的代價。設(shè)設(shè) c(x, y)表示節(jié)點表示節(jié)點 x到其子節(jié)點到其子節(jié)點 y的代價，則的代價，則 x的代價計算方法如下：的代價計算方法如下：如果如果 x是終葉節(jié)點，則定義是終葉節(jié)點，則定義 x的代價：的代價： h(x)=0如果如果 x不可擴(kuò)展，且不是終葉節(jié)點，則定義：不可擴(kuò)展，且不是終葉節(jié)點，則定義： h(x)=?如果如果 x是是 “或或 ”節(jié)點，節(jié)點， y1， y2， …… ， yn是它的子節(jié)點，則是它的子節(jié)點，則 x的代價為：的代價為：如果如果 x是是 “與與 ”節(jié)點．則節(jié)點．則 x的代價有兩種計算方法：的代價有兩種計算方法：※※ 和代價法和代價法 ※※ 最大代價法最大代價法例：與 /或樹的有序搜索例：設(shè)有如圖所示與 /或樹，包括兩棵解樹，一棵由 S, A, t1, t2組成，另一棵由 S, B, D, G, t4, t5組成。在與 /或樹中，邊上的數(shù)字是該邊的代價， t1, t2 , t3, t4, t5為終葉節(jié)點，代價為 0， E, F是端節(jié)點，代價為 ?。試計算解樹代價。和代價和代價 最大代價最大代價左邊左邊解樹解樹h(A)=11h(S)=13h(A)=6h(S)=8右邊右邊解樹解樹h(G)=3h(D)=4h(B)=6h(S)=8h(G)=2h(D)=3h(B)=5h(S)=7代價計算中存在的問題計算 h(x)的 條件： 已知 x所有子節(jié)點的代價。問題：問題： 搜索是自上而下進(jìn)行的，只有不可擴(kuò)展節(jié)點的代價是搜索是自上而下進(jìn)行的，只有不可擴(kuò)展節(jié)點的代價是已知的（已知的（ ?或或 0），因此除非），因此除非 x的所有子節(jié)點都不可擴(kuò)展，否則 x的代價無法計算得到。解決方案： 根據(jù)問題本身提供的啟發(fā)性信息定義一個 啟發(fā)函數(shù) ，由啟發(fā)函數(shù)估算子節(jié)點的代價，然后反推計算父節(jié)點和先輩節(jié)點的代價。每當(dāng)有新一代的節(jié)點生成時，都要自下而上地重新計算先輩節(jié)點的代價。希望樹希望樹的定義 選擇待擴(kuò)展節(jié)點時，挑選有希望成為最優(yōu)解樹一部分選擇待擴(kuò)展節(jié)點時，挑選有希望成為最優(yōu)解樹一部分的節(jié)點進(jìn)行擴(kuò)展，保證任一時刻求出的部分解樹的代價的節(jié)點進(jìn)行擴(kuò)展，保證任一時刻求出的部分解樹的代價都是最小的。都是最小的。 由這些節(jié)點及先輩節(jié)點（包括初始節(jié)點由這些節(jié)點及先輩節(jié)點（包括初始節(jié)點 S）構(gòu)）構(gòu)成的與成的與 /或樹有可能成為最優(yōu)解樹一部分，被稱為希望或樹有可能成為最優(yōu)解樹一部分，被稱為希望樹。樹。注意：注意：l 搜索過程中，隨著新節(jié)點的不斷生成，節(jié)點的代價值不斷搜索過程中，隨著新節(jié)點的不斷生成，節(jié)點的代價值不斷變化。因此，變化。因此， 希望樹希望樹 也是在也是在 不斷變化不斷變化 的。的。l 有序搜索是一個不斷選擇、不斷修正希望樹的過程。有序搜索是一個不斷選擇、不斷修正希望樹的過程。希望樹的構(gòu)成初始節(jié)點初始節(jié)點 S在希望樹中；在希望樹中；如果節(jié)點如果節(jié)點 x在希望樹中，則一定有：l 如果如果 x是是 ““ 或或 ”” 節(jié)點，節(jié)點， y1， y2， …， yn是它的子節(jié)點，則具有是它的子節(jié)點，則具有 值的那個子節(jié)點值的那個子節(jié)點 yi也應(yīng)在希望樹中。也應(yīng)在希望樹中。l 如果如果 x是是 ““ 與與 ”” 節(jié)點，則它的全部子節(jié)點都應(yīng)在希望樹中。節(jié)點，則它的全部子節(jié)點都應(yīng)在希望樹中。有序搜索算法流程(1)把初始節(jié)點把初始節(jié)點 S放入放入 OPEN表中。表中。(2)根據(jù)當(dāng)前搜索樹中節(jié)點的代價求出以根據(jù)當(dāng)前搜索樹中節(jié)點的代價求出以 S為根的希望樹為根的希望樹 T 。(3)依次把依次把 OPEN表中表中 T的端節(jié)點的端節(jié)點 N選出放入選出放入 CLOSED表中。表中。(4)如果如果 N是終葉節(jié)點，則做下列工作：是終葉節(jié)點，則做下列工作：①① 標(biāo)示標(biāo)示 N為可解節(jié)點。為可解節(jié)點。②② 對對 T應(yīng)用可解標(biāo)示過程，標(biāo)記應(yīng)用可解標(biāo)示過程，標(biāo)記 N的先輩節(jié)點。的先輩節(jié)點。③③ 若若 S被標(biāo)記為可解，則被標(biāo)記為可解，則 T就是最優(yōu)解樹，成功退出。就是最優(yōu)解樹，成功退出。④④ 否則，從否則，從 OPLN表中刪去具有可解先輩的節(jié)點。表中刪去具有可解先輩的節(jié)點。(5)如果如果 N不是終葉節(jié)點，且不可擴(kuò)展，則做下列工作：不是終葉節(jié)點，且不可擴(kuò)展，則做下列工作：①① 標(biāo)示標(biāo)示 N為不可解節(jié)點。為不可解節(jié)點。②② 對對 T應(yīng)用不可
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1