寬度優(yōu)先n皇后實驗報告

1、本科實驗報告課程名稱：人工智能實驗項目：實驗地點：實驗室110專業(yè)班級：學(xué)號學(xué)生姓名：指導(dǎo)教師：2016 年 4 月 24 0太原理工大學(xué)學(xué)生實驗報告學(xué)院名稱計算機科學(xué)與技術(shù)專業(yè)班 級計 z1303學(xué)號2013002007學(xué)生姓名宋純顯實驗日期20160420成績課程名稱人工智能實驗題目寬度優(yōu)先n皇后一、實驗?zāi)康暮鸵笫煜ず驼莆諏挾葍?yōu)先搜索的定義和算法過程，并利用 寬度優(yōu)先算法求解n皇后問題，理解求解流程和搜索順 序。理解n皇后問題，并且用寬度優(yōu)先算法求解。二、實驗內(nèi)容和原理用基于寬度優(yōu)先搜索的方法求解n皇后問題。n皇后：在nxn格的國際象棋上擺放八個皇后，使其不能 互相攻擊，即任意兩個皇后都

2、不能處于同一行、同一列或 同一斜線上，問有多少種擺法。寬度優(yōu)先算法：寬度優(yōu)先算法從一般的圖搜索算法演變而 來。在寬度優(yōu)先算法中，每次選擇深度最淺的結(jié)點優(yōu)先拓 展。將拓展的結(jié)點放在open表的最前邊。三、主要儀器設(shè)備 計算機，實驗操作環(huán)境(jdk, eclipse),四、操作方法與實驗步驟1. 先熟悉寬度優(yōu)先算法的基本概念；2. 熟悉n皇后問題的概念；3. 用編程語言編程實現(xiàn)實驗內(nèi)容；4. java環(huán)境下的實驗代碼如下： 代碼：package ai2;import java< util. linkedlist;import java .util. queue;import java.uti

3、l. seanner;public class a12 /* param args*/static queue<queen> opcn 二 new linkedlist<queon>(); static qucue<queen> closed = new linkedlist<queen>(); static int a;public static void main(string args) / todo auto-generated method stub int w 二 0;system, out. printin ("請輸入 r

4、t);scanner sc = new sea rm er (system, in);a = sc. ncxtlnt ();queen ql;ql = new queen(0, null);open.offer(ql);system, out. println(，z結(jié)果為：);while (!open. isempty() queen n = open, poll ();/ closed, offer (n);if (n. deepa) /system.out. printin(pk)； for (int i 二 0; i < n.deep; i+) system, out. print

5、 (n. pathfi); system out printsys tent out. pri；system, out. println();w+;elseexpand(n);system out print!n(w);static void expand(queon q) for (int i = 0; i < a; i卄)queen queen = new queen (q. deep + 1, q. path); queen.setnext (i);if (check(queen) open.of fer (queen);static boolean check(queen q)

6、for (int i = 0; i < q. deep - 1; i+) if (q. pathi = q. pathq. deep-1) | |(math, abs(i-qdcep+1) = math.abs(q. pathi 一 q. pathq. deep-1) return false;return true;class queen int path;int deep;queen (int deep, int path) this deep = deep;if (this, deep = 0) this.path = new int1: else this. path=new i

7、nt deep;for (int i 二 0; i < deep - 1; i+) this, pathi = pathi;void setnext (int i) this. paththis .deep - 1 = i;五：實驗結(jié)果與分析4皇后uterminated> ai2 java application h:ji 請輸入n結(jié)果為：1,3,0幾28皇后problems javadoc 屬 declaration貝 console :w 苜 hi stor、<terminated> ai2 java application h:javabinjavaw.exe (

8、2016-4-5,7,2,3,0,6,4,2,60,2,7,5,3,2,4,62,3,0,7,4,2,5,62,5,2,0,3,7,4,62,0,5,7,4,2,3,6,2,7,2,4,0,5,3,63,2,4,7,0,2,5,63,2,7,5,0,2,4,6,4,2,0,5,7,2,3,7,2,3,0,6,4,2,5,7,2,4,2,0,6,3,5,7,2,0,5,2,4,6,3,7,3,0,2,5,2,6,4,92木程序理論上可以達到n皇后（n為人于等于4的任意白然數(shù)），但是實際上由于電腦 性能的現(xiàn)在，在11皇后的時候會發(fā)現(xiàn)很明顯的延遲，12皇后人約需要5秒，13皇后 幾分鐘，14皇后15-20分鐘，15皇后就需要2小時以上了。六.討論、心得通過此次實驗，對回溯法有了深刻的理解，對遞歸方面得到 鞏固，還有編程方面的知識。在編寫n皇后算法的過程中，此次采用寬度優(yōu)