【正文】 4 8 7 32 5 61 4 87 3 2 5 61 4 7 3 82 5 61 47 3 82 5 1 4 67 3 8S 123456789101112131415162 51 4 67 3 82 4 51 67 3 8 2 51 4 67 3 82 4 5 1 67 3 82 4 51 6 7 3 82 4 51 3 67 82 4 51 3 6 7 82 4 51 3 67 8 17181920合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 15/79 盲目搜索 深度優(yōu)先搜索 有界深度優(yōu)先搜索 ： 引入搜索深度限制值 d， 使深度優(yōu)先搜索過(guò)程具有完備性 。 (5) 把 n的所有后繼節(jié)點(diǎn)放到 OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到 n的指針。 (2) 如果 OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。這時(shí)，能夠重現(xiàn)從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的這條成功路徑，其辦法是從目標(biāo)節(jié)點(diǎn)按指針向 S返回追溯。 (9) GO LOOP。把 M的這些成員加進(jìn) OPEN表。 (5) 若 n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖 G中沿著指針從 n到 S這條路徑而得到的 (指針將在第 7步中設(shè)置 )。 (2) 建立一個(gè)叫做 CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫(kù)和滿足終止條件的數(shù)據(jù)庫(kù)。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問(wèn)題就等價(jià)于求得圖中的一條路徑問(wèn)題。 (3) LOOP：若 OPEN表是空表，則失敗退出。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 5/79 盲目搜索 圖搜索策略 (GRAPHSEARCH)的一般過(guò)程 (6) 擴(kuò)展節(jié)點(diǎn) n，同時(shí)生成不是 n的祖先的那些后繼節(jié)點(diǎn)的集合M。對(duì)已經(jīng)在 OPEN或 CLOSED表上的每一個(gè) M成員，確定是否需要更改通到 n的指針?lè)较颉? 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 6/79 盲目搜索 節(jié)點(diǎn) 父輩節(jié)點(diǎn) 圖搜索策略 （ 1） OPEN表與 CLOSE表 OPEN表 CLOSED表 編號(hào) 節(jié)點(diǎn) 父輩節(jié)點(diǎn) 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 7/79 盲目搜索 圖搜索策略 3. 搜索圖與搜索樹(shù) 搜索過(guò)程框圖 開(kāi) 始 初始化 ： S 放入 OPEN 表 ， CLOES 表置空 , n = 1 OPEN 表中的第一個(gè)結(jié)點(diǎn) n 移至 CLOSE 表 若 n 的后繼未曾在搜索圖 G 中出現(xiàn) ， 則將其放入 OPEN 表的末端 ， 并提供返回結(jié)點(diǎn) n 的指針 , 置 n = n + 1 根據(jù)后繼結(jié)點(diǎn)在搜索圖 G 中的出現(xiàn)情況 修改指針?lè)较? 依某種準(zhǔn)則重新排序 OPEN 表 失敗 成功 N Y N OPEN 為空表 NULL ？ n = 目標(biāo)結(jié)點(diǎn) D 嗎 ? Y 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 8/79 盲目搜索 圖搜索策略 ： 圖搜索過(guò)程的第 8步對(duì) OPEN表上的節(jié)點(diǎn)進(jìn)行排序，以便能夠從中選出一個(gè)“最好”的節(jié)點(diǎn)作為第 4步擴(kuò)展用。當(dāng)搜索樹(shù)不再剩有未被擴(kuò)展的端節(jié)點(diǎn)時(shí)，過(guò)程就以失敗告終 (某些節(jié)點(diǎn)最終可能沒(méi)有后繼節(jié)點(diǎn)，所以 OPEN表可能最后變成空表 )。 (3) 把第一個(gè)節(jié)點(diǎn) (節(jié)點(diǎn) n)從 OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (6) 如果 n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第 (2)步。 設(shè)定搜索深度限制 d=5， 問(wèn)題同深度優(yōu)先算法中的八數(shù)碼問(wèn)題(2)。 如果所有的連接弧線具有相等的代價(jià)，那么等代價(jià)算法就簡(jiǎn)化為寬度優(yōu)先搜索算法 。 （ 2）在擴(kuò)展一個(gè)節(jié)點(diǎn)的過(guò)程中，用于確定要生成哪一個(gè)或哪幾個(gè)后繼節(jié)點(diǎn)，避免盲目生成所有可能節(jié)點(diǎn)。 建立估價(jià)函數(shù)的一般方法：試圖確定一個(gè)處在最佳路徑上的節(jié)點(diǎn)的概率；提出任意節(jié)點(diǎn)與目標(biāo)集之間的距離量度或差別量度；或者在棋盤式的博弈和難題中根據(jù)棋局的某些特點(diǎn)來(lái)決定棋局的得分?jǐn)?shù)。這種搜索方法叫做有序搜索 或 最佳優(yōu)先搜索 (bestfirst search)，而其算法就叫做有序搜索算法 或 最佳優(yōu)先算法 。結(jié)果有幾個(gè)節(jié)點(diǎn)合格，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn) i。對(duì)于 i的每一個(gè)后繼節(jié)點(diǎn) j： (a) 計(jì)算 f(j)。如果新的 f值較小，則 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 24/79 啟發(fā)式搜索 有序搜索 (i) 以此新值取代舊值。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 25/79 啟發(fā)式搜索 有序搜索 開(kāi)始 把 S放入 OPEN表 OPEN為空表？ 失敗 選取 OPEN表中 f值最小 的節(jié)點(diǎn) i，放入 CLOSED表 i=Sg？ 成功 是 是 擴(kuò)展 i得后繼節(jié)點(diǎn) j，計(jì)算 f(j)，提 供返回 i的指針，利用 f(j)對(duì) OPEN 表重新排序調(diào)整父子關(guān)系及指針 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 26/79 啟發(fā)式搜索 有序搜索 寬度優(yōu)先搜索、等代價(jià)搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。如果沒(méi)有適用的準(zhǔn)確的希望量度，那么 f的選擇將涉及兩個(gè)方面的內(nèi)容：一方面是一個(gè)時(shí)間和空間之間的折衷方案；另一方面是保證有一個(gè)最優(yōu)的解或任意解。 1. A*算法的估價(jià)函數(shù) k(ni， nj)：表示任意兩個(gè)節(jié)點(diǎn) ni和 nj之間最小代價(jià)路徑的實(shí)際代價(jià) (對(duì)于兩節(jié)點(diǎn)間沒(méi)有通路的節(jié)點(diǎn)，函數(shù) k沒(méi)有定義 )。 定義函數(shù) f*， f*(n)=g*(n)+h*(n) 使得在任一節(jié)點(diǎn) n上其函數(shù)值 f*(n)就是從節(jié)點(diǎn) S到節(jié)點(diǎn) n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn) n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和。 h(n)：對(duì) h*(n)的估計(jì)，依賴于有關(guān)問(wèn)題的領(lǐng)域的啟發(fā)信息。 定義 在 A算法中，如果對(duì)所有的 x存在 h(x)≤h*(x),則稱 h(x)為 h*(x)的下界，它表示某種偏于保守的估計(jì)。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 33/79 啟發(fā)式搜索 A*算法 開(kāi)始 把 S放入 OPEN表 ,記 f=h OPEN為空表？ 失敗 選取 OPEN表中未設(shè)置過(guò)的具有最小 f值 的節(jié)點(diǎn) BESTNODE，放入 CLOSED表 BESTNODE=Sg？ 成功 是 是 擴(kuò)展 BESTNODE，產(chǎn)生后繼節(jié)點(diǎn) SUVVESSOR 建立從 SUCCESSOR返回 BESTNODE的指針 計(jì)算 g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR) SUCCESSOR∈ OPEN？ 否 是 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 34/79 啟發(fā)式搜索 A*算法 把 SECCESSOR放入 OPEN表， 加入 BESTNODE的后裔表 g(SUCCESSOR)g(OLD)？ 否 重新確定 OLD的父輩節(jié)點(diǎn)為 BESTNODE， 并修正父輩節(jié)點(diǎn)的 g值和 f值，記下 g(OLD) SUCCESSOR∈ CLOSED？ 否 是 SECCESSOR=OLD，把它添到 BESTNODE的后繼節(jié)點(diǎn)表中 是 否 計(jì)算 f值 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 35/79 博弈樹(shù)搜索 博弈概述 何謂博弈？ 博弈就是下棋、打牌、競(jìng)技、戰(zhàn)爭(zhēng)等一類競(jìng)爭(zhēng)性智能活動(dòng)。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 36/79 博弈樹(shù)搜索 博弈概述 參加博弈的各方都希望己方取得勝利。 博弈樹(shù)有如下特點(diǎn)： （ 1）博弈的初始格局是初始節(jié)點(diǎn)。此外，所有其它的節(jié)點(diǎn)則是具有風(fēng)險(xiǎn)的中間節(jié)點(diǎn)。在圖中，方框形狀“□”表示是 MAX方控制的或節(jié)點(diǎn)；圓形框形狀“○”表示 MIN方控制與節(jié)點(diǎn)。這樣計(jì)算出的父輩節(jié)點(diǎn)的等分稱為倒推值。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 40/79 4 1 1 8 1 2 5 0 4 9 1 5 11 4 3 1 –1 5 8 10 1 4 2 5 5 9 6 0 6 4 10 –9 1 12 5 MAXMIN博弈樹(shù)的倒推值計(jì)算 h(S0)=？ 4 8 2 0 1 4 1 博弈樹(shù)搜索 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 41/79 博弈樹(shù)搜索 αβ剪枝技術(shù) 基本思想：邊生成博弈樹(shù)邊估算各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無(wú)必要再擴(kuò)展的子節(jié)點(diǎn)。這一過(guò)程稱為 β 剪枝。 （ 2）一個(gè) MIN節(jié)點(diǎn)的 β 值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。生物染色體用數(shù)學(xué)方式或計(jì)算機(jī)方式來(lái)體現(xiàn)就是一串?dāng)?shù)碼，仍叫染色體，有時(shí)也叫個(gè)體；適應(yīng)能力用對(duì)應(yīng)一個(gè)染色體的數(shù)值來(lái)衡量；染色體的選擇或淘汰問(wèn)題是按求最大還是最小問(wèn)題來(lái)進(jìn)行。從 1985年起，國(guó)際上開(kāi)始陸續(xù)舉行遺傳算法的國(guó)際會(huì)議，后來(lái)又更名為進(jìn)化計(jì)算。遺傳算法具有以下特點(diǎn)： (1) 遺傳算法是對(duì)參數(shù)集合的編碼而非針對(duì)參數(shù)本身進(jìn)行進(jìn)化； (2) 遺傳算法是從問(wèn)題解的編碼組開(kāi)始而非從單個(gè)解開(kāi)始搜索； (3) 遺傳算法利用目標(biāo)函數(shù)的適應(yīng)度這一信息而非利用導(dǎo)數(shù)或其它輔助信息來(lái)指導(dǎo)搜索； (4) 遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進(jìn)行隨機(jī)操作。從此，遺傳算法始才得到學(xué)術(shù)界普遍關(guān)注與認(rèn)可。 1. 編碼與解碼 許多應(yīng)用問(wèn)題的結(jié)構(gòu)很復(fù)雜，但可以化為簡(jiǎn)單的位串形式編碼表示。按一條回路中城市的次序進(jìn)行編碼。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 54/79 遺傳算法 遺傳算法的基本原理 2. 適應(yīng)度函數(shù) 為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)（ fitness function）。改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作，以達(dá)到更高的效率。 產(chǎn)生一個(gè) 1~7之間的隨機(jī)數(shù) c，假設(shè)為 3，則將 P1和 P2的低 3位交換 1 0 0 0 1 1 1 0 P1： 1 1 0 1 1 0 0 1 P2： 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 57/79 遺傳算法 遺傳算法的基本原理 3. 遺傳操作 1 0 0 0 1 1 1 0 P1： 1 1 0 1 1 0 0 1 P2： 1 0 0 0 1 0 0 1 1 1 0 1 1 1 1 0