經(jīng)典邏輯推理3

1、模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/61人工智能導(dǎo)論經(jīng)典邏輯推理3模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/62課程進(jìn)度人工智能原理與應(yīng)用人工智能原理與應(yīng)用前言前言緒論緒論數(shù)學(xué)數(shù)學(xué)基礎(chǔ)基礎(chǔ)知識(shí)知識(shí)表示表示(1)知識(shí)知識(shí)表示表示(2)經(jīng)典經(jīng)典邏輯邏輯推理推理(1)經(jīng)典經(jīng)典邏輯邏輯推理推理(2)經(jīng)典經(jīng)典邏輯邏輯推理推理(3)經(jīng)典經(jīng)典邏輯邏輯推理推理(4)課程課程設(shè)計(jì)設(shè)計(jì)(1)課程課程設(shè)計(jì)設(shè)計(jì)(2)不確不確定推定推理理(1)不確不確定推定推理理(2)不確不確定推定推理

2、理(3)經(jīng)典經(jīng)典邏輯邏輯推理推理(5)模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/63本節(jié)課的知識(shí)框架搜索策略搜索策略什么是搜索什么是搜索狀態(tài)空間表示法狀態(tài)空間表示法狀態(tài)空間的一般過(guò)程狀態(tài)空間的一般過(guò)程廣度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/64搜索的作用搜索的作用知識(shí)的表示知識(shí)的表示邏輯推理邏輯推理知知識(shí)識(shí)搜搜索索知識(shí)的表示知識(shí)的表示指導(dǎo)了推理指導(dǎo)了推理的基本過(guò)程的基本過(guò)程知識(shí)的搜索在知識(shí)的搜索在這個(gè)過(guò)程的作用這個(gè)過(guò)程

3、的作用反饋搜索信息反饋搜索信息指導(dǎo)搜索過(guò)程指導(dǎo)搜索過(guò)程知識(shí)的獲取,推理技術(shù) ,搜索技術(shù) ,知識(shí)的表示 模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/65搜索的作用搜索的作用知識(shí)的表示形式知識(shí)的表示形式邏輯推理邏輯推理搜索策略搜索策略體現(xiàn)了知識(shí)的組織形式體現(xiàn)了知識(shí)的組織形式加快和糾正求解過(guò)程加快和糾正求解過(guò)程模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/66本節(jié)課的知識(shí)框架搜索策略搜索策略什么是搜索什么是搜索狀態(tài)空間表示法狀態(tài)空間表示法狀態(tài)空間的一般過(guò)程狀態(tài)空間的一般過(guò)程廣度優(yōu)

4、先搜索廣度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/67搜索的基本概念什么是搜索什么是搜索 人工智能所要解決的大部分問(wèn)題是結(jié)構(gòu)不良或非結(jié)構(gòu)化的人工智能所要解決的大部分問(wèn)題是結(jié)構(gòu)不良或非結(jié)構(gòu)化的問(wèn)題，對(duì)這樣的問(wèn)題一般不存在成熟的求解算法可供利用，問(wèn)題，對(duì)這樣的問(wèn)題一般不存在成熟的求解算法可供利用，而只能是利用已有的知識(shí)一步步摸索著前進(jìn)。而只能是利用已有的知識(shí)一步步摸索著前進(jìn)。 在此過(guò)程中，存在著如何尋找可用知識(shí)的問(wèn)題，即如何確在此過(guò)程中，存在著如何尋找可用知識(shí)的問(wèn)題，即如何確定推理路線，使其付出的代價(jià)

5、盡可能的少，而問(wèn)題又能得定推理路線，使其付出的代價(jià)盡可能的少，而問(wèn)題又能得到較好的解決。到較好的解決。例如例如: 在正向推理中，對(duì)已知的初始事實(shí)，需要在知識(shí)庫(kù)中尋找可使用的知識(shí)，在正向推理中，對(duì)已知的初始事實(shí)，需要在知識(shí)庫(kù)中尋找可使用的知識(shí)，這就存在按何種線路進(jìn)行尋找的問(wèn)題。這就存在按何種線路進(jìn)行尋找的問(wèn)題。 另外，可能存在多條線路都可實(shí)現(xiàn)對(duì)問(wèn)題的求解，這就又出現(xiàn)按哪一條線另外，可能存在多條線路都可實(shí)現(xiàn)對(duì)問(wèn)題的求解，這就又出現(xiàn)按哪一條線路進(jìn)行求解以獲得較高的運(yùn)行效率的問(wèn)題。路進(jìn)行求解以獲得較高的運(yùn)行效率的問(wèn)題。像這樣根據(jù)問(wèn)題的實(shí)際情況不斷尋找可利用的知識(shí)，從而像這樣根據(jù)問(wèn)題的實(shí)際情況不斷尋找可

6、利用的知識(shí)，從而構(gòu)造一條代價(jià)較少的推理路線，使問(wèn)題得到圓滿解決的過(guò)構(gòu)造一條代價(jià)較少的推理路線，使問(wèn)題得到圓滿解決的過(guò)程稱為搜索。程稱為搜索。模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/68搜索分類搜索分類搜索分為盲目搜索和啟發(fā)式搜索。搜索分為盲目搜索和啟發(fā)式搜索。 盲目搜索盲目搜索按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。這種搜索具有盲目獲得的中間信息不用來(lái)改進(jìn)控制策略。這種搜索具有盲目性，效率不高，不便于復(fù)雜問(wèn)題的求解。性，效率不高，不便于復(fù)雜問(wèn)題的求解。 啟發(fā)式

7、搜索啟發(fā)式搜索在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。過(guò)程并找到最優(yōu)解。模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/69本節(jié)課的知識(shí)框架搜索策略搜索策略什么是搜索什么是搜索狀態(tài)空間表示法狀態(tài)空間表示法狀態(tài)空間的一般過(guò)程狀態(tài)空間的一般過(guò)程廣度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021

8、/8/610 用搜索策略求解問(wèn)題，首先要解決的問(wèn)題也是：用搜索策略求解問(wèn)題，首先要解決的問(wèn)題也是：用什么樣的形式把問(wèn)題表示出來(lái)用什么樣的形式把問(wèn)題表示出來(lái). 一般來(lái)說(shuō)，有一般來(lái)說(shuō)，有兩種方法：兩種方法：狀態(tài)空間表示法；狀態(tài)空間表示法；與與/或樹(shù)表示法；或樹(shù)表示法；模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/611狀態(tài)空間表示法狀態(tài)空間表示法 狀態(tài)空間表示法是用來(lái)表示問(wèn)題及其搜索過(guò)程的一種方法，狀態(tài)空間表示法是用來(lái)表示問(wèn)題及其搜索過(guò)程的一種方法，它是人工智能中最基本的形式化方法。它是人工智能中最基本的形式化方法。 狀態(tài)空間表示法是用狀

9、態(tài)空間表示法是用“狀態(tài)狀態(tài)”和和“算符算符”來(lái)表示問(wèn)題的來(lái)表示問(wèn)題的一種方法。其中一種方法。其中: “狀態(tài)狀態(tài)”用以描述問(wèn)題求解過(guò)程中不同時(shí)刻的狀況；用以描述問(wèn)題求解過(guò)程中不同時(shí)刻的狀況； “算符算符”表示對(duì)狀態(tài)的操作，算符的每一次使用就表示對(duì)狀態(tài)的操作，算符的每一次使用就使問(wèn)題由一種使問(wèn)題由一種 狀態(tài)變換為另一種狀態(tài)狀態(tài)變換為另一種狀態(tài); “ 解解 ” 當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時(shí)，由初始狀態(tài)到目標(biāo)狀當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就是問(wèn)題的一個(gè)解。態(tài)所用算符的序列就是問(wèn)題的一個(gè)解。模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/

10、8/612狀態(tài)空間表示法狀態(tài)空間表示法模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/613狀態(tài)空間表示法狀態(tài)空間表示法模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/614狀態(tài)空間表示法狀態(tài)空間表示法上述問(wèn)題的狀態(tài)空間上述問(wèn)題的狀態(tài)空間“三元組三元組”為：為： （S5, f1,f2,f3, s0,s7） 相應(yīng)的狀態(tài)空間圖：相應(yīng)的狀態(tài)空間圖：從圖中看出：從圖中看出：從從S5不可能經(jīng)三次翻轉(zhuǎn)到不可能經(jīng)三次翻轉(zhuǎn)到達(dá)達(dá)S0, 從從S5 可經(jīng)三次翻轉(zhuǎn)到達(dá)可經(jīng)三次翻轉(zhuǎn)到達(dá)S7 , 且有七種

11、操作方式。且有七種操作方式。模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/615本節(jié)課的知識(shí)框架搜索策略搜索策略什么是搜索什么是搜索狀態(tài)空間表示法狀態(tài)空間表示法狀態(tài)空間的一般過(guò)程狀態(tài)空間的一般過(guò)程廣度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/616狀態(tài)空間的一般過(guò)程狀態(tài)空間的一般過(guò)程 .給出初始狀態(tài)（初始節(jié)點(diǎn)）；給出初始狀態(tài)（初始節(jié)點(diǎn)）； .選擇選擇適用的算符對(duì)其進(jìn)行操作，生成一組選擇選擇適用的算符對(duì)其進(jìn)行操作，生成一組子狀態(tài)子

12、狀態(tài)( (或稱后繼狀態(tài)、后繼節(jié)點(diǎn)、子節(jié)點(diǎn)或稱后繼狀態(tài)、后繼節(jié)點(diǎn)、子節(jié)點(diǎn)) )； .檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問(wèn)題的解；若不出現(xiàn)，則按某種索成功，找到了問(wèn)題的解；若不出現(xiàn)，則按某種搜索策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)搜索策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)。前狀態(tài)。 重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)或者不再有可重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及算符時(shí)為止。供操作的狀態(tài)及算符時(shí)為止。模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/617狀態(tài)

13、空間的一般過(guò)程狀態(tài)空間的一般過(guò)程(4) (4) 搜索過(guò)程中要用到的兩個(gè)數(shù)據(jù)結(jié)構(gòu)搜索過(guò)程中要用到的兩個(gè)數(shù)據(jù)結(jié)構(gòu) 用于存放剛生成的節(jié)點(diǎn)。對(duì)于不同的搜索策略，節(jié)點(diǎn)在用于存放剛生成的節(jié)點(diǎn)。對(duì)于不同的搜索策略，節(jié)點(diǎn)在OPENOPEN表中的排列順序表中的排列順序是不同的。是不同的。 用于存放將要擴(kuò)展或者已擴(kuò)展的節(jié)點(diǎn)，所謂對(duì)節(jié)點(diǎn)進(jìn)行用于存放將要擴(kuò)展或者已擴(kuò)展的節(jié)點(diǎn)，所謂對(duì)節(jié)點(diǎn)進(jìn)行“擴(kuò)展擴(kuò)展”是指：用是指：用合適的算符對(duì)該節(jié)點(diǎn)進(jìn)行操作，生成一組子節(jié)點(diǎn)。合適的算符對(duì)該節(jié)點(diǎn)進(jìn)行操作，生成一組子節(jié)點(diǎn)。狀態(tài)節(jié)狀態(tài)節(jié)點(diǎn)點(diǎn)父節(jié)父節(jié)點(diǎn)點(diǎn)OPEN表表編號(hào)編號(hào)狀態(tài)節(jié)狀態(tài)節(jié)點(diǎn)點(diǎn)父節(jié)父節(jié)點(diǎn)點(diǎn)CLOSED表表模式識(shí)別與智能系統(tǒng)研究所

14、模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/618狀態(tài)空間的一般過(guò)程狀態(tài)空間的一般過(guò)程5) 狀態(tài)空間法搜索策略狀態(tài)空間法搜索策略 廣度優(yōu)先搜索廣度優(yōu)先搜索 深度優(yōu)先搜索深度優(yōu)先搜索 有界深度優(yōu)先搜索有界深度優(yōu)先搜索 代價(jià)樹(shù)的廣度優(yōu)先搜索代價(jià)樹(shù)的廣度優(yōu)先搜索 代價(jià)樹(shù)的深度優(yōu)先搜索代價(jià)樹(shù)的深度優(yōu)先搜索 （以上屬于盲目搜索策略）（以上屬于盲目搜索策略） 局部擇優(yōu)搜索局部擇優(yōu)搜索 全局擇優(yōu)搜索全局擇優(yōu)搜索 （以上搜索屬于啟發(fā)式搜索）（以上搜索屬于啟發(fā)式搜索）模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/6

15、19本節(jié)課的知識(shí)框架搜索策略搜索策略什么是搜索什么是搜索狀態(tài)空間表示法狀態(tài)空間表示法狀態(tài)空間的一般過(guò)程狀態(tài)空間的一般過(guò)程廣度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/620廣度優(yōu)先搜索(1) 基本思想基本思想 從初始節(jié)點(diǎn)開(kāi)始，按照某種生成規(guī)則（算符）逐步生成下一級(jí)各子節(jié)點(diǎn)，從初始節(jié)點(diǎn)開(kāi)始，按照某種生成規(guī)則（算符）逐步生成下一級(jí)各子節(jié)點(diǎn)，順序（先生成的子節(jié)點(diǎn)優(yōu)先檢查，優(yōu)先擴(kuò)展）地檢查是否出現(xiàn)目標(biāo)節(jié)點(diǎn)，在順序（先生成的子節(jié)點(diǎn)優(yōu)先檢查，優(yōu)先擴(kuò)展）地檢查是否出現(xiàn)目標(biāo)節(jié)點(diǎn)，在該級(jí)全部節(jié)點(diǎn)中沿廣度進(jìn)

16、行該級(jí)全部節(jié)點(diǎn)中沿廣度進(jìn)行“橫向橫向”掃描，即：沿掃描，即：沿“廣度廣度”遍歷所有節(jié)點(diǎn)，遍歷所有節(jié)點(diǎn)，故稱故稱“廣度優(yōu)先搜索法廣度優(yōu)先搜索法”。 (2) 廣度優(yōu)先搜索法搜索過(guò)程廣度優(yōu)先搜索法搜索過(guò)程 .把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放人放人OPEN表，若表，若S0為目標(biāo)節(jié)點(diǎn)，則得到問(wèn)題的解，退為目標(biāo)節(jié)點(diǎn)，則得到問(wèn)題的解，退出；出； .如果如果OPEN表為空，則問(wèn)題無(wú)解，退出；表為空，則問(wèn)題無(wú)解，退出； .把把OPEN表的第一個(gè)節(jié)點(diǎn)表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)記為節(jié)點(diǎn)n)取出放入取出放入CLOSED表；表； .考察節(jié)點(diǎn)考察節(jié)點(diǎn)n，若節(jié)點(diǎn)，若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第步；步； .擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)

17、n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入0PEN表的尾部表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針；置指向父節(jié)點(diǎn)的指針； .如果如果n的任一個(gè)后繼節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則找到問(wèn)題的解，成功退出，否的任一個(gè)后繼節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則找到問(wèn)題的解，成功退出，否則轉(zhuǎn)向第則轉(zhuǎn)向第步。步。模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/621開(kāi)始開(kāi)始把把S0送入送入OPEN表表 把把OPEN表的第一個(gè)節(jié)點(diǎn)表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)記為節(jié)點(diǎn)n) 從表中移出，放入從表中移出，放入CLOSED表表 OPEN表為空？表為空？ 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n

18、,將其子節(jié)點(diǎn)放入將其子節(jié)點(diǎn)放入，并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針。的指針。 是否有任何后繼是否有任何后繼 節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？ 節(jié)點(diǎn)節(jié)點(diǎn)n可擴(kuò)展？可擴(kuò)展？失敗，退出失敗，退出成功，退出成功，退出YNYNYNS0為目標(biāo)節(jié)點(diǎn)？為目標(biāo)節(jié)點(diǎn)？ 成功，退出成功，退出YN模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/622狀態(tài)節(jié)狀態(tài)節(jié)點(diǎn)點(diǎn)父節(jié)父節(jié)點(diǎn)點(diǎn)OPEN表表編號(hào)編號(hào)狀態(tài)節(jié)狀態(tài)節(jié)點(diǎn)點(diǎn)父節(jié)父節(jié)點(diǎn)點(diǎn)CLOSED表表S012S012634 5S012634 5789(a)(b)(c)(d)S0S01121200

19、034203356789411112233445S010203141Sg(9)S0491模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/623廣度優(yōu)先搜索例：例： 重排九宮問(wèn)題。在重排九宮問(wèn)題。在3X3的方格棋盤上放置分別標(biāo)有數(shù)字的方格棋盤上放置分別標(biāo)有數(shù)字1，2，3，4，5，6， 7，8的八張牌，初始狀態(tài)為的八張牌，初始狀態(tài)為50，目標(biāo)狀態(tài)為，目標(biāo)狀態(tài)為S，如下圖所示。，如下圖所示。 可使用的算符有：可使用的算符有： 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移 即，它們只允許把位于空格左，上，右，下邊

20、的牌移入空格。即，它們只允許把位于空格左，上，右，下邊的牌移入空格。 要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。 應(yīng)用廣度優(yōu)先搜索，可得到如圖所示的搜索樹(shù)。應(yīng)用廣度優(yōu)先搜索，可得到如圖所示的搜索樹(shù)。2 8 31 47 6 51 2 38 47 6 5模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/624 由圖可以看出，解的路徑是由圖可以看出，解的路徑是: S03 8 16 26 (Sg) 廣度優(yōu)先搜索的盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許廣度優(yōu)先搜索的盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將

21、會(huì)產(chǎn)生許 多無(wú)用節(jié)點(diǎn)，搜索效率低，這是它的缺點(diǎn)。多無(wú)用節(jié)點(diǎn)，搜索效率低，這是它的缺點(diǎn)。 只要問(wèn)題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的只要問(wèn)題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的 解，這是它的優(yōu)點(diǎn)。解，這是它的優(yōu)點(diǎn)。模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/625本節(jié)課的知識(shí)框架搜索策略搜索策略什么是搜索什么是搜索狀態(tài)空間表示法狀態(tài)空間表示法狀態(tài)空間的一般過(guò)程狀態(tài)空間的一般過(guò)程廣度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏

22、輯推理經(jīng)典邏輯推理-22021/8/626深度優(yōu)先搜索 (1) 基本思想基本思想 從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)S0開(kāi)始，按生成規(guī)則生成下一級(jí)各子節(jié)點(diǎn)，開(kāi)始，按生成規(guī)則生成下一級(jí)各子節(jié)點(diǎn)，若目標(biāo)節(jié)點(diǎn)未出現(xiàn)，則按若目標(biāo)節(jié)點(diǎn)未出現(xiàn)，則按“最晚生成的子節(jié)點(diǎn)優(yōu)先擴(kuò)展最晚生成的子節(jié)點(diǎn)優(yōu)先擴(kuò)展”的原則，生成再下一級(jí)的子節(jié)點(diǎn)，如此下去，沿著最晚生的原則，生成再下一級(jí)的子節(jié)點(diǎn)，如此下去，沿著最晚生成的子節(jié)點(diǎn)分支，逐級(jí)向成的子節(jié)點(diǎn)分支，逐級(jí)向“縱向縱向”深入發(fā)展，故稱為深入發(fā)展，故稱為“深深度優(yōu)先搜索法度優(yōu)先搜索法”。 (2) 深度優(yōu)先搜索法搜索過(guò)程深度優(yōu)先搜索法搜索過(guò)程 廣度優(yōu)先搜索是將節(jié)點(diǎn)廣度優(yōu)先搜索是將節(jié)點(diǎn)n的子節(jié)

23、點(diǎn)放入到的子節(jié)點(diǎn)放入到OPEN表的尾部，表的尾部，而深度優(yōu)先搜索是把節(jié)點(diǎn)而深度優(yōu)先搜索是把節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到的子節(jié)點(diǎn)放入到OPEN表的首表的首部。部。僅此一點(diǎn)不同，就使得搜索的路線完全不一樣。僅此一點(diǎn)不同，就使得搜索的路線完全不一樣。模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/627開(kāi)始開(kāi)始把把S0送入送入OPEN表表 把把OPEN表的第一個(gè)節(jié)點(diǎn)表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)記為節(jié)點(diǎn)n) 從從表中移出，放入表中移出，放入CLOSED表表 OPEN表為空？表為空？擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n,將其子節(jié)點(diǎn)放入將其子節(jié)點(diǎn)放入，并為，并為每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)每個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針。的指針。 是否有任何后繼是否有任何后繼 節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？ 節(jié)點(diǎn)節(jié)點(diǎn)n可擴(kuò)展？可擴(kuò)展？失敗，退出失敗，退出成功，退出成功，退出YNYNYNS0為目標(biāo)節(jié)點(diǎn)？為目標(biāo)節(jié)點(diǎn)？ 成功，退出成功，退出YN模式識(shí)別與智能系統(tǒng)研究所模式識(shí)別與智能系統(tǒng)研究所版權(quán)所有版權(quán)所有經(jīng)典邏輯推理經(jīng)典邏輯推理-22021/8/628狀態(tài)節(jié)狀態(tài)節(jié)點(diǎn)點(diǎn)父節(jié)父節(jié)點(diǎn)點(diǎn)OPEN表表編號(hào)編號(hào)狀態(tài)節(jié)狀態(tài)節(jié)點(diǎn)點(diǎn)父節(jié)父節(jié)點(diǎn)點(diǎn)CLOSED表表S012S01234(a)(b)(c)S0S012345S0123465S012346578(d)02022203242425