狀態(tài)空間搜索策略(編輯修改稿)
2025-02-03 06:36 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 可能有無(wú)窮分支，如果誤入無(wú)窮分支（即深度無(wú)限），則不可能找到目標(biāo)節(jié)點(diǎn) ? 策略不是完備的 ? 找到的解是不一定最優(yōu)解最短路徑 ) 等代價(jià)搜索 ? 定義 是寬度優(yōu)先搜索的一種推廣，不是沿著等長(zhǎng)度路徑斷層進(jìn)行擴(kuò)展，而是沿著等代價(jià)路徑斷層進(jìn)行擴(kuò)展。 搜索樹(shù)中每條連接弧線上的有關(guān)代價(jià) ,表示時(shí)間、距離等花費(fèi)。 ? 算法 若所有連接弧線具有相等代價(jià)，則簡(jiǎn)化為寬度優(yōu)先搜索算法。 開(kāi)始 把 S放入 OPEN表 OPEN表為空表？ 把具有最小 g(i)值的節(jié)點(diǎn) i從 OPEN表移至 CLOSED表 是否有后繼節(jié)點(diǎn) 為目標(biāo)節(jié)點(diǎn)？ 失敗 成功 圖 等代價(jià)搜索算法框圖 是 否 是 否 S是否目標(biāo)節(jié)點(diǎn) ？ 是 成功 擴(kuò)展 i，計(jì)算其后繼節(jié)點(diǎn) j的 g(j)，并把后繼節(jié)點(diǎn)放入 OPEN表 否 令 g(s)=0 國(guó)際象棋對(duì)弈程序 :深藍(lán) 開(kāi)發(fā)者 : IBM 的 Murry Campbell, FengHsiung Hsu 和 Joseph Hoane ? 采用 30個(gè) IBM RS/6000處理器來(lái)運(yùn)行軟件搜索 ? 使用 480個(gè)定制 VLSI國(guó)際象棋處理器執(zhí)行生成行棋的功能 ﹑ 樹(shù)的最后幾層的 ”硬件搜索 ” 以及對(duì)葉節(jié)點(diǎn)的評(píng)價(jià) . ? 每秒平均搜索 ，峰值時(shí)每秒鐘搜索 33億個(gè)節(jié)點(diǎn) . 每走一步至多能夠預(yù)先計(jì)算 300億種個(gè)棋局 , 常規(guī)搜索深度是 14步 . ? 機(jī)器的核心算法是使用調(diào)換表的標(biāo)準(zhǔn)迭代深入 α β 搜索 , 而且對(duì)關(guān)鍵的點(diǎn)具備產(chǎn)生超越搜索深度的擴(kuò)展能力 ,在某些情況下可以達(dá)到 40層的深度 . ? 評(píng)價(jià)函數(shù)采用了超過(guò) 8000個(gè)特征 。使用一本有 4000個(gè)棋局的 ” 開(kāi)局手冊(cè) ” 以及一個(gè)存有 70萬(wàn)個(gè)大師級(jí)比賽棋譜的數(shù)據(jù)庫(kù) 。 使用一個(gè)大型殘局?jǐn)?shù)據(jù)庫(kù)保存已解決的棋局 . Video ? Deep Blue 15 years ? 卡斯帕羅夫 ? Windows 8 ? Kinect 問(wèn)題的提出 ? 窮舉算法 ? 可以解決狀態(tài)空間很小的簡(jiǎn)單問(wèn)題 ? 大空間無(wú)法勝任：組合爆炸 ? 組合爆炸 ? 64階梵塔： – 節(jié)點(diǎn)： 364=*1030 – 理論最短路徑： 2641=2*1019 ? 博弈 – 一字棋： 9！ = *105 – 西洋棋： 1078 – 國(guó)際象棋： 10120（ 極限并行速度 10104秒 /步，需 1016年 ） – 圍棋： 10761 啟發(fā)式搜索 啟發(fā)性信息 ? 按其用途劃分 , 啟發(fā)性信息可分為以下三類： – 用于擴(kuò)展節(jié)點(diǎn)的選擇 , 即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn) , 以免盲目擴(kuò)展 。 – 用于生成節(jié)點(diǎn)的選擇 ,即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn) ,以免盲目地生成過(guò)多無(wú)用節(jié)點(diǎn) 。 – 用于刪除節(jié)點(diǎn)的選擇 ,即用于決定應(yīng)刪除哪些無(wú)用節(jié)點(diǎn) , 以免造成進(jìn)一步的時(shí)空浪費(fèi) 。 啟發(fā)式搜索 ? 特點(diǎn)： 重排 OPEN表，選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展 ? 種類：有序搜索、 A*算法等 啟發(fā)式搜索策略和估價(jià)函數(shù) ?盲目搜索可能帶來(lái)組合爆炸 ?啟發(fā)式信息 用來(lái)加速搜索過(guò)程的有關(guān)問(wèn)題領(lǐng)域的特征信息。 ? 啟發(fā)函數(shù) – 啟發(fā)函數(shù)是用來(lái)估計(jì)搜索樹(shù)上節(jié)點(diǎn) x與目標(biāo)節(jié)點(diǎn) Sg接近程度的一種函數(shù) , 通常記為 h(x) – 定義 ? 一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的度量 ? 一個(gè)節(jié)點(diǎn)處于最佳路徑上的概率 ? 根據(jù)經(jīng)驗(yàn)的主觀打分 ? 估價(jià)函數(shù) 為獲得某些節(jié)點(diǎn) “ 希望 ” 的啟發(fā)信息，提供一個(gè)評(píng)定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上 。 f(n)—— 表示節(jié)點(diǎn) n的估價(jià)函數(shù)值 ? 應(yīng)用節(jié)點(diǎn) “ 希望 ” 程度（估價(jià)函數(shù)值）重排 OPEN表 有序搜索 ?實(shí)質(zhì)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1