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