搜索-基于狀態(tài)空間的搜索

《搜索-基于狀態(tài)空間的搜索》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第二章用以搜索狀態(tài)空間的結(jié)構(gòu)與策略內(nèi)容2.0簡(jiǎn)介2.1圖論2.2問題狀態(tài)空間的表示2.3狀態(tài)空間搜索的方向2.4一般圖搜索2.5常見的盲目式搜索技術(shù)用以搜索狀態(tài)空間的結(jié)構(gòu)與策略22.0簡(jiǎn)介什么是問題？283710514115964111412123487659101112151413?用以搜索狀態(tài)空間的結(jié)構(gòu)與策略32.0簡(jiǎn)介問題（現(xiàn)代認(rèn)知心理學(xué)）：在給定信息和目標(biāo)狀態(tài)之間有某些障礙需要加以克服的情境。①給定：有關(guān)問題條件的描述，即問題的起始狀態(tài)；②目標(biāo)：有關(guān)構(gòu)成問題結(jié)論的描述，即問題的目標(biāo)狀態(tài)；③障礙：無法直接到達(dá)目標(biāo)，必須通過一定的思維活

2、動(dòng)才能找到答案，達(dá)到目標(biāo)狀態(tài)。問題解決（信息加工觀點(diǎn)）：就是搜索問題空間，尋找一條從起始狀態(tài)通向目標(biāo)狀態(tài)的通路，或使用算子使起始狀態(tài)逐步過渡到目標(biāo)狀態(tài)。按解決問題所需的領(lǐng)域特有知識(shí)的多寡，問題求解系統(tǒng)可以劃分為兩大類：①知識(shí)貧乏系統(tǒng)：依靠搜索技術(shù)去解決問題。②知識(shí)豐富系統(tǒng)：依靠推理的識(shí)別技術(shù)解決問題。用以搜索狀態(tài)空間的結(jié)構(gòu)與策略42.0簡(jiǎn)介搜索人工智能所研究的對(duì)象大多是屬于結(jié)構(gòu)不良或非結(jié)構(gòu)化的問題。對(duì)于這些問題，一般很難獲得其全部信息，更沒有現(xiàn)成的算法可供求解使用。只能依靠經(jīng)驗(yàn)，利用已有知識(shí)逐步摸索求解。根據(jù)問題的實(shí)際情況，不斷尋找可利用知

3、識(shí)，從而構(gòu)造一條代價(jià)最小的推理路線，使問題得以解決的過程——搜索。對(duì)那些結(jié)構(gòu)性能較好，理論上有算法可依的問題，如果問題或算法的復(fù)雜性較高（如按指數(shù)形式增長(zhǎng)），由于受計(jì)算機(jī)在時(shí)間和空間上的限制，也無法付諸實(shí)用。——組合爆炸問題。用以搜索狀態(tài)空間的結(jié)構(gòu)與策略52.0簡(jiǎn)介搜索的分類①根據(jù)搜索過程是否使用啟發(fā)式信息盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息并不改變控制策略。由于搜索總是按預(yù)先規(guī)定的路線進(jìn)行，沒有考慮到問題本身的特性，因此這種搜索具有盲目性。啟發(fā)式搜索：搜索過程中加入與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望

4、的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。②根據(jù)問題的表示方式狀態(tài)空間搜索：基于問題到狀態(tài)空間表示求解問題所進(jìn)行的搜索。與／或樹搜索：基于問題的與／或樹表示利用問題歸約法來求解問題時(shí)所進(jìn)行的搜索。第六章用以搜索狀態(tài)空間的結(jié)構(gòu)與策略6內(nèi)容2.0簡(jiǎn)介2.1圖論2.2問題狀態(tài)空間的表示2.3狀態(tài)空間搜索的方向2.4一般圖搜索2.5常見的盲目式搜索技術(shù)用以搜索狀態(tài)空間的結(jié)構(gòu)與策略72.1圖論例1：從某王姓家族的四代中找王A的后代且其壽命為X的人王A：壽命47，有兒子王B1、王B3、王B2王B1：壽命77，有兒子王C1、王C2王B3：壽命52，有兒

5、子王D1王B2：壽命65，有兒子王E1、王E2王F1：壽命32王G1：壽命96王C2：壽命87，有兒子王F1王D1：壽命77，沒有兒子王E1：壽命57，有兒子王G1王E2：壽命92，有兒子王H1王C1：壽命27，沒有兒子王H1：壽命51用以搜索狀態(tài)空間的結(jié)構(gòu)與策略82.1圖論例1：從某王姓家族的四代中找王A的后代且其壽命為X的人用以搜索狀態(tài)空間的結(jié)構(gòu)與策略92.1圖論例2：哥尼斯堡七橋問題（瑞士數(shù)學(xué)家-歐拉）用以搜索狀態(tài)空間的結(jié)構(gòu)與策略102.1圖論圖節(jié)點(diǎn)和連接這些節(jié)點(diǎn)的弧的集合。帶標(biāo)簽的有向圖用以搜索狀態(tài)空間的結(jié)構(gòu)與策略112.1圖論有根

6、圖具有一個(gè)唯一節(jié)點(diǎn)（根），從這個(gè)節(jié)點(diǎn)到圖中所有節(jié)點(diǎn)都存在一條路徑。用以搜索狀態(tài)空間的結(jié)構(gòu)與策略122.1圖論樹兩個(gè)節(jié)點(diǎn)之間最多有一條路徑的圖。用以搜索狀態(tài)空間的結(jié)構(gòu)與策略13內(nèi)容2.0簡(jiǎn)介2.1圖論2.2問題狀態(tài)空間的表示2.3狀態(tài)空間搜索的方向2.4一般圖搜索2.5常見的盲目式搜索技術(shù)用以搜索狀態(tài)空間的結(jié)構(gòu)與策略142.2問題狀態(tài)空間的表示狀態(tài)空間表示法用來表示問題及其搜索過程的一種形式化方法。①狀態(tài)②操作③狀態(tài)空間⑴什么是狀態(tài)？狀態(tài)（State）是表示問題求解過程中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)：Sk＝｛Sk0，Sk1，…｝對(duì)每一個(gè)分量給予確

7、定的值時(shí)，得到一個(gè)具體的狀態(tài)。任何一種類型的數(shù)據(jù)結(jié)構(gòu)都可以用來描述狀態(tài)，只要它有利于問題求解，就可以選用。用以搜索狀態(tài)空間的結(jié)構(gòu)與策略152.2問題狀態(tài)空間的表示⑵什么是操作？操作（Operator）——算符當(dāng)對(duì)一個(gè)問題狀態(tài)使用某個(gè)可用操作時(shí)，它將引起該狀態(tài)中某些分量值的變化，從而使問題從一個(gè)具體狀態(tài)變?yōu)榱硪粋€(gè)具體狀態(tài)。操作可以是一個(gè)機(jī)械步驟、一個(gè)運(yùn)算、一條規(guī)則或一個(gè)過程。操作可理解為狀態(tài)集合上的一個(gè)函數(shù)，它描述了狀態(tài)之間的關(guān)系。State1State2Operator用以搜索狀態(tài)空間的結(jié)構(gòu)與策略162.2問題狀態(tài)空間的表示⑶什么是狀態(tài)空間

8、？狀態(tài)空間（Statespace）用來描述一個(gè)問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。狀態(tài)空間常用一個(gè)三元組表示：（S，F(xiàn)，G）S：為問題的所有初始狀態(tài)的集合；F：為操作的集合