【正文】 安全約束條件：o 1)船上人數(shù)不得超過載重限量，設(shè)為 K個人； o 2)任何時刻（包括兩岸、船上）野人數(shù)目不得超過傳教士； o 3)允許在河的某一岸或者在船上只有野人而沒有傳教士；2023/5/15 24狀態(tài)空間搜索狀態(tài)空間搜索——(2)狀態(tài)空間表示的經(jīng)典例子狀態(tài)空間表示的經(jīng)典例子 “傳教士和野人問題傳教士和野人問題 ”o 特例：特例： N=3， K=2 n 狀態(tài)分量狀態(tài)分量 m———— 傳教士在左岸的實(shí)際人數(shù)傳教士在左岸的實(shí)際人數(shù)n 狀態(tài)分量狀態(tài)分量 c———— 野人在左岸的實(shí)際人數(shù)野人在左岸的實(shí)際人數(shù)n 狀態(tài)分量狀態(tài)分量 b———— 指示船是否在左岸指示船是否在左岸 ( 0)n 3個安全約束條件個安全約束條件o m ≧≧ c (左岸安全左岸安全 )且且 Nm ≧≧ Nc(右岸安全右岸安全 )。 分析：通過引入一個 三維變量 將問題表示出來。 56741382初始棋局56748321目標(biāo)棋局移動數(shù)碼2023/5/15 192 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61 2 3 8 47 6 52023/5/15 202023/5/15 21 例 3:錢幣翻轉(zhuǎn)問題。狀態(tài)空間搜索狀態(tài)空間搜索2023/5/15 17o 格子、入口和出口格子、入口和出口 ———— 節(jié)點(diǎn)節(jié)點(diǎn) ———— 狀態(tài)狀態(tài)o 通道通道 ———— 有向弧有向弧 ———— 操作算子操作算子o 迷宮可以由一個迷宮可以由一個 有向圖有向圖 表示表示2023/5/15 18 例 2:在一個 33的方格棋盤上放置著 1,2,3,4,5,6,7,8八個數(shù)碼，每個數(shù)碼占一格，且有一個空格。 基于狀態(tài)空間的搜索技術(shù)基于狀態(tài)空間的搜索技術(shù)2023/5/15 14狀態(tài)空間搜索狀態(tài)空間搜索——(1)狀態(tài)空間的表示狀態(tài)空間的表示 ★★o 狀態(tài)空間記為狀態(tài)空間記為 SP，可表示為二元組：，可表示為二元組：n SP=(S,O)n S——問題求解（即搜索）過程中所有 可能到達(dá) 的 合法狀態(tài)構(gòu)成的集合；n O——操作算子 的集合， 操作算子的執(zhí)行會導(dǎo)致問題狀態(tài)的變遷 ；n 狀態(tài) ——用于記載問題求解（即搜索）過程中 某一時刻問題現(xiàn)狀的快照 ；o 抽象為矢量形式 Q=[q0,q1,…,qn]To 每個元素 qi稱為 狀態(tài)分量 o 給定每個 狀態(tài)分量 qi的值就得到一個具體的狀態(tài) Qk=[q0k,q1k,…,qnk]T2023/5/15 15狀態(tài)表示狀態(tài)的變遷操作算子問題的狀態(tài)空間 是一個表示該問題的全部可能狀態(tài)及其變遷的 有向圖 。這種類型的遍歷稱為 “ 確定性 ” 的，也就是 盲目搜索 。o 寬度優(yōu)先搜索o 深度優(yōu)先搜索如果根節(jié)點(diǎn)首先擴(kuò)展，然后是擴(kuò)展根節(jié)點(diǎn)生成的所有節(jié)點(diǎn)，然后是這些節(jié)點(diǎn)的后繼，如此反復(fù)下去。 沒有考慮到問題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復(fù)雜問題的求解。搜索空間通常是指一系列狀態(tài)的匯集，因此稱為 狀態(tài)空間 。一般給定問題就是確定該問題的一些基本信息，一個問題由 4部分組成 :2023/5/15 6o 和通常的搜索空間不同，人工智能中大多數(shù)問題的 狀態(tài)空間在問題求解之前不是全部知道的 。（ 3）目標(biāo)檢測函數(shù)：用來確定一個狀態(tài)是不是目標(biāo)。 2023/5/15 4o 搜索算法的輸入是 給定的問題 ，輸出時表示為動作序列的方案 。2023/5/15 1第 3章 搜索策略o 問題求解系統(tǒng)劃分為兩大類n 知識貧乏系統(tǒng) o 依靠 搜索技術(shù) 解決問題 o 知識貧乏、缺乏針對性o 效率低 n 知識豐富系統(tǒng) o 依靠 推理技術(shù) 解決問題o 基于豐富知識的推理技術(shù)，直截了當(dāng) o 效率高 2023/5/15 2第 3章 搜索策略o 兩大類 搜索 技術(shù) :n 一般圖搜索、啟發(fā)式搜索n 基于問題歸約的與或圖搜索 o 兩種典型的 推理技術(shù) :n 基于歸結(jié)的演繹推理o 歸結(jié)反演n 基于規(guī)則的演繹推理o 正向演繹推理o 逆向演繹推理 2023/5/15 3 引言引言 o對于給定的問題，智能系統(tǒng)的行為一般是找到能夠達(dá)到所希望目標(biāo)的動作序列 ，并使其所付出的 代價最小、性能最好 。o 一旦有了方案，就可以執(zhí)行該方案所給出的動作了。（ 4）路徑費(fèi)用函數(shù)：對每條路徑賦予一定費(fèi)用的函數(shù)。 216。2023/5/15 7o所以，人工智能中的搜索可以分成兩個階段：n 狀態(tài)空間的生成階段n 在該狀態(tài)空間中對所求問題狀態(tài)的搜索216。 o啟發(fā)式搜索是在搜索過程中加入了 與問題有關(guān)的啟發(fā)式信息 ，用于指導(dǎo)搜索 朝著最有希望的方向前進(jìn)，加速問題的求解并找到最優(yōu)解 。在樹的最深一層的節(jié)點(diǎn)中擴(kuò)展一個節(jié)點(diǎn)。o 對于啟發(fā)式搜索，在計算每個節(jié)點(diǎn)的參數(shù)之前無法確定先選擇哪個節(jié)點(diǎn)擴(kuò)展 ，這種搜索一般也稱為 非確定 的。 o 節(jié)點(diǎn)n 狀態(tài)o 有向弧n 狀態(tài)的變遷 o 弧上的標(biāo)簽n 導(dǎo)致狀態(tài)變遷的操作算子 用 狀態(tài)空間搜索 來求解問題的系統(tǒng)均定義一個 狀態(tài)空間 ，并通過適當(dāng)?shù)?搜索算法 在 狀態(tài)空間 中搜索 解答路徑 。這些數(shù)碼可在棋盤上移動，其移動規(guī)則是：與空格相鄰的數(shù)碼方可移入空格。設(shè)有 3個錢幣，其初始狀態(tài)為 (正、反、正 ),欲得的目標(biāo)狀態(tài)為 (正、正、正 )或 (反、反、反 )。設(shè)三維變量為： Q=[q1,q2,q3]，式中 qi (i=1,2,3)=1表示錢幣為正面， qi (i=1,2,3)=0表示錢幣為反面。(想一想想一想，為什么不考慮船安全？，為什么不考慮船安全？ )o m=0且且 0≤c ≤N (左岸沒有傳道士，右岸一定安全左岸沒有傳道士，右岸一定安全 )。另外，還要。如果在使用某個操作后得到的新狀態(tài)是目標(biāo)狀態(tài)，就得到了問題的一個解。這樣，在從初始狀態(tài)轉(zhuǎn)變必須使用一次操作。 n 對其中的某一個狀態(tài)，可能存在多個操作．使對其中的某一個狀態(tài)，可能存在多個操作．使該狀態(tài)變到幾個不同的后繼狀態(tài)．那么到底用該狀態(tài)變到幾個不同的后繼狀態(tài)．那么到底用哪個操作進(jìn)行搜索呢哪個操作進(jìn)行搜索呢 ?這就有賴于這就有賴于 搜索策略了搜索策略了 ．．不同的搜索策略有不同的順序不同的搜索策略有不同的順序 ，這就是本章后，這就是本章后面要討論的問題。請為該問題的解決設(shè)計狀態(tài)空間，并畫出狀態(tài)空間圖。o 基本思想 ——通過搜索引擎 E尋找一個 操作算子的調(diào)用序列，使問題從初始狀態(tài) I變遷到目標(biāo)狀態(tài) G之一。2023/5/15 35狀態(tài)空間搜索狀態(tài)空間搜索——(3)狀態(tài)空間的搜索o 或圖（一般圖）n 一個狀態(tài)可以有多個可供選擇的操作算子；n 操作算子間的選擇是一種 “ 或 ” 的關(guān)系， 這樣的有向圖稱為 或圖。o 需要 32個操作算子n 簡易方法 ——僅為空格制定這 4種走步。n 即 C(ni, ni+1)=1 。并且要重新加入open表。 ?深度優(yōu)先 —— 擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于 OPEN表的前端，即 OPEN表作為 棧 使用， 后進(jìn)先出 ，使搜索優(yōu)先向 縱深方向發(fā)展。即先按生成規(guī)則生成第一層節(jié)點(diǎn)，在該層全部節(jié)點(diǎn)中沿寬 (廣 )度進(jìn)行橫向掃描，檢查目標(biāo)節(jié)點(diǎn)Sg是否在這些子節(jié)點(diǎn)中。?“先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展 ”2023/5/15 75 (1)把初始節(jié)點(diǎn) S0，放入 OPEN表。若是，則求得了問題的解，成功并退出。請畫出按照寬度優(yōu)先搜索策略所產(chǎn)生的搜索樹。（ 2）如 Y是積木（不是桌面），則積木 Y的頂部也必須為空。 寬度優(yōu)先搜索優(yōu)點(diǎn)：目標(biāo)節(jié)點(diǎn)如果存在，用寬度優(yōu)先搜索算法總可以找到該目標(biāo)節(jié)點(diǎn)，而且 是最?。醋疃搪窂剑┑墓?jié)點(diǎn)。 2023/5/15 81深度優(yōu)先實(shí)例2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61234 689 1113141618191 2 3 8 47 6 5目標(biāo)5 71012151720212023/5/15 82深度優(yōu)先搜索o 在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的 (最深的 )節(jié)點(diǎn)，深度 相等的節(jié)點(diǎn)可以任意排列。2023/5/15 84(1)把初始節(jié)點(diǎn) S0放入 OPEN表； (2)如果 OPEN表為空，則問題無解，失敗并退出?；跅?shí)現(xiàn)的深度優(yōu)先搜索算法： 2023/5/15 85 例 卒子穿陣問題 : 要求一卒子從頂部通過圖所示的列陣到達(dá)底部。o 深度優(yōu)先搜索的存儲器要求是深度約束的線性函數(shù)。這樣一來對于這些問題，深度優(yōu)先搜索要么陷入無限的循環(huán)而不能給出一個答案，要么最后找到一個答案，但路徑很長而且不是最優(yōu)的答案。 ?節(jié)點(diǎn)排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識去指導(dǎo)排序，往往會在白白搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn)后才碰到解答，所以也稱為 盲目搜索 。 (3)把 OPEN表中的第一個節(jié)點(diǎn)取出放入 CLOSE表中。 (5)如果節(jié)點(diǎn) n的深度 d(n)= dm，則轉(zhuǎn)第 (2)步 。然后轉(zhuǎn)第 (2)步。2023/5/15 94（ 2） 深度限制 dm不能太大 。2023/5/15 96o 迭代加深搜索 ，試圖嘗試所有可能的深度限制：n 首先深度為 0，n 然后深度為 1，n 然后為 2，等等。 2023/5/15 97o 迭代加深搜索看起來會很浪費(fèi)，因為很多節(jié)點(diǎn)都可能擴(kuò)展多次。 (3)While棧不空并且深度在給定的深度限制之內(nèi) do Begin 彈出棧頂元素； If棧頂元素 =goal,返回并結(jié)束 。o 寬度優(yōu)先搜索 需要指數(shù)數(shù)量的空間，深度優(yōu)先搜索的空間復(fù)雜度和最大搜索深度呈線性關(guān)系。但對空間要求和深度優(yōu)先搜索一樣是適中的。o 如何用評價函數(shù)來實(shí)現(xiàn) A算法 ? （ 掌握！ ） 2023/5/15 108啟發(fā)式搜索啟發(fā)式搜索——（算法（ 掌握掌握 ））o A算法 的設(shè)計與 一般圖搜索 相同，劃分為二個階段 ★ ：n 初始化 o 建立只包含初始狀態(tài)節(jié)點(diǎn) s的搜索圖 G:={s}o O