滑塊問(wèn)題求解系統(tǒng)報(bào)告

1、滑塊問(wèn)題求解系統(tǒng)報(bào)告一、 設(shè)計(jì)任務(wù)：以八數(shù)碼問(wèn)題為例設(shè)計(jì)一類滑塊問(wèn)題的求解系統(tǒng)初步掌握智能搜索算法中的 盲目搜索和啟發(fā)式搜索這兩類基本方淑時(shí)通過(guò)具體的問(wèn)題體會(huì)搜索算法攵 據(jù)結(jié)構(gòu)、程序設(shè)計(jì)等知識(shí)的綜合應(yīng)用。28312314 -484765765圖1 8數(shù)碼問(wèn)題示意圖二設(shè)計(jì)環(huán)境及使用說(shuō)明操作系統(tǒng)Windows Xp開(kāi)發(fā)平臺(tái)eclipse開(kāi)發(fā)語(yǔ)言:java三系統(tǒng)已實(shí)現(xiàn)的功能a）狀態(tài)設(shè)置欄：（如圖）(1)默認(rèn)終態(tài)：本程序默認(rèn)終態(tài)為23456780手動(dòng)布局:狀態(tài)設(shè)臂隨機(jī)生成態(tài)，空格用0表示導(dǎo)入布局:隨機(jī)生成：包括（起始狀態(tài)）（目標(biāo)狀態(tài)）生成,避免無(wú)解可以產(chǎn)生一個(gè)有解狀態(tài)八數(shù)碼建起始狀態(tài)目標(biāo)伏態(tài)避免無(wú)解議

2、勾選）（5）如下圖進(jìn)行導(dǎo)入操作：（單擊左框狀態(tài)設(shè)置欄的“導(dǎo)入布局”按鈕）23857641衲始伏蠱:23S7E5410.盲目搜索:-A*算法2當(dāng)前步數(shù)終點(diǎn)狀態(tài):124376560b）算法選擇區(qū)C）當(dāng)前步驟欄目：顯示當(dāng)前進(jìn)行的步數(shù)統(tǒng)計(jì)（如圖）當(dāng)前步數(shù)0d）操作欄執(zhí)行時(shí)間： 執(zhí)廳步數(shù)： 已擴(kuò)展結(jié)點(diǎn): 未擴(kuò)展結(jié)點(diǎn).：j開(kāi)始攙索自動(dòng)滴示退出恢復(fù)初態(tài)：演示后恢復(fù)到初始狀態(tài)開(kāi)始搜索：搜索是否有解及步數(shù)自動(dòng)演示：界面將實(shí)時(shí)顯示求解過(guò)程e)界面選擇輸入初始時(shí)，每個(gè)格子均顯示所有數(shù)字，之后根據(jù)用戶選擇動(dòng)態(tài)更新候選數(shù)四算法思想及分析1采用算法 盲目搜索(深度優(yōu)先)，啟發(fā)式搜索兩種2. 設(shè)計(jì)的思想(啟發(fā)函數(shù))a.啟發(fā)

3、函數(shù)一：f(n)=g(n)+h(n)其中g(shù) (n)為當(dāng)前節(jié)點(diǎn)深度,h (n)為直線距離b.啟發(fā)函數(shù)二：1 (7向下一次+ 1 (2向上一次+ 2 (4向左兩次+ 3 (6向右兩次，向上一次 + 2 (5向上一次向左一次二9f(n)=g(n)+h(n)其中g(shù) (n)為當(dāng)前節(jié)點(diǎn)深度,h (n)為曼哈頓距離 3數(shù)據(jù)結(jié)構(gòu)定義了一個(gè)結(jié)構(gòu)體，每個(gè)如左圖結(jié)點(diǎn)都包含如下信息：class Node/定義NOD結(jié)構(gòu)int Id;/當(dāng)前結(jié)點(diǎn)Dint arr=new int33;/八數(shù)碼狀態(tài)數(shù)組int FatherId;/父親結(jié)點(diǎn)的Dint g;/深度int f;/權(quán)值int h;/曼哈頓long hash;/哈希值

4、OPE表 :存放未檢查和擴(kuò)展的節(jié)點(diǎn)CLOSED存放已檢查和擴(kuò)展的節(jié)點(diǎn)規(guī)則：1. 從OPES中取出一個(gè)節(jié)點(diǎn)，檢查其是否為目標(biāo)節(jié)點(diǎn)，若是則搜索成功，返回 結(jié)果路徑。2. 將n放ACLOSgDo3. 擴(kuò)展的子節(jié)點(diǎn)，檢杳重復(fù)性，放入PE表中。4)主要的實(shí)現(xiàn)框架兩個(gè)隨機(jī)狀態(tài)之間是否可達(dá)，可以通過(guò)計(jì)算兩者的逆序值，若兩者奇偶性相同則可達(dá)，否則兩個(gè)狀 態(tài)不可達(dá)。(關(guān)鍵算法)for(int i = 0;i<9;i+)for(i nt j = O;j<i;j+)if(startsi<startsj &&startsi!=0)coun t1+;/ 統(tǒng)計(jì)初始狀態(tài)的逆序數(shù)for(i

5、nt i = 0;i<9;i+)for(i nt j = O;j<i;j+)if(e ndsi<e ndsj&&en dsi!=O)cou nt2+;/統(tǒng)計(jì)目標(biāo)狀態(tài)的逆序數(shù)if(cou nt1%2=cou nt2%2)System.out.println(” 有解");return true;elseSystem.out.println(” 無(wú)解");return false;5.實(shí)現(xiàn)中遇到的問(wèn)題在做盲目搜索時(shí)，因?yàn)槲疫x擇的是深度優(yōu)先搜索，所以就要用到當(dāng)時(shí)有自己定義一 個(gè)stack類，不過(guò)在這之后我在ava的API文檔中發(fā)現(xiàn)了有一個(gè)erto

6、r類，可以很方便的模按tacK新添時(shí)加入到最后，取數(shù)時(shí)從最后一個(gè)開(kāi)始取, 這樣就可以模擬stack了。6.部分關(guān)鍵代碼/=/進(jìn)行OPEN!排序操作/= public void QueueOpen()/=OPEN表排序，只用找 F值最小的設(shè)為第一個(gè) NODE=int min_flag=0; / 最小的位置int arr= new int 33;/初始化一個(gè)2維數(shù)組放結(jié)點(diǎn)Nodetemp =new Node(0,0,arr,0,0,0,0);/初始化一個(gè)結(jié)點(diǎn)結(jié)構(gòu)，都是0,當(dāng)然只是初始化Node node_flag=(Node)open.get(0);/ 把OPE表的第一個(gè)拿岀來(lái)賦值給node_fl

7、agint minvalue=node_flag.f; /然后看看第一個(gè)的權(quán)值，暫且放 MINVALUE把第一個(gè)默認(rèn)是最小的，然后進(jìn)行更新for (int i=0;i< open.size();i+)/開(kāi)始比較了Node opei=(Node) open.get(i);/這里的get只是查看，所以沒(méi)有修改OPE表，我們目的是看哪個(gè)最小所以不要POPif (opei. f <minvalue)/找到一個(gè)比第一個(gè)更小的minvalue=opei.f; / 來(lái)了，進(jìn)行更新了min_flag=i;/記錄這個(gè)最小的位置在OPEf表的哪個(gè)地方temp=(Node)open.get(0); /把

8、OPE表的第一個(gè)放到 temp里面=也就是先記錄第一個(gè)結(jié)占八、open.setElementAt(Node)open.elementAt(min_flag),O);/ 好好講下這個(gè)函數(shù)方法了/這個(gè)括號(hào)里面什么意思呢？就是把OPEf表里面min_flag我們記錄的那個(gè)結(jié)點(diǎn)放到第一個(gè)位置(0代表OPEf第一個(gè))，前面vNODE指明/ 了他是一個(gè)結(jié)點(diǎn)，是不是很明了了？open.setElementAt(temp,min_flag);/你把那個(gè)第一個(gè)放了最小的，我這個(gè)原本第一個(gè)放哪里？/當(dāng)然是放到那個(gè)min_flag的位置啦五.結(jié)果圖示及分析文燉殆朋主題狀瑟役豈起殆伏苗 口目標(biāo)杭謬謹(jǐn)免無(wú)解'12345678初舲我態(tài)；C盲目攬素C打算去1匚當(dāng)前歩敢012345678辭點(diǎn)裁喜；目動(dòng)糧示退出六.算法效率 相同輸入：243185670相同輸出:635207481盲目搜索執(zhí)行時(shí)間：2