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