哈工大人工智能原理習(xí)題homework-1

1、人工智能原理練習(xí)題 -1從習(xí)題中選擇自己感興趣的題目進(jìn)行思考和解答，任何嘗試都是有益的。必要時(shí)，仔細(xì)閱讀教科書(shū)當(dāng)中的某些章節(jié)。對(duì)于加星號(hào)的習(xí)題，應(yīng)該編寫程序來(lái)完成。第 1 章 人工智能概述1用自己的語(yǔ)言定義：（a）智能，（b）人工智能，（c）智能體。2 用你自己的話定義下列術(shù)語(yǔ)：智能體、智能體函數(shù)、智能體程序、理性、自主、反射型智能體、基于模型的智能體、基于目標(biāo)的智能體、基于效用的智能體、學(xué)習(xí)智能體。3 對(duì)于下列智能體，分別給出任務(wù)環(huán)境PEAS 描述：a. 機(jī)器人足球運(yùn)動(dòng)員；b. 因特網(wǎng)購(gòu)書(shū)智能體；c. 自主的火星漫游者；d. 數(shù)學(xué)家的定理證明助手。4 檢查 AI 的文獻(xiàn)，去發(fā)現(xiàn)下列任務(wù)現(xiàn)在計(jì)

2、算機(jī)是否能夠解決：a. 打正規(guī)的乒乓球比賽。b. 在開(kāi)羅市中心開(kāi)車。c. 在市場(chǎng)購(gòu)買可用一周的雜貨。d. 在萬(wàn)維網(wǎng)上購(gòu)買可用一周的雜貨。e. 參加正規(guī)的橋牌競(jìng)技比賽。f. 發(fā)現(xiàn)并證明新的數(shù)學(xué)定理。g. 寫一則有內(nèi)涵的有趣故事。h. 在特定的法律領(lǐng)域提供令人滿意的法律建議。i. 從英語(yǔ)到西班牙語(yǔ)的口語(yǔ)實(shí)時(shí)翻譯。j. 完成復(fù)雜的外科手術(shù)。對(duì)于現(xiàn)在不可實(shí)現(xiàn)的任務(wù)，試著找出困難所在，并預(yù)測(cè)如果可能的話它們什么時(shí)候能被克服。5 Loebner 獎(jiǎng)每年頒發(fā)給最接近天通過(guò)某個(gè)版本圖靈測(cè)試的程序。查找和匯報(bào)Loebner 獎(jiǎng)最近的得主。它使用了什么技術(shù)？它對(duì)AI 目前的發(fā)展水平有什么推動(dòng)？6 這道習(xí)題要探討的

3、是智能體函數(shù)與智能體程序的區(qū)別：a. 是否有不止一個(gè)智能體程序可以實(shí)現(xiàn)給定的智能體函數(shù)？請(qǐng)舉例，或者說(shuō)明為什么不可能。b. 有沒(méi)有無(wú)法用任何智能體程序?qū)崿F(xiàn)的智能體函數(shù)。c.給定一個(gè)機(jī)器體系結(jié)構(gòu)，能使每個(gè)智能體程序剛好實(shí)現(xiàn)一個(gè)智能體函數(shù)嗎？d. 給定一個(gè)存儲(chǔ)量為n 比特的體系結(jié)構(gòu)，可以有多少種可能的不同智能體程序？7 有一些類眾所周知的難題對(duì)計(jì)算機(jī)而言是難以解決的困難，其它類問(wèn)題是不能判定的。這是否意味著AI 是不可能的？是如何不精確的？我會(huì)搞錯(cuò)我怎么想的嗎？請(qǐng)討論。8 內(nèi)省 匯報(bào)自己的內(nèi)心想法 第 2 章 搜索技術(shù)1 解釋為什么問(wèn)題的形式化必須在目標(biāo)的形式化之后。2 有限的狀態(tài)空間總是導(dǎo)致有限

4、的搜索樹(shù)嗎？是樹(shù)結(jié)構(gòu)的有限空間呢？你能更精確地說(shuō)出什么類型的狀態(tài)空間總是導(dǎo)致有限的搜索樹(shù)嗎？（改編自Bender， 1996）2 給出下列問(wèn)題的初始狀態(tài)、目標(biāo)測(cè)試、后繼函數(shù)和耗散函數(shù)。選擇精確得足以實(shí)現(xiàn)的形式化。a. 只用四種顏色對(duì)平面地圖染色，要求每?jī)蓚€(gè)相鄰的地區(qū)不能染成相同的顏色。b. 一間屋子里有一只3 英尺的猴子，屋子的房頂上掛著一串香蕉，離地面8 英尺 .屋子里有兩個(gè)可疊放起來(lái)、可移動(dòng)、可攀登的3 英尺高的箱子。猴子很想得到香蕉。c. 有一個(gè)程序，當(dāng)送入一個(gè)特定文件的輸入記錄時(shí)會(huì)輸出“不合法的輸入記錄”。已知每個(gè)記錄的處理獨(dú)立于其它記錄。要求找出哪個(gè)記錄不合法。d. 有三個(gè)水壺，容量

5、分別為12 加侖、 8 加侖和 3 加侖，還有一個(gè)水龍頭。可以把壺裝滿或者倒空，從一個(gè)壺倒進(jìn)另一個(gè)壺或者倒在地上。要求量出剛好1 加侖水。*3 傳教士和野人問(wèn)題通常描述如下：三個(gè)傳教士和三個(gè)野人在河的一邊，還有一條能載一個(gè)人或者兩個(gè)人的船。找到一個(gè)辦法讓所有的人都渡到河的另一岸，要求在任何地方野人數(shù)都不能多于傳教士的人數(shù)（可以只有野人沒(méi)有傳教士）。 這個(gè)問(wèn)題在AI 領(lǐng)域中很著名，因?yàn)樗堑谝黄獜姆治龅挠^點(diǎn)探討問(wèn)題形式化的論文的主題（Amarel,1968 ）a. 精確地形式化該問(wèn)題，只描述確保該問(wèn)題有解所必需的特性。畫(huà)出該問(wèn)題的完全狀態(tài)空間圖。b. 用一個(gè)合適的搜索算法實(shí)現(xiàn)和最優(yōu)地求解該問(wèn)題。

6、檢查重復(fù)狀態(tài)是個(gè)好主意嗎？c. 這個(gè)問(wèn)題的狀態(tài)空間如此簡(jiǎn)單，你認(rèn)為為什么人們求解它卻很困難？*4編寫一個(gè)程序，當(dāng)輸入兩個(gè)網(wǎng)頁(yè)的URL （鏈接地址）后能找到從一個(gè)網(wǎng)頁(yè)到另一個(gè)網(wǎng)頁(yè)的鏈接路徑。什么樣的搜索策略是適合的？雙向搜索是好主意嗎？能用搜索引擎實(shí)現(xiàn)一個(gè)前輩函數(shù)嗎？5 考慮一個(gè)狀態(tài)空間，它的初始狀態(tài)編號(hào)為1 ，狀態(tài) n 的后繼函數(shù)返回兩個(gè)狀態(tài)，編號(hào)為2n 和2n+1 。a. 畫(huà)出狀態(tài)1 到 15 的部分狀態(tài)空間圖。b. 假設(shè)目標(biāo)狀態(tài)為11。 列出用以下算法訪問(wèn)節(jié)點(diǎn)的順序：廣度優(yōu)先搜索，深度限制為3的深度有限搜索，以及迭代深入搜索。c. 雙向搜索是否適合這個(gè)問(wèn)題？如果合適的話，詳細(xì)地描述它是怎樣

7、工作的。d. 在雙向搜索中每個(gè)方向上的分支因子是什么？e.對(duì)（c）的回答是否能提出問(wèn)題的一種重新形式化，使你可以幾乎不用搜索來(lái)求解從狀態(tài)1到達(dá)目標(biāo)狀態(tài)的問(wèn)題？*6 實(shí)現(xiàn)兩種八數(shù)碼游戲的后繼函數(shù)：一種通過(guò)復(fù)制和編輯八數(shù)碼游戲的數(shù)據(jù)結(jié)構(gòu)立刻生成它的生成一個(gè)全部后繼；另一種每次調(diào)用的時(shí)候通過(guò)直接修改父狀態(tài)(需要的話可以撤消修改)新后繼。寫出使用這兩種后繼函數(shù)的迭代深入算法和深度優(yōu)先算法并比較它們的性能。7證明用于GRAPH-SEARCH算法是，單步耗散為常數(shù)的代價(jià)一致搜索和廣度優(yōu)先搜索是最優(yōu)的。給出一個(gè)單步消耗為常數(shù)的狀態(tài)空間，在其中使用迭代深入的GRAPH-SEARCH 算法會(huì)找到非最優(yōu)解。8描述

8、一個(gè)狀態(tài)空間，在其中迭代深入搜索比深度優(yōu)先搜索的性能要差很多(例如，一個(gè)是O(n2),另一個(gè)是 O (n)。*9在下圖中所示的平面上有兩個(gè)點(diǎn)，之間有很多凸多邊形障礙物，考慮尋找這兩個(gè)點(diǎn)之間的最短路很的問(wèn)題。這是機(jī)器人在擁擠的環(huán)境中求解道路導(dǎo)航問(wèn)題的一種理想化情況。a.假設(shè)狀態(tài)狀態(tài)空間由平面上所有的點(diǎn)( x,y )組成。共有多少個(gè)狀態(tài)？共有多少條到達(dá)目 標(biāo)的路徑？b.簡(jiǎn)要解釋為什么在這個(gè)場(chǎng)景中從一個(gè)多邊形的頂點(diǎn)到另一個(gè)頂點(diǎn)的最短距離必然由連接 某些多邊形的頂點(diǎn)的直線段組成?，F(xiàn)在定義一個(gè)良好的狀態(tài)空間。 這個(gè)狀態(tài)空間有多大?c.定義必要的函數(shù)來(lái)實(shí)現(xiàn)這個(gè)搜索問(wèn)題，包括把一個(gè)頂點(diǎn)作為輸入的后繼函數(shù)，它

9、返回從 該頂點(diǎn)出發(fā)能夠通過(guò)直線段到達(dá)的頂點(diǎn)集合。(不要忘記該頂點(diǎn)所在的多邊形的相鄰頂點(diǎn)。)用直線段的長(zhǎng)度作為啟發(fā)函數(shù)。d.應(yīng)用本章中的一種或多種搜索算法來(lái)求解這個(gè)領(lǐng)或內(nèi)的一定范圍的問(wèn)題，并評(píng)價(jià)它們的 性能。10跟蹤A*搜索算法用直線距離啟發(fā)式求解從Lugoj到Bucharest問(wèn)題的過(guò)程。按順序列出算法擴(kuò)展的節(jié)點(diǎn)和每個(gè)節(jié)點(diǎn)的f, g, h值。11啟發(fā)式路徑算法 是一個(gè)最佳優(yōu)先搜索，它的目標(biāo)函數(shù)是f(n) = (2 - w) g(n) + w h(n)。算法中w取什么值能保證算法是最優(yōu)的？當(dāng) w = 0時(shí)，這個(gè)算法是什么搜索？w = 1呢？ w = 2呢？12設(shè)計(jì)一個(gè)狀態(tài)空間，在其中用GRAPH

10、-SEARCH的A*算法返回的不是最優(yōu)解，如果它的啟發(fā)函數(shù)h(n)是可采納的但不是一致的。13在第4.2.2節(jié)，我們定義了松弛的八數(shù)碼游戲，其中如果 B是空的，一個(gè)棋子可以直接從方 格A移到方格B。這個(gè)問(wèn)題的精確解定義了Gaschnig啟發(fā)式(Gaschnig, 1979)。解釋為什么Gaschnig啟發(fā)式至少和h1 （不在位棋子數(shù)） 一樣精確，并說(shuō)明它比 %和卜2 （曼哈頓距離） 更精確的情況。你能給出一個(gè)有效計(jì)算Gaschnig啟發(fā)式的方法嗎？14根據(jù)下面的特殊情況給出算法的名稱：a. k = 1的局部剪枝搜索。b. k = 8的局部剪枝搜索。c.所有時(shí)刻T =。的模擬退火搜索。d.種群大

11、小為N = 1的遺傳算法。15有些情況下一個(gè)問(wèn)題找不到好的評(píng)價(jià)函數(shù)，但是有一個(gè)好的比較方法：即只是指出一個(gè)節(jié)點(diǎn)是否優(yōu)于另一個(gè)節(jié)點(diǎn)而不需要指出它們實(shí)際的評(píng)價(jià)數(shù)值。證明這對(duì)于最佳優(yōu)先搜索就已經(jīng)足夠了。A*算法是否類似？16假設(shè)一個(gè)智能體在一個(gè)教科書(shū)中圖4.18所示的3X3大小的迷宮里（如下圖）。智能體知道它的起始位置是（1, 1）,目標(biāo)位置是（3, 3）,四種行動(dòng)Up （上），Down （下），Left （左），Right （右）通?？梢园l(fā)揮效果，除非遇到有墻阻礙。智能體不知道迷宮內(nèi)部的墻在哪些地 方。在任何給定的狀態(tài)，智能體知道合法行動(dòng)集合；它也知道一個(gè)狀態(tài)是已經(jīng)訪問(wèn)過(guò)的狀態(tài) 還是新?tīng)顟B(tài)。GS1

12、23圖4.18 一個(gè)簡(jiǎn)單的迷宮問(wèn)題。智能體從狀態(tài)S出發(fā)到達(dá)狀態(tài)G,但是智能體對(duì)環(huán)境一無(wú)所知a.解釋這個(gè)聯(lián)機(jī)搜索問(wèn)題如何可以視為在信念狀態(tài)空間中的脫機(jī)搜索問(wèn)題，初始的信念狀態(tài)包括所有可能的環(huán)境布局。初始信念狀態(tài)有多大？信念狀態(tài)空間有多大？b.在初始狀態(tài)可能有多少個(gè)不同的感知信息？c.描述這個(gè)問(wèn)題的偶發(fā)性計(jì)劃的頭幾個(gè)分支。完整的計(jì)劃（大約）有多大？注意這個(gè)偶發(fā)性計(jì)劃是符合給定描述的每個(gè)可能環(huán)境的解決方案。因此，即使在未知環(huán)境下搜索和行動(dòng)的交叉也不是嚴(yán)格必需的了。*17在本題中，我們將在機(jī)器人導(dǎo)航問(wèn)題中考察爬山法，以第9題中圖示（教科書(shū)圖 3.22）的環(huán)境為例。a.用爬山法算法重復(fù)習(xí)題 9。智能體會(huì)

13、卡在局部最小值上嗎？可能遇到被凸障礙物卡住的情 況嗎？b.構(gòu)造一個(gè)非凸多邊形的環(huán)境，智能體在其中會(huì)被卡住。c.修改爬山法算法，在決定下一步的時(shí)候不用深度為1的搜索，而用深度為 k的搜索。它將找到最好的k步路徑并且沿著該路徑走一步，然后重復(fù)這個(gè)過(guò)程。d.有沒(méi)有某個(gè)k使得新的算法保證能避免局部極小值？e.解釋LRT A*是怎樣使新的算法能夠在這種情況下避免局部極小值的。18用你自己的話定義約束滿足問(wèn)題、約束、回溯搜索、弧相容、后向跳轉(zhuǎn)和最小沖突。19圖5.1 （澳大利亞地圖）所示的地圖染色問(wèn)題一共有多少個(gè)解？20解釋為什么在 CSP搜索中，一個(gè)好的啟發(fā)式選擇變量的時(shí)候應(yīng)該選擇約束最多的變量，而選擇

14、值得時(shí)候應(yīng)該選擇造成約束最少的。21對(duì)以下兩個(gè)問(wèn)題給出精確的約束滿足問(wèn)題的形式化：a.直線地面規(guī)劃：在一個(gè)大的矩形里找到不重疊放置許多小的矩形的方法。b.授課日程安排：給定了固定數(shù)量的教授和教室，一個(gè)可提供課程的清單，以及可能安排課 程的時(shí)間段清單。每個(gè)教授有他（或她）能教的課程列表。22分別用回溯算法、前向檢驗(yàn)算法、MRV和最少約束值啟發(fā)式算法手工求解下圖（圖5.2）中10的密碼算術(shù)問(wèn)題。(b)(a)圖5.2 （a） 一個(gè)密碼算術(shù)游戲。每個(gè)字母表示一個(gè)不同的數(shù)字：目標(biāo)是找到能使加法式子成立的代替字母的數(shù)字，附加約束是前面的數(shù)字不能是0o （b）密碼算術(shù)游戲的約束超圖，表示了 Alldiff約

15、束和每列相加的約束。每個(gè)約束在圖中用方塊表示，連接到它所約束的變量23 考慮下述的邏輯問(wèn)題：有5 所不同顏色的房子，住著5 個(gè)來(lái)自不同國(guó)家的人，每個(gè)人都喜歡一種不同牌子的香煙、不同牌子的飲料和不同的寵物。給定下列已知條件，請(qǐng)回答問(wèn)題“斑馬住在哪兒？以及哪所房子里的人喜歡喝水？”：英國(guó)人住在紅色的房子里。西班牙人養(yǎng)的是狗。挪威人住在最左邊的第一所房子里。住在黃色房子里的人喜歡抽Kools 牌香煙。喜歡抽Chesterfields牌香煙的人住在養(yǎng)狐貍的人旁邊。挪威人住在藍(lán)色房子旁邊。喜歡抽Winston 牌香煙的人養(yǎng)了一只蝸牛。喜歡抽L(zhǎng)ucky Strike牌香煙的人喜歡喝橙汁。烏克蘭人喜歡喝茶。

16、日本人喜歡抽Parliaments 牌香煙。喜歡抽 Kools 牌香煙的人住在養(yǎng)馬的人的隔壁。住在中間房子里的人喜歡喝牛奶。討論把這個(gè)問(wèn)題表示成CSP 問(wèn)題的不同方法。你認(rèn)為哪種比較好，為什么？24這道習(xí)題以井字棋（圈與十字游戲）為例子，練習(xí)博弈中的基本概念。我們定義Xn為恰好有n 個(gè) X 而沒(méi)有 O 的行、列或者對(duì)角線的數(shù)目。同樣On 為正好有n 個(gè) O 的行、列或者對(duì)角線的數(shù)目。效用函數(shù)給X3=1 的局部賦值+1，給O3=1 的局部賦值-1。所有其它終止局面效用值為 0。對(duì)于非終止局面，我們使用線性的評(píng)價(jià)函數(shù)，定義為Eval （s） = 3X2 （s） + Xi （s） - （3。2 （s

17、） + Oi （s）。a. 估算大約總共有多少種可能的井字棋局面？b. 考慮到對(duì)稱性，給出從空棋盤開(kāi)始到深度為2 的完整博弈樹(shù)（例如，在棋盤上一個(gè)X 和一個(gè) O 的局面）c. 標(biāo)出深度為2 的所有局面的評(píng)價(jià)值。d. 使用極小極大值算法標(biāo)出深度為i 和 0 的局面的回傳值，并根據(jù)這些值選出最佳的起始步。e.假設(shè)節(jié)點(diǎn)按對(duì)a - 3剪枝的最優(yōu)順序生成，圈出如果使用a - 3剪枝將被剪掉的深度為2的節(jié)點(diǎn)。25證明下面的斷言：對(duì)于每棵博弈樹(shù)，MAX使用極小極大值算法對(duì)抗非最優(yōu)招數(shù)的MIN得到的效用值不會(huì)比對(duì)抗最優(yōu)招數(shù)的MIN得到的效用值低。你能構(gòu)造出一棵博弈樹(shù)，使得MA刖非最優(yōu)策略對(duì)抗非最優(yōu) MIN可以

18、做得比使用最優(yōu)策略更好嗎？26考慮圖6.14 （下頁(yè)圖）中描述的兩人游戲。a. 用下面的約定，畫(huà)出完整的博弈樹(shù)：每個(gè)狀態(tài)用（Sa, Sb）表示，其中Sa和Sb表示棋子的位置。每個(gè)終止?fàn)顟B(tài)外面畫(huà)方框，并在圓圈里寫出它的博弈值。把循環(huán)狀態(tài)（已經(jīng)在到根節(jié)點(diǎn)的路徑上出現(xiàn)過(guò)的狀態(tài)）放在雙方框內(nèi)。由于不清楚怎樣給循環(huán)狀態(tài)賦值，在圓圈里標(biāo)記一個(gè)“？”。b. 現(xiàn)在給每個(gè)節(jié)點(diǎn)標(biāo)記回傳得極小極大值（也標(biāo)記在圓圈里）。解釋怎樣處理“？”值和為什么。c.解釋標(biāo)準(zhǔn)的極小極大值算法為什么在這棵博弈樹(shù)中會(huì)失敗，簡(jiǎn)要地勾畫(huà)你可能如何改進(jìn) 它，并在問(wèn)題（b）的圖上畫(huà)出你的答案。你的改進(jìn)算法對(duì)于所有包含循環(huán)的游戲都能給 出最優(yōu)決

19、策嗎？d.這個(gè)4-方格游戲可以推廣到 n個(gè)方格，對(duì)于任意n2。證明如果n是偶數(shù)，A一定能贏;而n是奇數(shù)，A 一定會(huì)輸。圖6.14 一個(gè)簡(jiǎn)單游戲的初始局面。游戲者A先走。然后兩個(gè)游戲者輪流走棋，每個(gè)人必須把自己的棋子移動(dòng)到任一個(gè)方向上的相鄰空位中。如果對(duì)方的棋子占據(jù)著相鄰的位置，你可以跳過(guò)對(duì)方的棋子到下一個(gè)空位，如果有空位的話。（例如，A在位置3, B在位置2,那么A可以移回1。）當(dāng)一方的棋子移動(dòng)到對(duì)方的棋盤端點(diǎn)時(shí)游戲結(jié)束。如果A先到達(dá)位置4, A的游戲值為+1;如果B先到位置1, A的游戲值-1。27給出一個(gè)關(guān)于 -3剪枝正確性的形式化證明。要做到這個(gè)，考慮圖 6.15中的情況。問(wèn)題為 是否要

20、剪掉節(jié)點(diǎn) nj,它是一個(gè) MAX節(jié)點(diǎn)，也是 小的一個(gè)后代?；镜乃悸肥钱?dāng)且僅當(dāng)m的極小極大值可以被證明獨(dú)立于 nj的值時(shí)，才剪枝。圖6.15考慮是否剪掉節(jié)點(diǎn)nj時(shí)的情形a. n i的值由下面公式給出ni = min （n2,n 21, , , n2b2）為n2找到類似的表達(dá)式，因此得到用nj表示ni的表達(dá)式。b.節(jié)點(diǎn)ni的極小極大值已知，li是在節(jié)點(diǎn)ni左側(cè)深度為i的節(jié)點(diǎn)的極小值（或者極大值）。 同樣，m是在ni右側(cè)深度為i的未探索過(guò)的節(jié)點(diǎn)的極小值（或者極大值）。用li和ri的值重寫你的ni表達(dá)式。c.現(xiàn)在調(diào)整你的表達(dá)式來(lái)說(shuō)明為了影響ni, nj必須不超出由li值得到的一個(gè)特定界限。d.對(duì)于n

21、是MIN節(jié)點(diǎn)的情況重復(fù)上面的過(guò)程。28描述把標(biāo)準(zhǔn)的博弈方法運(yùn)用到連續(xù)的物理狀態(tài)空間中進(jìn)行的游戲，諸如網(wǎng)球、臺(tái)球和門球, 效果會(huì)如何？29對(duì)于下列問(wèn)題試用深度優(yōu)先、廣度優(yōu)先、A*算法分別解決，如果步驟太多，可以擇要加以討論。（1）有2n個(gè)硬幣，其中除一個(gè)略重外，其余2n-1個(gè)都一樣重，如果有一架無(wú)祛碼的天平，請(qǐng)求出：至少稱多少次才能把略重的那個(gè)硬幣找出來(lái)？（提示：把2n個(gè)硬幣對(duì)應(yīng)于一個(gè) 2n維狀態(tài)向量，其中每個(gè)硬幣對(duì)應(yīng)于（1）未知（2）略重（3）正常三種狀態(tài)。）（2）下圖是一張西極洲地圖， 共14個(gè)國(guó)家，試用上述3種狀態(tài)搜索法來(lái)解該圖的四色問(wèn)題。（提示：可把狀態(tài)設(shè)計(jì)為一個(gè)別14個(gè)維向量，每個(gè)分量

22、可為紅、黃、藍(lán)、綠四色之一。任意選擇一個(gè)向量，例如全紅，為初始狀態(tài)，每步改變其中的一個(gè)顏色，直到相鄰國(guó)家顏色都不同為止）（3）下圖是由四個(gè)圓環(huán)組成的盤面，每個(gè)圓環(huán)都可以獨(dú)立地繞中心轉(zhuǎn)動(dòng)，每次轉(zhuǎn)動(dòng)90°。圖中所示的是初始狀態(tài)，要達(dá)到目標(biāo)狀態(tài)是每條半徑上的數(shù)字總和為12。試用上述3種狀態(tài)搜索法搜索，并寫出搜索步驟。(4)有四個(gè)正方塊。在每個(gè)正方塊上任意選擇四面，分別涂上紅、黃、藍(lán)、綠四種顏色，其余 兩面隨意各涂這四色之一。請(qǐng)你把四個(gè)方塊疊成一根方柱，使方柱每一面都具備四種不同顏色， 并把搜索過(guò)程用狀態(tài)空間法描述出來(lái)。63.3萬(wàn)柱問(wèn)題(5)有2n個(gè)硬幣排成一行，n個(gè)正向的在左，n個(gè)反向的在右，規(guī)定每次移動(dòng)時(shí)必須把緊挨著的兩個(gè)一起移，只許旋轉(zhuǎn)，要求至多用n步把它們變成正反相間的形式，并且中間不許出現(xiàn)空檔。下圖n=3的情形。初始：正正正反反反第1步移動(dòng)：正反反反正正第2步移動(dòng)：