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

1、滑塊問(wèn)題求解系統(tǒng)報(bào)告一、設(shè)計(jì)任務(wù)：以八數(shù)碼問(wèn)題為例，設(shè)計(jì)一類(lèi)滑塊問(wèn)題的求解系統(tǒng)初，步掌握智能搜索算法中的盲目搜索和啟發(fā)式搜索這兩類(lèi)基本方法同，時(shí)通過(guò)具體的問(wèn)題體會(huì)搜索算法數(shù)、據(jù)結(jié)構(gòu)、程序設(shè)計(jì)等知識(shí)的綜合應(yīng)用。2831231484765765圖 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)為123456780（2） 手動(dòng)布局：用戶可以手動(dòng)輸入起始狀態(tài)和終點(diǎn)狀態(tài)，空格用0 表示（3） 導(dǎo)入布局：用戶輸入結(jié)束后把布局導(dǎo)入到程序中（4） 隨機(jī)生成：包括（起始

2、狀態(tài)）（目標(biāo)狀態(tài)）的隨機(jī)生成，避免無(wú)解可以產(chǎn)生一個(gè)有解狀態(tài)八數(shù)（碼建。議勾選）(5) 如下圖進(jìn)行導(dǎo)入操作：（單擊左框狀態(tài)設(shè)置欄的“導(dǎo)入布局”按鈕）b）算法選擇區(qū)C）當(dāng)前步驟欄目：顯示當(dāng)前進(jìn)行的步數(shù)統(tǒng)計(jì)（如圖）d) 操作欄恢復(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ā)函數(shù)一：f(n)=g(n)+h(n)其中g(shù)（n）為當(dāng)前節(jié)點(diǎn)深度，h（n）為直線距離b. 啟發(fā)函數(shù)二：1 (

3、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/定義NODE結(jié)構(gòu)int Id;/ 當(dāng)前結(jié)點(diǎn)IDint arr=new int33;/八數(shù)碼狀態(tài)數(shù)組int FatherId;/ 父親結(jié)點(diǎn)的IDint g;/ 深度int f;/ 權(quán)值int h;/ 曼哈頓long hash;/ 哈希值OPEN表：存放未檢查和擴(kuò)展的節(jié)點(diǎn)CLOSED表：存放已檢查和擴(kuò)展的節(jié)

4、點(diǎn)規(guī)則：1從OPEN表中取出一個(gè)節(jié)點(diǎn)n，檢查其是否為目標(biāo)節(jié)點(diǎn)，若是則搜索成功，返回結(jié)果路徑。2將n放入CLOSED表中。3擴(kuò)展n的子節(jié)點(diǎn)，檢查重復(fù)性，放OPEN入表中。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(int j = 0;j<i;j+)if(startsi<startsj&&startsi!=0)count1+;/統(tǒng)計(jì)初始狀態(tài)的逆序數(shù)for(int i = 0;i<9;i+)for(int j = 0;j<i

5、;j+)if(endsi<endsj&&endsi!=0)count2+;/統(tǒng)計(jì)目標(biāo)狀態(tài)的逆序數(shù)if(count1%2=count2%2)return true;有解-");elsereturn false;無(wú)解-");5. 實(shí)現(xiàn)中遇到的問(wèn)題在做盲目搜索時(shí)，因?yàn)槲疫x擇的是深度優(yōu)先搜索，所以就要用stack,到當(dāng)時(shí)有自己定義一個(gè)stack類(lèi)，不過(guò)在這之后我在java的 API文檔中發(fā)現(xiàn)了有一個(gè)vertor類(lèi)，可以很方便的模擬stack，新添時(shí)加入到最后，取數(shù)時(shí)從最后一個(gè)開(kāi)始取，這樣就可以模擬stack了。6部分關(guān)鍵代碼/=/進(jìn)行 OPEN表排序操作/=p

6、ublicvoid QueueOpen()/=OPEN表排序，只用找F值最小的設(shè)為第一個(gè)NODE=intmin_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);/ 把 OPEN表的第一個(gè)拿出來(lái)賦值給node_flagintminvalue=node_flag.f ; / 然后看看第一個(gè)的權(quán)值，暫且放MINVALUE，把第一個(gè)默認(rèn)是最小的，然后進(jìn)行更新for ( int

7、i=0;i<open.size();i+)/ 開(kāi)始比較了Nodeopei=(Node) open.get(i);/ 這里的 get 只是查看，所以沒(méi)有修改是看哪個(gè)最小所以不要POPif (opei.f <minvalue)/ 找到一個(gè)比第一個(gè)更小的OPEN表，我們目的minvalue=opei.f ; /來(lái)了，進(jìn)行更新了min_flag=i;/ 記錄這個(gè)最小的位置在OPEN表的哪個(gè)地方temp=(Node)open.get(0);/ 把 OPEN表的第一個(gè)放到temp里面 =也就是先記錄第一個(gè)結(jié)點(diǎn)open.setElementAt(Node)open.elementAt(min_flag),0);/ 好好講下這個(gè)函數(shù)方法了/ 這個(gè)括號(hào)里面什么意思呢？就是把OPEN表里面min_flag我們記錄的那個(gè)結(jié)點(diǎn)放到第一個(gè)位置（ 0代表 OPEN第一個(gè)），前面<NODE>指明/ 了他是一個(gè)結(jié)點(diǎn)，是不是很明了了？open.setElementAt(temp,min_flag);/ 你把那個(gè)第一個(gè)放了最小的，我這個(gè)原本第一個(gè)放哪里？/ 當(dāng)然是放到那個(gè)min_flag的位置啦五結(jié)果圖示及分析六算法效率相同輸入：243185670相同輸出：635207481盲目搜索執(zhí)行時(shí)間：2609ms執(zhí)行