【文章內(nèi)容簡(jiǎn)介】 i表示金片 C的針號(hào) 。 j表示金片 B的針號(hào) 。 k表示金片 A的針號(hào) 。 34 人工智能 2023秋 利用問(wèn)題歸約方法，原問(wèn)題可分解為以下三個(gè)子問(wèn)題 : (1)把金片 A及 B移到 2號(hào)鋼針上的雙金片移動(dòng)問(wèn)題： (1,1,1) → (1,2,2) (2)把金片 C移到 3號(hào)鋼針上的單金片移動(dòng)問(wèn)題： (1,2,2) → (3,2,2) (1)把金片 A及 B移到 3號(hào)鋼針上的雙金片移動(dòng)問(wèn)題： (3,2,2) → (3,3,3) 35 人工智能 2023秋 (1,1,1) → (3,3,3) (1,1,1) → (1,2,2) (3,2,2) → (3,3,3) (1,2,2) → (3,2,2) (3,3,1) → (3,3,3) (3,2,1) → (3,3,1) (3,2,2) → (3,2,1) (1,2,3) → (1,2,2) (1,1,3) → (1,2,3) (1,1,1) → (1,1,3) 36 人工智能 2023秋 原始問(wèn)題的解： (1,1,1) → (1,1,3) (1,1,3) → (1,2,3) (1,2,3) → (1,2,2) (1,2,2) → (3,2,2) (3,2,2) → (3,2,1) (3,2,1) → (3,3,1) (3,3,1) → (3,3,3) 37 人工智能 2023秋 狀態(tài)空間的搜索策略可分為盲目搜索和啟發(fā)式搜索。 啟發(fā)式搜索需要抽取與問(wèn)題本身有關(guān)的特征信息，而信息抽取比較困難，所以盲目搜索仍不失為一種有效的搜索策略。 38 人工智能 2023秋 一般圖搜索過(guò)程 當(dāng)用狀態(tài)空間法解決問(wèn)題時(shí)，需要考慮： （ 1）對(duì)于很大問(wèn)題，計(jì)算機(jī)無(wú)法保存其全部狀態(tài)空間； （ 2）對(duì)于具體問(wèn)題，與解有關(guān)的狀態(tài)空間一般僅是全部狀態(tài)空間的一部分。 因此在問(wèn)題求解過(guò)程中，沒(méi)有必要生成和保存該問(wèn)題的全部狀態(tài)空間，只要能夠生成和保存與解有關(guān)的那部分狀態(tài)空間即可。 解決問(wèn)題的方法是采用狀態(tài)空間搜索技術(shù)。 39 人工智能 2023秋 對(duì)狀態(tài)空間的搜索，由于問(wèn)題的狀態(tài)空間可用一個(gè)有向圖來(lái)表示，因此狀態(tài)空間搜索實(shí)際上就是對(duì)有向圖的搜索。 40 人工智能 2023秋 狀態(tài)空間搜索的基本思想是： 先把問(wèn)題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問(wèn)題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。 若出現(xiàn)，則搜索成功，找到了問(wèn)題的解； 若沒(méi)有出現(xiàn)，則按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，重復(fù)上述過(guò)程，指導(dǎo)目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒(méi)有可供擴(kuò)展的節(jié)點(diǎn)為止。 41 人工智能 2023秋 狀態(tài)空間算法： 需要設(shè)立數(shù)據(jù)結(jié)構(gòu) Open和 Closed表。 Open表（未擴(kuò)展節(jié)點(diǎn)表）： 用于存放剛生成沒(méi)有擴(kuò)展的節(jié)點(diǎn)； Closed表（已擴(kuò)展節(jié)點(diǎn)表）： 用于存放已經(jīng)擴(kuò)展或?qū)⒁獢U(kuò)展的節(jié)點(diǎn)。 42 人工智能 2023秋 狀態(tài)空間的一般圖搜索過(guò)程為： （ 1）把初始節(jié)點(diǎn) S0放入 Open表并建立目前僅包含 S0的圖 G。 （ 2） 檢查 Open表是否為空，若為空，則問(wèn)題無(wú)解，失敗退出； （ 3）把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn) n。 （ 4） 考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問(wèn)題的解，成功退出； 43 人工智能 2023秋 （ 5）擴(kuò)展節(jié)點(diǎn) n， 生成一組子節(jié)點(diǎn)。把這些子節(jié)點(diǎn)中不是節(jié)點(diǎn) n先輩的那部分子節(jié)點(diǎn)記入集合 M， 并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn) n的子節(jié)點(diǎn)加入 G中。 （ 6）針對(duì) M中子節(jié)點(diǎn)的不同情況，分別作如下處理： ? 對(duì)那些沒(méi)有在 G中出現(xiàn)過(guò)的 M成員設(shè)置一個(gè)指向其父節(jié)點(diǎn)（即節(jié)點(diǎn) n） 的指針，并把它放入 Open表； ? 對(duì)那些原來(lái)已在 G中出現(xiàn)過(guò)，但還沒(méi)有被擴(kuò)展的 M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針； 44 人工智能 2023秋 ? 對(duì)于先前已在 G中出現(xiàn)過(guò)，并已經(jīng)擴(kuò)展了的 M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。 （ 7）按某種策略對(duì) Open表中的節(jié)點(diǎn)進(jìn)行排序； （ 8）轉(zhuǎn) (2)步。 45 人工智能 2023秋 搜索過(guò)程說(shuō)明： （ 1）狀態(tài)空間圖搜索算法具有通用性，其它的各種狀態(tài)空間搜索策略都是上述的一個(gè)特例。 各種搜索策略的主要區(qū)別在于對(duì) Open表中節(jié)點(diǎn)的排列順序不同。 如廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面；深度優(yōu)先搜索把后生成的子節(jié)點(diǎn)排在前面。 46 人工智能 2023秋 （ 2）在第 (5)步對(duì)節(jié)點(diǎn) n擴(kuò)展后，生成并記入 M的子節(jié)點(diǎn)有以下三種情況： ? 該子節(jié)點(diǎn)從未被任何節(jié)點(diǎn)生成過(guò)，由 n第一次生成； ? 該子節(jié)點(diǎn)原來(lái)被其它節(jié)點(diǎn)生成過(guò)，但還沒(méi)有被擴(kuò)展，這一次又被 n再次生成； ? 該子節(jié)點(diǎn)原來(lái)被其它節(jié)點(diǎn)生成過(guò)，并且已經(jīng)被擴(kuò)展過(guò)，這一次又被 n再次生成。 47 人工智能 2023秋 對(duì)于一般圖搜索算法，具有以上三種情況； 對(duì)于盲目搜索，由于其狀態(tài)空間是樹(shù)狀結(jié)構(gòu)，因此不會(huì)出現(xiàn)后兩種情況 ，每個(gè)節(jié)點(diǎn)擴(kuò)展后生成的子節(jié)點(diǎn)都是第一次出現(xiàn)的節(jié)點(diǎn)，不必檢查并修改指向父節(jié)點(diǎn)的指針。 （ 3）在第（ 6）步針對(duì) M中子節(jié)點(diǎn)的不同情況進(jìn)行處理時(shí)，如果發(fā)生上面第 2種情況，一般是由原時(shí)節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代價(jià)來(lái)決定。 48 人工智能 2023秋 例題見(jiàn)書(shū) P177 廣度優(yōu)先搜索 廣度優(yōu)先搜索也成為寬度優(yōu)先搜索，是一種先生成的節(jié)點(diǎn)限擴(kuò)展的策略。 49 人工智能 2023秋 廣度優(yōu)先搜索策略搜索過(guò)程為： 從初始節(jié)點(diǎn) S0開(kāi)始逐層向下擴(kuò)展，在第 n曾節(jié)點(diǎn)還沒(méi)有全部搜索完之前，不進(jìn)入第 n+1層節(jié)點(diǎn)的搜索。 Open表