【正文】 0487321??????????056487321??????????567480321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表2022/8/21 60 ??????????586427301??????????586427031??????????586407321??????????586427310??????????506487321??????????586470321??????????586047321??????????560487321??????????056487321??????????567480321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表2022/8/21 61 ??????????586427301??????????586427031??????????586407321??????????586427310??????????506487321??????????586470321??????????586047321??????????560487321??????????056487321??????????567480321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表??????????567481320??????????5674083212022/8/21 62 ??????????586427301??????????586427031??????????586407321??????????586427310??????????506487321??????????586470321??????????586047321??????????560487321??????????056487321??????????567480321??????????567481320??????????567408321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表2022/8/21 63 ??????????586427301??????????586427031??????????586407321??????????586427310??????????506487321??????????586470321??????????586047321??????????560487321??????????056487321??????????567480321??????????567481320??????????567408321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表2022/8/21 64 ??????????586427301??????????586427031??????????586407321??????????586427310??????????506487321??????????586470321??????????586047321??????????560487321??????????056487321??????????567480321??????????567481320??????????567408321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表2022/8/21 65 ??????????586427301??????????586427031??????????586407321??????????586427310??????????506487321??????????586470321??????????586047321??????????560487321??????????056487321??????????567480321??????????567481320??????????567408321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表2022/8/21 66 狀態(tài)空間搜索 —— （ 2）一般圖搜索算法 ——搜索過程中的指針修改 ? 節(jié)點(diǎn) n擴(kuò)展后 的子節(jié)點(diǎn)分為 3類 ： ? (i)全新節(jié)點(diǎn) ? (ii)已出現(xiàn)在 OPEN表 中的節(jié)點(diǎn) ? (iii)已出現(xiàn)的 CLOSE表 中的節(jié)點(diǎn) ? 指針標(biāo)記和修改的方法： ? (i)類節(jié)點(diǎn)：加入 OPEN表，建立從子節(jié)點(diǎn)到父節(jié)點(diǎn) n的指針 ? (ii)類節(jié)點(diǎn)、 (iii)類節(jié)點(diǎn) ? 比較 經(jīng)由 老父節(jié)點(diǎn) 、 新父節(jié)點(diǎn) n到達(dá) 初始狀態(tài)節(jié)點(diǎn) 的 路徑代價(jià) ? 經(jīng)由新父節(jié)點(diǎn) n的代價(jià)比較小，則將原子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，修改為指向新父節(jié)點(diǎn) n ? (iii)類節(jié)點(diǎn)還得從 CLOSE表中移出，重新加入 OPEN表。 ? 即 C(ni, ni+1)=1 。 2022/8/21 39 狀態(tài)空間搜索 —— 狀態(tài)空間 、 搜索圖 和 解答路徑 之間的關(guān)系 S0 Sg 2022/8/21 40 狀態(tài)空間搜索 —— （ 1）搜索術(shù)語 ? 節(jié)點(diǎn)深度 ? 根節(jié)點(diǎn) 指示 初始狀態(tài) ，令其深度為 0； ? 搜索圖中的其他節(jié)點(diǎn)的 深度 dn就可以遞歸地定義為其 父節(jié)點(diǎn)深度 dn1加 1： dn= dn1+1。 ? 需要 32個(gè)操作算子 ? 簡(jiǎn)易方法 ——僅為空格制定這 4種走步。 狀態(tài)空間搜索 一般圖搜索 2022/8/21 34 狀態(tài)空間搜索 —— (3)狀態(tài)空間的搜索 ? 狀態(tài)空間 、 搜索圖 和 解答路徑 之間的關(guān)系 S0 Sg 2022/8/21 35 狀態(tài)空間搜索 —— (4)一般圖搜索例子 ——八數(shù)碼游戲 ? 求解的問題： ? 給定初始布局 (即 初始狀態(tài) )和目標(biāo)布局 (即 目標(biāo)狀態(tài) )， ? 如何移動(dòng)數(shù)碼才能從初始布局到達(dá)目標(biāo)布局 ？ ? 解答 ? 就是一個(gè)合法的 棋牌走步序列 。 2022/8/21 33 狀態(tài)空間搜索 —— (3)狀態(tài)空間的搜索 ? 或圖（一般圖） ? 一個(gè)狀態(tài)可以有多個(gè)可供選擇的操作算子； ? 操作算子間的選擇是一種 “ 或 ” 的關(guān)系 ， 這樣的有向圖稱為 或圖 。 2022/8/21 32 狀態(tài)空間搜索 —— ? 或圖（一般圖） ? 一個(gè)狀態(tài) 可以 有多個(gè)可供選擇 的操作算子； ? 操作算子間的選擇是一種 “ 或 ” 的關(guān)系 。 ? 基本思想 ——通過搜索引擎 E尋找一個(gè) 操作算子的調(diào)用序列 ，使問題從初始狀態(tài) I變遷到目標(biāo)狀態(tài) G之一。都是 7個(gè)操作步 . ? 思考：為什么不把船的狀態(tài)放到狀態(tài)空間中去？ 2022/8/21 30 解析 :四元組 (m、 f、 s、 v) 2022/8/21 31 狀態(tài)空間搜索 —— (3)狀態(tài)空間的搜索 ? 狀態(tài)空間的搜索記為 SE，可表示為五元組： ? SE=(S,O,E,I,G)； ? E——搜索引擎； ? I——問題的初始狀態(tài)， I ∈ S； ? G——問題的目標(biāo)狀態(tài)集合， G ? S。問題狀態(tài)可以四元組 (m、 f、 s、 v)描述 ,設(shè)初始狀態(tài)下均在左岸 ,目標(biāo)狀態(tài)下都到達(dá)右岸。請(qǐng)為該問題的解決設(shè)計(jì)狀態(tài)空間，并畫出狀態(tài)空間圖。 2022/8/21 28 課堂練習(xí) ? 有一農(nóng)夫帶一只狐貍、一只小羊和一籃菜過河（從左岸到右岸）。那么，其中 使用操作最少或較少的解才為最優(yōu)解 (因?yàn)橹挥性谑褂貌僮鲿r(shí)所付出的代價(jià)為最小的解才是最優(yōu)解 )。 2022/8/21 27 狀態(tài)空間搜索 —— ? 由此例可以看出 ? 要使問題由一種狀態(tài)轉(zhuǎn)變到另一種狀態(tài)時(shí)，就必須使用一次操作。如果在使用某個(gè)操作后得到的新狀態(tài)是目標(biāo)狀態(tài)，就得到了問題的一個(gè)解。另外，還要 定義一組操作 ，通過使用這些操作可把問題 由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài) 。 2022/8/2