【正文】 2022/8/21 1 第 3章 搜索策略 ? 問題求解系統(tǒng)劃分為兩大類 ? 知識(shí)貧乏系統(tǒng) ? 依靠 搜索技術(shù) 解決問題 ? 知識(shí)貧乏、缺乏針對(duì)性 ? 效率低 ? 知識(shí)豐富系統(tǒng) ? 依靠 推理技術(shù) 解決問題 ? 基于豐富知識(shí)的推理技術(shù)，直截了當(dāng) ? 效率高 2022/8/21 2 第 3章 搜索策略 ? 兩大類 搜索 技術(shù) : ? 一般圖搜索、啟發(fā)式搜索 ? 基于問題歸約的與或圖搜索 ? 兩種典型的 推理技術(shù) : ? 基于歸結(jié)的演繹推理 ? 歸結(jié)反演 ? 基于規(guī)則的演繹推理 ? 正向演繹推理 ? 逆向演繹推理 2022/8/21 3 引言 ?對(duì)于給定的問題，智能系統(tǒng)的行為一般是找到能夠達(dá)到所希望目標(biāo)的動(dòng)作序列 ，并使其所付出的 代價(jià)最小、性能最好 。 ?基于給定的問題，問題求解的第一步是目標(biāo)的表示。 ?搜索就是找到智能系統(tǒng)的 動(dòng)作序列的過程 。 2022/8/21 4 ? 搜索算法的輸入是 給定的問題 ，輸出是表示為動(dòng)作序列的方案 。 ? 一旦有了方案，就可以執(zhí)行該方案所給出的動(dòng)作了。（執(zhí)行階段） ? 因此，求解問題包括： ?目標(biāo)表示 ?搜索 ?執(zhí)行 2022/8/21 5 （ 1）初始狀態(tài)集合：定義了初始的環(huán)境。 （ 2）操作符集合：把一個(gè)問題從一個(gè)狀態(tài)變換為另一個(gè)狀態(tài)的動(dòng)作集合。 （ 3）目標(biāo)檢測(cè)函數(shù)：用來確定一個(gè)狀態(tài)是不是目標(biāo)。 （ 4）路徑費(fèi)用函數(shù)：對(duì)每條路徑賦予一定費(fèi)用的函數(shù)。 其中，初始狀態(tài)集合和操作符集合定義了問題的搜索空間。 ?一般給定問題就是確定該問題的一些基本信息，一個(gè)問題由 4部分組成 : 2022/8/21 6 ? 和通常的搜索空間不同，人工智能中大多數(shù)問題的狀態(tài)空間在問題求解之前不是全部知道的。 ? 在人工智能中，搜索問題一般包括兩個(gè)重要的問題： ?搜索什么 搜索什么通常指的就是目標(biāo)。 ?在哪里搜索 在哪里搜索就是 “ 搜索空間 ” 。搜索空間通常是指一系列狀態(tài)的匯集，因此稱為 狀態(tài)空間 。 2022/8/21 7 ?所以，人工智能中的搜索可以分成兩個(gè)階段： ? 狀態(tài)空間的生成階段 ? 在該狀態(tài)空間中對(duì)所求問題狀態(tài)的搜索 ?搜索可以根據(jù)是否使用啟發(fā)式信息分為 ?盲目搜索 ?啟發(fā)式搜索 2022/8/21 8 ?盲目搜索 只是可以區(qū)分出哪個(gè)是目標(biāo)狀態(tài)。 一般是按預(yù)定的搜索策略進(jìn)行搜索。 沒有考慮到問題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復(fù)雜問題的求解。 ?啟發(fā)式搜索 是在搜索過程中加入了 與問題有關(guān)的啟發(fā)式信息 ，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解并找到最優(yōu)解。 2022/8/21 9 ? 根據(jù)問題的表示方式分為 ? 狀態(tài)空間搜索 ? 與或圖搜索 狀態(tài)空間搜索是用狀態(tài)空間法來求解問題所進(jìn)行的搜索 與 /或圖搜索是指用問題規(guī)約方法來求解問題時(shí)所進(jìn)行的搜索。 2022/8/21 10 ? 考慮一個(gè)問題的狀態(tài)空間為一棵樹的形式。 ? 寬度優(yōu)先搜索 ? 深度優(yōu)先搜索 如果根節(jié)點(diǎn)首先擴(kuò)展，然后是擴(kuò)展根節(jié)點(diǎn)生成的所有節(jié)點(diǎn)，然后是這些節(jié)點(diǎn)的后繼，如此反復(fù)下去。 在樹的最深一層的節(jié)點(diǎn)中擴(kuò)展一個(gè)節(jié)點(diǎn)。只有當(dāng)搜索遇到一個(gè)死亡節(jié)點(diǎn)（非目標(biāo)節(jié)點(diǎn)并且是無法擴(kuò)展的節(jié)點(diǎn)）的時(shí)候，才返回上一層選擇其他的節(jié)點(diǎn)搜索。 2022/8/21 11 ? 無論是寬度優(yōu)先搜索還是深度優(yōu)先搜索，遍歷節(jié)點(diǎn)的順序一般都是固定的，即一旦搜索空間給定，節(jié)點(diǎn)遍歷的順序就固定了。這種類型的遍歷稱為 “ 確定性 ” 的，也就是 盲目搜索 。 ? 對(duì)于啟發(fā)式搜索，在計(jì)算每個(gè)節(jié)點(diǎn)的參數(shù)之前無法確定先選擇哪個(gè)節(jié)點(diǎn)擴(kuò)展 ，這種搜索一般也稱為 非確定 的。 2022/8/21 12 ? 完備性： ? 如果存在一個(gè)解答，該策略是否保證能夠找到？ ? 時(shí)間復(fù)雜性： ? 需要多長(zhǎng)時(shí)間可以找到解答？ ? 空間復(fù)雜性： ? 執(zhí)行搜索需要多少存儲(chǔ)空間？ ? 最優(yōu)性： ? 如果存在不同的幾個(gè)解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答？ 搜索策略評(píng)價(jià)標(biāo)準(zhǔn) : 2022/8/21 13 有許多智力問題 (如梵塔問題、旅行商問題、八皇后問題、農(nóng)夫過河問題等 )和實(shí)際問題（如路徑規(guī)劃、機(jī)器人行動(dòng)規(guī)劃等）都可以歸結(jié)為 狀態(tài)空間搜索 。 用 狀態(tài)空間搜索 來求解問題的系統(tǒng)均定義一個(gè) 狀態(tài)空間 ，并通過適當(dāng)?shù)?搜索算法 在 狀態(tài)空間 中搜索 解答路徑 。 基于狀態(tài)空間圖的搜索技術(shù) 2022/8/21 14 狀態(tài)空間搜索 —— (1)狀態(tài)空間的表示 ? 狀態(tài)空間記為 SP，可表示為二元組： ? SP=(S,O) ? S——問題求解（即搜索）過程中所有 可能到達(dá) 的 合法狀態(tài)構(gòu)成的集合； ? O——操作算子 的集合， 操作算子的執(zhí)行會(huì)導(dǎo)致問題狀態(tài)的變遷 ； ? 狀態(tài) ——用于記載問題求解（即搜索）過程中 某一時(shí)刻問題現(xiàn)狀的快照 ； ? 抽象為矢量形式 Q=[q0,q1,…,q n]T ? 每個(gè)元素 qi稱為 狀態(tài)分量 ? 給定每個(gè) 狀態(tài)分量 qi的值就得到一個(gè)具體的狀態(tài) Qk=[q0k,q1k,…,q nk]T 2022/8/21 15 狀態(tài) 表示狀態(tài)的變遷 操作算子 問題的狀態(tài)空間 是一個(gè)表示該問題的全部可能狀態(tài)及其變遷的 有向圖 。 ? 節(jié)點(diǎn) ? 狀態(tài) ? 有向弧 ? 狀態(tài)的變遷 ? 弧上的標(biāo)簽 ? 導(dǎo)致狀態(tài)變遷的操作算子 用 狀態(tài)空間搜索 來求解問題的系統(tǒng)均定義一個(gè) 狀態(tài)空間 ，并通過適當(dāng)?shù)?搜索算法 在 狀態(tài)空間 中搜索 解答路徑 。 2022/8/21 16 例 1： 走迷宮 是人們熟悉的一種游戲 。 狀態(tài)空間搜索 S1S2S3S4S5S6S7S8S9S0Sg2022/8/21 17 S1S2S3S4S5S6S7S8S9S0Sg? 格子、入口和出口 ——節(jié)點(diǎn) ——狀態(tài) ? 通道 ——有向弧 ——操作算子 ? 迷宮可以由一個(gè) 有向圖 表示 2022/8/21 18 例 2:在一個(gè) 3 3的方格棋盤上放置著 1,2,3,4,5,6,7,8八個(gè)數(shù)碼 ， 每個(gè)數(shù)碼占一格 ， 且有一個(gè)空格 。 這些數(shù)碼可在棋盤上移動(dòng) ， 其移動(dòng)規(guī)則是：與空格相鄰的數(shù)碼方可移入空格 。 現(xiàn)在的 問題 是：對(duì)于指定的 初始棋局 和 目標(biāo)棋局 ，給出 數(shù)碼的移動(dòng)序列 。 該問題稱為 八數(shù)碼問題 。 5 6 7 4 1 3 8 2 初始棋局 5 6 7 4 8 3 2 1 目標(biāo)棋局 移動(dòng)數(shù)碼 2022/8/21 19 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 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 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 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 8 4 7 6 5 2022/8/21 20 2022/8/21 21 狀態(tài)空間搜索 —— (2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題” ? 問題的描述 ： ? N個(gè)傳教士帶領(lǐng) N個(gè)野人劃船過河； ? 3個(gè)安全約束條件： ? 1)船上人數(shù)不得超過載重限量，設(shè)為 K個(gè)人； ? 2)任何時(shí)刻（包括兩岸、船上）野人數(shù)目不得超過傳教士； ? 3)允許在河的某一岸或者在船上只有野人而沒有傳教士； 2022/8/21 22 狀態(tài)空間搜索 —— (2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題” ? 特例： N=3， K=2 ? 狀態(tài)分量 m——傳教士在左岸的實(shí)際人數(shù) ? 狀態(tài)分量 c——野人在左岸的實(shí)際人數(shù) ? 狀態(tài)分量 b——指示船是否在左岸 ( 0) ? 3個(gè)安全約束條件 ? m ≧ c (左岸安全 )且 Nm ≧ Nc(右岸安全 )。 ? m=0且 0≤c ≤N (左岸沒有傳道士，右岸一定安全 )。 ? Nm=0且 0≤Nc≤N (右岸沒有傳道士，左岸一定安全 )。 2022/8/21 23 設(shè) 初始狀態(tài) 下傳教士、野人和船都在左岸， 目標(biāo)狀態(tài) 下這三者均在右岸， 問題狀態(tài) 以 （ m,c,b） 表示。 ? 問題的求解任務(wù)可描述為： (3,3,1) → (0,0,0) ? 該簡(jiǎn)單問題 可能到達(dá) 的 合法狀態(tài) ： ? 可能狀態(tài) 總數(shù) ： 4 4 2=32 ? 根據(jù)條件得出 合法狀態(tài) ： 20 ? m ≧ c 且 Nm ≧ Nc (左岸安全且右岸安全 ) ? m=1,c=1； m=2,c=2 ? m=0且 0≤c ≤N(左岸沒有傳道士 ) ? m=0,c=0,1,2,3 ? Nm=0且 0≤Nc≤N(右岸沒有傳道士 ) ? m=3,c=0,1,2,3 ? 不可能到達(dá)的合法狀態(tài) ： ? (0,0,1),(0,3,0),(3,0,1),(3,3,0) ? 可能到達(dá) 的 合法狀態(tài) 共 16個(gè) 2022/8/21 24 狀態(tài)空間搜索 —— (2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題” ? 定義 2類 操作算子 ： ? L(x,y)——指示從 左岸 到 右岸 的劃船操作 ? R(x,y)——指示從 右岸 到 左岸 的劃船操作 ? x + y ≤K=2(船的載重限制 )； ? x和 y取值的可能組合只有 5個(gè) ? 10， 20， 11， 01， 02 ? ( 允許在船上只有野人而沒有傳教士 ) ? 共有 10個(gè)操作算子 2022/8/21 25 渡河問題的狀態(tài)空間有向圖 2022/8/21 26 狀態(tài)空間搜索 —— ? 由此例可以看出 ? 用狀態(tài)空間方法表示問題時(shí)，首先必須 定義狀態(tài)的描述形式 ，通過使用這種描述形式可把問題的 一切狀態(tài)都表示出來 。另外，還要 定義一組操作 ，通過使用這些操作可把問題 由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài) 。 ? 問題的求解過程是一個(gè) 不斷把操作作用于狀態(tài)的過程 。如果在使用某個(gè)操作后得到的新狀態(tài)是目標(biāo)狀態(tài)，就得到了問題的一個(gè)解。這個(gè)解是從 初始狀態(tài)到目標(biāo)狀態(tài)所用操作構(gòu)成的序列 。 2022/8/21 27 狀態(tài)空間搜索 —— ? 由此例可以看出 ? 要使問題由一種狀態(tài)轉(zhuǎn)變到另一種狀態(tài)時(shí)，就必須使用一次操作。這樣，在從初始狀態(tài)轉(zhuǎn)變到目標(biāo)狀態(tài)時(shí)，就可能存在多個(gè)操作序列 (即得到多個(gè)解 )。那么，其中 使用操作最少或較少的解才為最優(yōu)解 (因?yàn)橹挥性谑褂貌僮鲿r(shí)所付出的代價(jià)為最小的解才是最優(yōu)解 )。 ? 對(duì)其中的某一個(gè)狀態(tài)，可能存在多個(gè)操作．使該狀態(tài)變到幾個(gè)不同的后繼狀態(tài)．那么到底用哪個(gè)操作進(jìn)行搜索呢 ?這就有賴于 搜索策略了 ． 不同的搜索策略有不同的順序 ，這就是本章后面要討論的問題。 2022/8/21 28 課堂練習(xí) ? 有一農(nóng)夫帶一只狐貍、一只小羊和一籃菜過河（從左岸到右岸）。假設(shè)船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河；考慮到安全，無農(nóng)夫看管時(shí)，狐貍和小羊不能在一起，小羊和那籃菜也不能在一起。請(qǐng)為該問題的解決設(shè)計(jì)狀態(tài)空間，并畫出狀態(tài)空間圖。