【正文】 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 1 2 3 4 5 6 7 8 9 a b c d 1 2 3 8 4 7 6 5 目標(biāo) 。 。 第三章 一般搜索原理 八數(shù)碼難題的深度優(yōu)先搜索樹 2/27/2023 48 深度優(yōu)先搜索的性質(zhì) ? 一般不能保證找到最優(yōu)解 ? 當(dāng)深度限制不合理時，可能找不到解，可以將算法改為可變深度限制 ? 最壞情況時，搜索空間等同于窮舉 ? 是一個通用的與問題無關(guān)的方法 第三章 一般搜索原理 2/27/2023 49 第三章 一般搜索原理 等代價搜索 成功 是 把具有最小 g(i)值的節(jié)點 i從 OPEN表移至 CLOSED表 計算其后繼節(jié)點 j的 g(j)值。 ? 利用知識來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。 ? 用于決定哪些節(jié)點應(yīng)從搜索樹中拋棄或修剪。它采用估算節(jié)點 n的兩個代價： ?從起始點 s到 n的最小代價路徑的代價 ?從 n到某個目標(biāo)節(jié)點的最小代價路徑的代價 ? 估價函數(shù)的形式： f(n) = g(n) + h(n) 其中： g(n)：是對 g*(n)的估價值 h(n)：是對 h*(n)的估價值 ,稱為啟發(fā)函數(shù) 第三章 一般搜索原理 2/27/2023 58 A算法 估價函數(shù)的說明 ? g*(n)：從 s到 n的最佳路徑的代價 ? h*(n)：從 n到某個目標(biāo)節(jié)點的最佳路徑的代價 ? f*(n)=g*(n)+h*(n)： 從 s經(jīng)過 n到某個目標(biāo)節(jié)點的最佳路徑的代價 ? g(n)、 h(n)、 f(n)分別是 g*(n)、 h*(n)、 f*(n)的估計值 ? 表明，估價函數(shù) f(n)是對從起始點 s經(jīng)過 n到某個目標(biāo)節(jié)點的最佳路徑的代價的估計值 第三章 一般搜索原理 2/27/2023 59 A算法流程 1, OPEN:=(s), f(s):=g(s)+h(s)。 3, n:=FIRST(OPEN)。 5, REMOVE(n, OPEN), ADD(n, CLOSED)。 第三章 一般搜索原理 2/27/2023 60 A算法流程（續(xù)） ADD(mj, OPEN), 標(biāo)記 mj到 n的指針； IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 標(biāo)記 mk到 n的指針； IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml), 標(biāo)記 ml到 n的指針 , ADD(ml, OPEN)。 第三章 一般搜索原理 2/27/2023 62 A*算法 估價函數(shù) 舉例 ? 在問題求解過程中，不可能明確知道 h*(n) ，可根據(jù)經(jīng)驗估計下界范圍條件 ? 例如， 8數(shù)碼問題 ?如取 h(n) = “不在位”的牌數(shù)，可估計出至少要移動h(n) 步，才能達(dá)到目標(biāo)，因此，有 h(n) ≤ h*(n) ?如取 h (n) = 每個 牌與目標(biāo)位置的距離和，同樣可估計出至少要移動 h(n) 步，才能達(dá)到目標(biāo)，因此，有 h(n) ≤ h*(n) 第三章 一般搜索原理 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 2/27/2023 63 博弈中的啟發(fā)式搜索 ? 博弈空間的極小極大搜索 : ? 假定對手具有相同的關(guān)于狀態(tài)空間的知識 ,且用該知識以一致方式比賽 . ? 博弈中的對手分別稱為 MIN和 MAX ? 一種余一棋變體： ? 博弈雙方要交替地將一堆牌分成數(shù)量不同的兩堆牌 ,最先無法分堆的棋手為失敗 第三章 一般搜索原理 2/27/2023 64 窮舉式的極小極大搜索 ? 博弈過程可以用一個樹來表示 ? 標(biāo)記葉節(jié)點若 MIN獲勝標(biāo) 0, MAX獲勝標(biāo) 1, ? 標(biāo)記 MIN節(jié)點為其子節(jié)點值中的最大值 ? 標(biāo)記 MAX節(jié)點為其子節(jié)點值中的最小值 ? 這樣向上傳播 ,直至根節(jié)點 第三章 一般搜索原理 2/27/2023 65 第三章 一般搜索原理 一種余一棋變體樹 43 421 511 7 52 22111 3211 61 4111 2221 31111 211111 322 0 0 1 1 0 1 1 1 1 1 1 0 0 331 0 MIN MAX MIN MAX MIN MAX 2/27/2023 66 固定層深的極小極大搜索 ? 這種策略稱為 n層預(yù)判 ? 用于狀態(tài)空間不可能全部展開的情形，比如國際象棋的狀態(tài)數(shù)大約是 10120 ? n的值由可用的時間和空間資源而定 ? 由于葉節(jié)點不是博弈的最終狀態(tài) ,不能用勝利或失敗來標(biāo)記 ? 需用某個啟發(fā)評估函數(shù)的值來標(biāo)記 ? 這個向上傳播的值不表示是否可以勝利 ,只表示經(jīng)過 n步可達(dá)到的最佳狀態(tài) ,也可能是完全誤導(dǎo)性的 ? 大多數(shù)博弈都為設(shè)計啟發(fā)提供了無限的想象空間 第三章 一般搜索原理 2/27/2023 67 第三章 一般搜索原理 一種九宮游戲的啟發(fā)函數(shù) ? 啟發(fā)值為對 MAX來說存在的所有可能勝利路線 ,減去對 MIN來說存在的所有可能勝利路線 X O X O X O X有 6條 ,O有 5條 可能的勝利路線 E(n)=65=1 X有 4條 ,O有 6條 可能的勝利路線 E(n)=46= 2 X有 5條 ,O有 4條 可能的勝利路線 E(n)=54=1 2/27/2023 68 第三章 一般搜索原理 αβ搜索 ? 單純的極小極大搜索需要對搜索空間進行兩遍分析 ,效率低 ?αβ 搜索 對極小極大搜索進行改進 ? 基本思想：不搜索預(yù)判深度的整個空間，對能判斷不起作用的分支則去掉，不搜索 ? 以深度優(yōu)先方式到達(dá)預(yù)判層，在不斷剪枝的過程中，向上傳播評估值 ?α值是與 MAX節(jié)點關(guān)聯(lián)的不減小值 ? β 值是與 MIN節(jié)點關(guān)聯(lián)的不增大值 2/27/2023 69 第三章 一般搜索原理 αβ搜索舉例 MIN MAX MIN MAX 2 3 5 9 0 7 4 2 1 5 6 3 9 0 7 2 6 3 0 2 3 ≥2 ≤3 ≥5 ≥2 ≤0 ≤2 ≥ 3 2/27/2023 70 雙向搜索 ? 搜索可以是從初始狀態(tài)開始向目標(biāo)狀態(tài)的 正向搜索 ； ? 搜索也可以是從目標(biāo)狀態(tài)開始向初始狀態(tài)的 逆向搜索 ? 再可能是同時從初始狀態(tài)向目標(biāo)狀態(tài)的正向搜索 和從目標(biāo)狀態(tài)向初始狀態(tài)的 逆向搜索 ，直至這兩條路徑在中途某處小結(jié)接為止，這種搜索策略稱為 雙向搜索 第三章 一般搜索原理 2/27/2023 71 消解原理 概述 ? 消解原理又稱為 歸結(jié)原理是一種重要的推理規(guī)則 ? 它來源于定理證明： F1 ∧ F2 ∧ … ∧ Fn → W ? 用反證法證： F= F1 ∧ F2 ∧ … ∧ Fn ∧ ～ W為永假 ? 等價于證明： F對應(yīng)的子句集 S為不可滿足的 ? 歸結(jié)原理的基本思路是：尋找將 S擴充后的子句集 S1，它可滿足性與 S相同，且容易判斷可滿足性，從而知道 S的可滿足性，則定理得證 第三章 一般搜索原理 消解原理 2/27/2023 72