人工智能試驗(yàn)

1、人工智能導(dǎo)論實(shí)驗(yàn)河南理工大學(xué)人工智能實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)一狀態(tài)空間搜索實(shí)驗(yàn)實(shí)驗(yàn)二A*算法實(shí)驗(yàn)實(shí)驗(yàn)三子句消解實(shí)驗(yàn)實(shí)驗(yàn)四化為子句集的九步法實(shí)驗(yàn)實(shí)驗(yàn)五梵塔問(wèn)題實(shí)驗(yàn)實(shí)驗(yàn)六BP網(wǎng)絡(luò)實(shí)驗(yàn)溫馨提示：上述實(shí)驗(yàn)可以采用任何自己熟悉的語(yǔ)言來(lái)實(shí)現(xiàn)1實(shí)驗(yàn)狀態(tài)空間搜索實(shí)驗(yàn)八數(shù)碼問(wèn)題（必修，2學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康募皟?nèi)容實(shí)驗(yàn)?zāi)康模豪斫夂驼莆諣顟B(tài)空間搜索的策略實(shí)驗(yàn)內(nèi)容要求：現(xiàn)要在一個(gè)3X3的九宮中有1 8，這八個(gè)數(shù)及一個(gè)空格， 隨機(jī)的擺放在其中的格子里, 求實(shí)現(xiàn)這個(gè)問(wèn)題：將該九宮格調(diào)整為某種有序的形式，調(diào)整的原則為每次只能將空格（上、下、左、右） 相鄰的一個(gè)數(shù)字平移到空格中，試編程實(shí)現(xiàn)這一問(wèn)題的求解二、實(shí)驗(yàn)原理及基本技術(shù)路線(xiàn)圖

2、（方框原理圖或程序流程圖）實(shí)驗(yàn)原理：算法分析：實(shí)驗(yàn)流程圖：三、所用儀器、材料（設(shè)備名稱(chēng)、型號(hào)、規(guī)格等或使用軟件）硬件：軟件：四、實(shí)驗(yàn)方法、步驟（或：程序代碼或操作過(guò)程）1. 實(shí)驗(yàn)步驟2. 實(shí)驗(yàn)源程序五、實(shí)驗(yàn)過(guò)程原始記錄（測(cè)試數(shù)據(jù)、圖表、計(jì)算等）六、實(shí)驗(yàn)結(jié)果、分析和結(jié)論實(shí)驗(yàn)二A*算法實(shí)驗(yàn)（2學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康模菏煜ず驼莆諉l(fā)式搜索的定義、估價(jià)函數(shù)和算法過(guò)程， 并利用A*算法求解N數(shù)碼難題，理解求解流程和搜索順序。二、實(shí)驗(yàn)原理：A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。對(duì)于一般的有序搜索， 總是選擇f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。因此，f是根據(jù)需要找到一條最小代價(jià)路徑的觀(guān)點(diǎn)來(lái)估算節(jié)點(diǎn)的

3、，所以，可考慮每個(gè)節(jié)點(diǎn)n的估價(jià)函數(shù)值為兩個(gè)分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的代價(jià)以及從節(jié)點(diǎn) n到達(dá)目標(biāo)節(jié)點(diǎn)的代價(jià)。、實(shí)驗(yàn)條件：1 N數(shù)碼難題演示程序。2 IE6.0 以上，可以上 In ternet。三、實(shí)驗(yàn)內(nèi)容：1 分別以8數(shù)碼和15數(shù)碼為例實(shí)際求解 A*算法。2 畫(huà)出A*算法求解框圖。3 分析估價(jià)函數(shù)對(duì)搜索算法的影響。4 分析A*算法的特點(diǎn)。四、實(shí)驗(yàn)步驟：1 開(kāi)始演示。進(jìn)入 N數(shù)碼難題演示程序，可選 8數(shù)碼或者15數(shù)碼，點(diǎn)擊 選擇數(shù)碼 按鈕確定。第一次啟動(dòng)后，點(diǎn)擊兩次“缺省”或者“隨機(jī)”按鈕，才會(huì)出現(xiàn)圖片。2 點(diǎn)擊“缺省棋局” ，會(huì)產(chǎn)生一個(gè)固定的初始節(jié)點(diǎn)。點(diǎn)擊“隨機(jī)生成” ，會(huì)產(chǎn)生任意排 列的初始

4、節(jié)點(diǎn)。3 算法執(zhí)行。點(diǎn)擊“連續(xù)執(zhí)行”則程序自動(dòng)搜索求解，并演示每一步結(jié)果；點(diǎn)擊“單 步運(yùn)行”則每次執(zhí)行一步求解流程。 “運(yùn)行速度”可自由調(diào)節(jié)。4 觀(guān)察運(yùn)行過(guò)程和搜索順序， 理解啟發(fā)式搜索的原理。 在下拉框中選擇演示 “15 數(shù)碼 難題”，點(diǎn)擊“選擇數(shù)碼”確定選擇；運(yùn)行 15 數(shù)碼難題演示實(shí)例。5 算法流程的任一時(shí)刻的相關(guān)狀態(tài)，以算法流程高亮、open表、close表、節(jié)點(diǎn)靜態(tài)圖、當(dāng)前擴(kuò)展節(jié)點(diǎn)移動(dòng)圖等 5 種形式在按鈕上方同步顯示 ,便于深入學(xué)習(xí)理解 A* 算法。6 根據(jù)程序運(yùn)行過(guò)程畫(huà)出 A* 算法框圖。 其它可參考幫助文件。五、實(shí)驗(yàn)報(bào)告要求：1 A* 算法流程圖和算法框圖。2 試分析估價(jià)函數(shù)的

5、值對(duì)搜索算法速度的影響。 根據(jù) A* 算法分析啟發(fā)式搜索的特點(diǎn)。7實(shí)驗(yàn)三子句消解實(shí)驗(yàn)（2學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康模豪斫夂凶兞康淖泳淙绾问褂孟庖?guī)則，掌握子句消解的原理和規(guī)則，能熟練進(jìn)行任意 兩個(gè)子句的消解，了解消解推理的某些常用規(guī)則。二、實(shí)驗(yàn)原理：對(duì)子句集進(jìn)行消解推理，得到相應(yīng)的結(jié)論。為了對(duì)含有變量的子句使用消解規(guī)則，我們 必須找到一個(gè)置換，作用于父輩子句使其含有互補(bǔ)文字。消解兩個(gè)子句時(shí)，可能有一個(gè)以上 的消解式，不過(guò)，在任何情況下最多有有限個(gè)消解式。三、實(shí)驗(yàn)條件1 子句消解推理演示程序。2 IE6.0 以上，可以上 In ternet。四、實(shí)驗(yàn)內(nèi)容:1 運(yùn)行并觀(guān)察演示實(shí)例。2 輸入新的子句，檢查

6、消解結(jié)果。3 根據(jù)消解過(guò)程理解消解原理和常用規(guī)則。五、實(shí)驗(yàn)步驟：1. 默認(rèn)示例演示。進(jìn)入演示實(shí)例，點(diǎn)擊“演示實(shí)例1 ”，然后點(diǎn)擊“開(kāi)始消解”，得到消解結(jié)果。2. 分別運(yùn)行“演示實(shí)例 2”和“演示實(shí)例 3”，觀(guān)察消解結(jié)果，理解常用消解規(guī)則的應(yīng)用。3. 自定義消解子句。點(diǎn)擊“系統(tǒng)重置”按鈕，再通過(guò)鍵盤(pán)與兩個(gè)按鈕“”與“V” 輸入合法的子句，點(diǎn)擊“加入子句集”加入子句集，點(diǎn)擊“開(kāi)始消解” ，觀(guān)察消解 結(jié)果。4. 重復(fù)步驟 3，多次輸入不同子句進(jìn)行消解，熟悉消解過(guò)程。六、實(shí)驗(yàn)結(jié)論：1 熟悉消解過(guò)程，理解子句消解規(guī)則。2 給出自己輸入的待消解子句、消解結(jié)果和詳細(xì)過(guò)程。實(shí)驗(yàn)四 化為子句集的九步法實(shí)驗(yàn)（2學(xué)

7、時(shí)）一、實(shí)驗(yàn)?zāi)康模豪斫夂驼莆障庠恚煜ぶ^詞公式化為子句集的九個(gè)步驟，理解消解推理規(guī)則，能把 任意謂詞公式轉(zhuǎn)換成子句集。二、實(shí)驗(yàn)原理消解是可用于一定的子句公式的重要推理規(guī)則，任一謂詞演算公式可以化成一個(gè)子句 集。通過(guò)九步法消解可以從這兩個(gè)父輩子句推導(dǎo)出一個(gè)新子句。九步法消解包括消去蘊(yùn)涵符號(hào)、減否定符轄域、對(duì)變量標(biāo)準(zhǔn)化、消去存在量詞、化為 前束型、化為合取范式、消去全程量詞、消去合取符、更換變量名，依次變換即可得到子句、實(shí)驗(yàn)條件:i 子句集轉(zhuǎn)換演示程序。J住為辛句棗的九歩法 Microsoft JntctTiet Ewtorcr.101 XI丈*W期刪E）亙看加收呱迦 zftd）莘陰r ”-

8、衛(wèi)；3 滋整索 國(guó)收慮歷更|苕*% 騎日詡9 Srfett(D) G:Alogramgiite£rgii.hljnq磚到|檻炎”2IE6.0 以上，可以上 In ternet。也空一iff詡K苴坯式化九一八平旬耒的九步法 B| P( y)P( i (y)Vy)Q( y)sp( y)OrP(y)VP(f(x,y)A(Vy)r(x,y)VP(y) H f)hP( y)VP( f( % y) A(3y)Q(斗 y)MP( y). QA.p(y)VP(f(xihy) A(3q)Q(xp q)MP(Q) 0叭 y)VP( f(% y) AQ( % W(s)AMw(藍(lán)) /M>(y)Vfr

9、(f(xty)Aq(xtw(x)AP(»(x) |Va*P( y)VP( f(知 y) )A(則弋 x)VQ( xaW(x)A(Mx)j(f(xty)A( M,(x)V(3(xlw(x)A(M,(x)VftjJ(w(x)> n。) 5 M(町VQ(連(町)J(/MXx)VMX»(x) >(f(x,y)jA.P(q)VQ(qiW(q) J(P(町陰P(肌町) '(f(叫 y)h M(q)w(q(q)("2)加卩2)幕琲鮒諧中，存在沖訶函數(shù)豪刑a|辱甜$ |酣 臥工桔能.J AiI題謝班 程認(rèn)工他-乩“|程1未趾E-團(tuán)|闔化為子可噪二ZiSrSl

10、11：応四、實(shí)驗(yàn)內(nèi)容：理解消解原理，熟悉謂詞公式轉(zhuǎn)換成子句集的步驟。五、實(shí)驗(yàn)步驟:1 對(duì)默認(rèn)謂詞公式進(jìn)行轉(zhuǎn)換。進(jìn)入演示程序，點(diǎn)擊“語(yǔ)法檢查” ，再依次點(diǎn)擊消解過(guò) 程的九個(gè)步驟按鈕，得到消解結(jié)果。2 自定義消解目標(biāo)。點(diǎn)擊“清除”刪除默認(rèn)公式，利用界面鍵盤(pán)輸入新的消解目標(biāo)， 用“大寫(xiě)字母” 、“小寫(xiě)字母”按鍵進(jìn)行輸入中的字母變換。3 語(yǔ)法檢查。點(diǎn)擊“語(yǔ)法檢查”檢查輸入謂詞公式的語(yǔ)法錯(cuò)誤。如無(wú)錯(cuò)誤，則依次點(diǎn) 擊步驟按鈕進(jìn)行消解。4 重復(fù)運(yùn)行 2、3 步，熟悉消解原理和消解過(guò)程。六、實(shí)驗(yàn)報(bào)告要求：1 了解每一步消解的規(guī)則和原則。2 給出一個(gè)謂詞公式消解的詳細(xì)過(guò)程和結(jié)果。3 分析消解原理的特點(diǎn)和原理。9

11、實(shí)驗(yàn)五 BP網(wǎng)絡(luò)實(shí)驗(yàn)（4學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康模豪斫夥聪騻鞑ゾW(wǎng)絡(luò)的結(jié)構(gòu)和原理，掌握反向傳播算法對(duì)神經(jīng)元的訓(xùn)練過(guò)程，了解反向傳播公式。通過(guò)構(gòu)建 BP網(wǎng)絡(luò)實(shí)例，熟悉前饋網(wǎng)絡(luò)的原理及結(jié)構(gòu)。二、實(shí)驗(yàn)原理反向傳播（BP）算法是一種計(jì)算單個(gè)權(quán)值變化引起網(wǎng)絡(luò)性能變化值的較為簡(jiǎn)單的方法。BP算法過(guò)程從輸出節(jié)點(diǎn)開(kāi)始，反向地向第一隱含層（即最接近輸入層的隱含層）傳播由總誤差引起的權(quán)值修正。BP網(wǎng)絡(luò)不僅含有輸入節(jié)點(diǎn)和輸出節(jié)點(diǎn)，而且含有一層或多層隱（層）節(jié)點(diǎn)。輸入信號(hào)先向前傳遞到隱節(jié)點(diǎn)，經(jīng)過(guò)作用后，再把隱節(jié)點(diǎn)的輸出信息傳遞到輸出節(jié)點(diǎn)，最后給 出輸出結(jié)果。三、實(shí)驗(yàn)條件：1 BP網(wǎng)絡(luò)演示程序。2 IE5.0以上版本，能連通

12、In ternet。購(gòu)悅EP1匪堀各弊整JfiAH B&g Wffi* pSizirz)s¥i'131SMM0"1廠(chǎng)DOOOD.a.eM70OSLJ0.0i* «fiDj石比|±北寶祕(mì)EyO.Q 二J ±SpoTo31號(hào)設(shè)眩UP8禪麵兩烙不滋團(tuán)p 擢式對(duì)r巴規(guī)畛妙1*玄毬 *|T5 «*四、實(shí)驗(yàn)內(nèi)容：1 通過(guò)BP網(wǎng)絡(luò)各項(xiàng)參數(shù)的不同設(shè)置，觀(guān)察BP算法的學(xué)習(xí)效果。2 觀(guān)察比較BP網(wǎng)絡(luò)各項(xiàng)參數(shù)變化對(duì)于訓(xùn)練結(jié)果的影響。五、實(shí)驗(yàn)步驟：1 設(shè)置各層神經(jīng)元個(gè)數(shù)設(shè)置。用戶(hù)點(diǎn)擊下拉列表框選擇輸入、隱含、輸出各層神經(jīng)元個(gè)數(shù)，其中隱含層神經(jīng)

13、元個(gè)數(shù)自動(dòng)設(shè)為輸入層神經(jīng)元個(gè)數(shù)（n）的2n+1個(gè)，然后再點(diǎn)擊確定”按鈕，就可以看到所設(shè)置 BP神經(jīng)網(wǎng)絡(luò)示意圖以及系統(tǒng)隨機(jī)生成默認(rèn)的各 層權(quán)值。2 學(xué)習(xí)參數(shù)設(shè)置，用戶(hù)點(diǎn)擊或拖動(dòng)各滾動(dòng)條分別設(shè)置樣本誤差、系統(tǒng)誤差、學(xué)習(xí)速率、動(dòng)量因子、迭代次數(shù)參數(shù)值。3 各層權(quán)值設(shè)置，如果用戶(hù)使用系統(tǒng)隨機(jī)生成默認(rèn)的各層權(quán)值，則進(jìn)行第或選中 “自定義權(quán) ”單選框自定義權(quán)各層權(quán)，在權(quán)值設(shè)置文本域設(shè)置權(quán)值后，單擊其 后“確定 ”按鈕?；螂p擊下方列表框選項(xiàng)，相應(yīng)權(quán)值會(huì)在權(quán)值設(shè)置文本域出現(xiàn)，則進(jìn) 行該權(quán)值修改后， 單擊其后 “確定 ”按鈕，修改后的權(quán)值會(huì)成功地列表框的原位修改。 后兩種方式均會(huì)成功地激活 “確定 ”按鈕。4

14、學(xué)習(xí)樣本設(shè)置，單文本域中出現(xiàn)“入層”字樣表示在單文本域中設(shè)置輸入層神經(jīng)元 信號(hào)向量。單文本域中出現(xiàn)“出層”字樣表示在單文本域中設(shè)置輸出層神經(jīng)元信號(hào) 向量。當(dāng)輸入已完成一個(gè)或一個(gè)以上模式對(duì)， “已設(shè)置完”單選框會(huì)成功地激活， 如選中，則“校正網(wǎng)絡(luò)”按鈕會(huì)成功地激活。樣本列表框也具有如步 3 的雙擊修改 功能。5 “校正網(wǎng)絡(luò)”按鈕成功地激活后，單擊“校正網(wǎng)絡(luò)”按鈕，進(jìn)行網(wǎng)絡(luò)學(xué)習(xí)。當(dāng)學(xué)習(xí) 完成后，“較正結(jié)果如下： ”列表框顯示校正學(xué)習(xí)后的結(jié)果， 用戶(hù)可通過(guò)察看 “學(xué)習(xí)” 是否滿(mǎn)意。 如滿(mǎn)意，則設(shè)置測(cè)試樣本， 進(jìn)行測(cè)試“學(xué)習(xí)”效果。如不滿(mǎn)意， 則可（重 新設(shè)置初始權(quán)值、或?qū)W習(xí)樣本等方式）讓網(wǎng)絡(luò)重新“學(xué)

15、習(xí)” 。六、實(shí)驗(yàn)結(jié)論：1 BP 網(wǎng)絡(luò)的基本結(jié)構(gòu)及 BP 算法的訓(xùn)練過(guò)程。2 試述閾值函數(shù)和權(quán)值變化對(duì) BP 網(wǎng)絡(luò)推理結(jié)果的影響。實(shí)驗(yàn)一狀態(tài)空間搜索實(shí)驗(yàn)樣例八數(shù)碼問(wèn)題一、實(shí)驗(yàn)?zāi)康募皟?nèi)容實(shí)驗(yàn)?zāi)康模豪斫夂驼莆諣顟B(tài)空間搜索的策略實(shí)驗(yàn)內(nèi)容要求：在一個(gè)3X3的九宮中有1 8，這八個(gè)數(shù)及一個(gè)空格， 隨機(jī)的擺放在其中的格子里， 現(xiàn)要 求實(shí)現(xiàn)這個(gè)問(wèn)題：將該九宮格調(diào)整為某種有序的形式，調(diào)整的原則為每次只能將空格（上、下、左、右） 相鄰的一個(gè)數(shù)字平移到空格中，試編程實(shí)現(xiàn)這一問(wèn)題的求解二、實(shí)驗(yàn)原理及基本技術(shù)路線(xiàn)圖（方框原理圖或程序流程圖）實(shí)驗(yàn)原理:八數(shù)碼問(wèn)題中，程序產(chǎn)生的隨機(jī)排列轉(zhuǎn)換成目標(biāo)共有兩種可能，而且這兩種不可

16、能同時(shí)成立,也就是奇數(shù)排列和偶數(shù)排列。我們可以把一個(gè)隨機(jī)排列的數(shù)組從左到右從上到下用一個(gè)數(shù)組 表示，例如18,7,1,5,2,6,3,4,0其中0代表空格。它在奇序列位置上。 在這個(gè)數(shù)組中我們首先計(jì)算它能夠重排列出來(lái)的結(jié)果，公式就是：刀（F（X）=Y，其 中F （X）,就是一個(gè)數(shù)他前面比這個(gè)數(shù)小的數(shù)的個(gè)數(shù)，Y為奇數(shù)和偶數(shù)個(gè)有一種解法。那 么上面的數(shù)組我們就可以解出它的結(jié)果。算法分析：九宮問(wèn)題的求解方法就是交換空格（0）位置，直至到達(dá)目標(biāo)位置 為止。圖形表示就是：EJHId因此可知：九宮的所以排列有9!種，也就是3 6 2 8 8 0種排法，數(shù)據(jù)量是非常大的，我 使用廣度搜索，需要記住每一個(gè)結(jié)點(diǎn)

17、的排列形式，要是用數(shù)組記錄的話(huà)會(huì)占用很多的內(nèi)存， 我們把數(shù)據(jù)進(jìn)行適當(dāng)?shù)膲嚎s。使用DWORD形式保存，壓縮形式是每個(gè)數(shù)字用3位表示， 這樣就是3X9 = 27個(gè)字節(jié)，由于8的二進(jìn)制表示形式1 0 0 0,不能用3位表示，我使 用了一個(gè)小技巧就是將8表示位0 0 0,然后用多出來(lái)的5個(gè)字表示8所在的位置，就可以 用DWORD表示了。用移位和或操作將數(shù)據(jù)逐個(gè)移入，比乘法速度要快點(diǎn)。定義了幾個(gè)結(jié)果來(lái)存儲(chǔ)遍歷到了結(jié)果和搜索完成后保存最優(yōu)路徑。實(shí)驗(yàn)流程圖：*程序結(jié)束19（設(shè)備名稱(chēng)、型號(hào)、規(guī)格等或使用軟件）一臺(tái)，三、所用儀器、材料硬件：個(gè)人計(jì)算機(jī)軟件:Microsoft Visual C+ 6.0四、實(shí)驗(yàn)方

18、法、步驟（或：程序代碼或操作過(guò)程）1. 實(shí)驗(yàn)步驟（1）運(yùn)行 Microsoft Visual C+ 6.0軟件，新建工作空間，得文檔。（2）輸入源程序代碼，進(jìn)行編譯，調(diào)試運(yùn)行。（3）運(yùn)行結(jié)果，按提示要求輸入 18 這八個(gè)數(shù)，進(jìn)行程序測(cè)驗(yàn)。2. 實(shí)驗(yàn)源程序#include <stdio.h>#include <stdlib.h>#include <windows.h>#include <queue>#include <stack> using namespace std;#define HashTableSize 362881#defi

19、ne NOT !#define UP 0#define DOWN 1#define LEFT 2#define RIGHT 3#define Bit char typedef struct mapsBit detail9;int myindex; / 記錄自己節(jié)點(diǎn)在 hash 表中的位置Bit position; / 記錄 空格（ 0 ）在序列中的位置 Map,*PMap;Map org; / 初始狀態(tài)int EndIndex;目標(biāo)/ 上移 ，下移 ，左移 ，右移int const derection4 = -3 , 3 , -1 , 1 ;/ 可移動(dòng)的四個(gè)方向int const Factor

20、ial9 = 40320 , 5040 , 720 , 120 , 24 , 6 , 2 , 1 , 1 ;int HashTableHashTableSize=0;/hash 表,其中記錄的是上一個(gè)父節(jié)點(diǎn)對(duì)應(yīng)的位置/* 八數(shù)碼的輸入 (在這里不做任何輸入檢查， 均認(rèn)為輸入數(shù)據(jù)是正確的 )*/ void input()int i,j;int sum , count ,index ;for(i = 0 ; i < 9 ; i + )scanf("%1d", &org.detail i );org.detail i | (org.position = i) ;fo

21、r(i = 0 ; i < 9 ; i + ) /計(jì)算逆序if( 0 = org.detail i ) continue;for(j = 0 ; j < i; j + )sum += ( 0 != org.detail j && org.detail j < org.detail i );for( i = 0 , index = 0 ; i < 9 ; i + ) / 計(jì)算初始狀態(tài)的 hash 值for(j = 0 , count = 0 ; j < i ; j +)count += org.detail j > org.detail i ;

22、index += Factorial org.detail i * count;org.myindex = index + 1 ;EndIndex = sum%2 ? 161328:322561; / 目標(biāo)狀態(tài)的 hash 值 return;/*hash值的計(jì)算*Parent:父狀態(tài)的hash值*direct:移動(dòng)的方向*/inline int HashValue(Map& Parent , int& direct )int i = Parent.position ;int newindex = Parent.myindex ;Bit *p = Parent.detail;sw

23、itch(direct)case UP :newindex -= 3*40320 ;newindex+= ( p i - 2 > p i - 3 ) ? ( Factorial p i- 3 ) : ( - Factorial p i - 2 );newindex+= ( p i - 1 > p i - 3 ) ? ( Factorial p i- 3 ) : ( - Factorial p i - 1 );break;case DOWN :newindex += 3*40320 ;newindex -= ( p i + 2 > p i + 3 ) ? ( + 3 ) : (

24、 - Factorial p i + 2 );newindex -= ( p i + 1 > p i + 3 ) ? ( + 3 ) : ( - Factorial p i + 1 );break;case LEFT : return newindex - 40320; break;case RIGHT : return newindex + 40320; break;return newindex;/* * *寬度優(yōu)先搜索 */void Bfs()queue<Map> Queue;Queue.push(org);HashTable org.myindex = -1; whi

25、le( NOT Queue.empty() ) Map node = Queue.front();Queue.pop();for(int k =0 ; k < 4; k + )Map tmp = node;tmp.position = node.position + derectionk;if(tmp.position < 0 | tmp.position > 8 tmp.position / 3 != node.position /3 ) )continue; tmp.myindex = HashValue( node , k ); if(0 != HashTabletmp

26、.myindex ) continue;tmp.detail node.position = tmp.detail tmp.position ; tmp.detail tmp.position = 0 ;HashTabletmp.myindex = node.myindex; / 狀態(tài)記錄到if( node.myindex = EndIndex ) return ;Factorial p iFactorial p i| ( k > 1 &&/ 移動(dòng)空格hashtable 中Queue.push( tmp ); return ;/* 通過(guò) hash 表中記錄的進(jìn)行查找路徑

27、*/ void FindPath()int nowindex;int count =0 ;int nixu9, result9;int i, j , k ; stack<int> Stack;Stack.push(EndIndex); nowindex = EndIndex;while( -1 != HashTable nowindex ) Stack.push(HashTable nowindex ); nowindex = HashTable nowindex ;printf(" 共需： %d 步 n",Stack.size()-1); getchar();

28、while( NOT Stack.empty() nowindex = Stack.top() - 1 ; Stack.pop();/ 計(jì)算出逆序/ 根據(jù)逆 序計(jì)算排列for( i = 0 ; i < 9; i + )nixui = nowindex / Factorial i ; nowindex %= Factorial i ; memset( result , -1 , 9 *sizeof(int);for( i =0 ; i < 9 ; i + )for( j = 0 , k = nixui ; j < 9 ; j + ) if(resultj = -1 ) k -; if( k < 0 ) break; resultj = i ; for( i =0 ; i < 9 ; i + )prin tf("%3d",resulti);if( 2 = i % 3 ) prin tf("n");if(0 != Stack.size()printf("nJ 第眇n",+count)