【正文】 4 32 5 61 4 87 32 5 61 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ò)程具有完備性 。 設(shè)定搜索深度限制 d=5， 問(wèn)題同深度優(yōu)先算法中的八數(shù)碼問(wèn)題(2)。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 16/79 盲目搜索 深度優(yōu)先搜索 2 8 31 6 47 512 8 31 6 47 5 22 8 31 6 7 5 432 81 6 37 5 442 8 31 6 4 7 52 8 31 47 6 52 8 31 4 7 6 52 8 3 1 47 6 52 31 8 47 6 52 3 1 8 47 6 5 2 31 8 47 6 51 2 3 8 47 6 52 3 41 8 7 6 51 2 37 8 4 6 51 2 38 47 6 52 3 41 87 6 52 3 41 8 57 6 2 81 4 37 6 52 4 81 37 6 52 81 4 37 6 52 8 1 4 37 6 52 8 31 4 57 6 2 8 31 4 5 7 62 8 31 57 4 62 8 31 4 57 6 8 32 1 67 5 42 8 37 1 6 5 42 8 3 1 67 5 42 8 31 67 5 42 8 31 5 67 4 2 31 8 67 5 42 3 1 8 67 5 42 8 31 5 6 7 42 8 31 5 67 4 2 81 6 37 5 42 6 81 37 5 42 81 6 37 5 42 31 8 67 5 452326273433282930 2524192021 15 1289DS1822 17 16 14 13 11 10 7 636 35 32 31合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 17/79 盲目搜索 深度優(yōu)先搜索 有界深度優(yōu)先算法步驟： (1)初始結(jié)點(diǎn) S放入堆棧 OPEN中； (2)若 OPEN為空，則搜索失敗，問(wèn)題無(wú)解； (3)彈出 OPEN中棧頂結(jié)點(diǎn) n，放入 CLOSE表中，并給出順序編號(hào) n； (4)若 n為目標(biāo)結(jié)點(diǎn) D，則搜索成功，問(wèn)題有解； (5)若 n的深度 d(n)=d，則轉(zhuǎn) (2) ； (6)若 n無(wú)子結(jié)點(diǎn)，即不可擴(kuò)展，轉(zhuǎn) (2) ； (7)擴(kuò)展結(jié)點(diǎn) n，將其所有子結(jié)點(diǎn)配上返回 n的指針，并壓入 OPEN堆棧，轉(zhuǎn) (2) 。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 18/79 盲目搜索 等代價(jià)搜索 寬度優(yōu)先搜索可被推廣用來(lái)解決尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價(jià)的路徑問(wèn)題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價(jià)搜索算法 。 等代價(jià)搜索中的幾個(gè)記號(hào) 起始節(jié)點(diǎn)記為 S； 從節(jié)點(diǎn) i到它的后繼節(jié)點(diǎn) j的連接弧線代價(jià)記為 c(i， j)； 起始節(jié)點(diǎn) S到任一節(jié)點(diǎn) i的路徑代價(jià)記為 g(i)。 如果所有的連接弧線具有相等的代價(jià)，那么等代價(jià)算法就簡(jiǎn)化為寬度優(yōu)先搜索算法 。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 19/79 啟發(fā)式搜索 盲目搜索的不足：效率低，耗費(fèi)空間與時(shí)間。 啟發(fā)式搜索：利用問(wèn)題域特性的信息（啟發(fā)信息）進(jìn)行搜索。 啟發(fā)式搜索策略 啟發(fā)式信息按用途分為三種： （ 1）用于確定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，避免盲目擴(kuò)展。 （ 2）在擴(kuò)展一個(gè)節(jié)點(diǎn)的過(guò)程中，用于確定要生成哪一個(gè)或哪幾個(gè)后繼節(jié)點(diǎn)，避免盲目生成所有可能節(jié)點(diǎn)。 （ 3）用于確定某些應(yīng)該從搜索樹(shù)中拋棄或修剪得節(jié)點(diǎn)。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 20/79 啟發(fā)式搜索 有序搜索（ ordered search）：利用第一種啟發(fā)信息，總是選擇“最有希望”的節(jié)點(diǎn)作為下一個(gè)被擴(kuò)展的節(jié)點(diǎn)。 估價(jià)函數(shù)（ evaluation function )：估算節(jié)點(diǎn)“希望”的量度，這種量度叫做估價(jià)函數(shù)。 建立估價(jià)函數(shù)的一般方法：試圖確定一個(gè)處在最佳路徑上的節(jié)點(diǎn)的概率；提出任意節(jié)點(diǎn)與目標(biāo)集之間的距離量度或差別量度；或者在棋盤(pán)式的博弈和難題中根據(jù)棋局的某些特點(diǎn)來(lái)決定棋局的得分?jǐn)?shù)。這些特點(diǎn)被認(rèn)為與向目標(biāo)節(jié)點(diǎn)前進(jìn)一步的希望程度有關(guān)。 f(n)—— 表示節(jié)點(diǎn) n的估價(jià)函數(shù)值 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 21/79 啟發(fā)式搜索 有序搜索 用估價(jià)函數(shù) f來(lái)排列 GRAPHSEARCH第 8步中 OPEN表上的節(jié)點(diǎn)。應(yīng)用某個(gè)算法 (例如等代價(jià)算法 )選擇 OPEN表上具有最小 f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。這種搜索方法叫做有序搜索 或 最佳優(yōu)先搜索 (bestfirst search)，而其算法就叫做有序搜索算法 或 最佳優(yōu)先算法 。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 22/79 啟發(fā)式搜索 有序搜索 有序狀態(tài)空間搜索算法： (1) 把起始節(jié)點(diǎn) S放到 OPEN表中，計(jì)算 f(S)并把其值與節(jié)點(diǎn) S聯(lián)系起來(lái)。 (2) 如果 OPEN是個(gè)空表，則失敗退出，無(wú)解。 (3) 從 OPEN表中選擇一個(gè) f值最小的節(jié)點(diǎn) i。結(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。 (4) 把節(jié)點(diǎn) i從 OPEN表中移出，并把它放入 CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 23/79 啟發(fā)式搜索 有序搜索 (5) 如果 i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。 (6) 擴(kuò)展節(jié)點(diǎn) i，生成其全部后繼節(jié)點(diǎn)。對(duì)于 i的每一個(gè)后繼節(jié)點(diǎn) j： (a) 計(jì)算 f(j)。 (b) 如果 j既不在 OPEN表中，又不在 CLOSED表中，則用估價(jià)函數(shù) f把它添入 OPEN表。從 j加一指向其父輩節(jié)點(diǎn) i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。 (c) 如果 j已在 OPEN表上或 CLOSED表上，則比較剛剛對(duì) j計(jì)算過(guò)的 f值和前面計(jì)算過(guò)的該節(jié)點(diǎn)在表中的 f值。如果新的 f值較小，則 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 24/79 啟發(fā)式搜索 有序搜索 (i) 以此新值取代舊值。 (ii) 從 j指向 i，而不是指向它的父輩節(jié)點(diǎn)。 (iii) 如果節(jié)點(diǎn) j在 CLOSED表中，則把它移回 OPEN表。 (7) 轉(zhuǎn)向 (2)，即 GO TO(2)。 合肥工業(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ù)的特例。對(duì)于寬度優(yōu)先搜索，選擇 f(i)作為節(jié)點(diǎn) i的深度。對(duì)于等代價(jià)搜索， f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn) i這段路徑的代價(jià)。 有序搜索的有效性直接取決于 f的選擇，如果選擇的 f不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。如果沒(méi)有適用的準(zhǔn)確的希望量度，那么 f的選擇將涉及兩個(gè)方面的內(nèi)容：一方面是一個(gè)時(shí)間和空間之間的折衷方案；另一方面是保證有一個(gè)最優(yōu)的解或任意解。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 27/79 啟發(fā)式搜索 有序搜索 例 ：八數(shù)碼難題 , 采用了簡(jiǎn)單的估價(jià)函數(shù) f(n)=d(n)+W(n) 其中： d(n)是搜索樹(shù)中節(jié)點(diǎn) n的深度； W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn) n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。因此，起始節(jié)點(diǎn)棋局 的 f值等于 0+4=4。 2 8 3 1 6 4 7 5 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 28/79 啟發(fā)式搜索 有序搜索 2 8 3 1 6 4 7 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 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 29/79 啟發(fā)式搜索 A*算法 A*算法是一種有序搜索算法，