1、人工智能實(shí)驗(yàn)報(bào)告姓 名：處添加內(nèi)容學(xué) 號(hào)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)所學(xué)專業(yè)：八數(shù)碼演示程序報(bào)告題目：2010年4月9日提交日期：八數(shù)碼演示程序1. 問題描述1.1八數(shù)碼問題的解釋八數(shù)碼問題是人工智能經(jīng)典難題之一。問題是在3×3 方格盤上，放有八個(gè)數(shù)碼，剩下一個(gè)為空，每一空格其上下左右的數(shù)碼可移至空格。問題給定初始位置和目標(biāo)位置，要求通過一系列的數(shù)碼移動(dòng)，將初始位置轉(zhuǎn)化為目標(biāo)位置。本文介紹用A星算法，采用估計(jì)值h（n）（曼哈頓距離）和g(m)(當(dāng)前深度)的和作為估計(jì)函數(shù)。1.2八數(shù)碼問題的搜索形式描述初始狀態(tài)：初始狀態(tài)向量，規(guī)定向量中各分量對(duì)應(yīng)的位置，各位置上的初始數(shù)字<0，1，3，

2、4，5，6，7，8，2>后繼函數(shù)：移動(dòng)規(guī)則，按照某條規(guī)則移動(dòng)數(shù)字得到的新向量<0，1，3，4，5，6，7，8，9>轉(zhuǎn)移到<4，1，3，0，5，6，7，8，2>目標(biāo)測(cè)試：新向量是否是目標(biāo)狀態(tài)，也即為<0，1，2，3，4，5，6，7，8>路徑耗散函數(shù)：在搜索時(shí)，每深入一層則當(dāng)前步數(shù)代價(jià)加1，代價(jià)總和由當(dāng)前步數(shù)和可能還需要移動(dòng)的步數(shù)之和。1.3 解決方案介紹首先，A*算法需要個(gè)估價(jià)(評(píng)價(jià))函數(shù):f(x)=g(x)+h(x)g(x)通常表示移動(dòng)至當(dāng)前狀態(tài)需要的步數(shù)，h(x)則是啟發(fā)函數(shù)。在算法進(jìn)行的時(shí)候，我們將對(duì)每一個(gè)可能移動(dòng)到的狀態(tài)做評(píng)價(jià)，計(jì)算其f(x)，然

3、后將其放入一個(gè)OPEN數(shù)組中，最后我們選取OPEN中f(x)值最小的狀態(tài)作為下一步，再重復(fù)上 述過程，因?yàn)閒(x)值最小的狀態(tài)意味著它最有可能(不是一定)最接近最終狀態(tài)。2. 算法介紹2.1 搜索算法一般介紹A*算法是一種啟發(fā)式搜索算法，是常用的最短路搜尋算法，在游戲領(lǐng)域中有廣泛的應(yīng)用。所謂啟發(fā)式算法，它與常規(guī)的搜索方法最大的不同是在執(zhí)行過程中始終有一個(gè)提示性的信息在引導(dǎo)著算法的進(jìn)行，使得我們不斷靠近目標(biāo)而不是盲目的遍歷，這個(gè)提示信息就是由啟發(fā)函數(shù)產(chǎn)生的，啟發(fā)函數(shù)的好壞將直接影響算法的效率，從幾篇文獻(xiàn)看來，A*算法和廣度優(yōu)先、深度優(yōu)先算法相比是有很明顯的效率優(yōu)勢(shì)的。2.2 算法偽代碼Initi

4、alize OPEN、CLOSE、初始狀態(tài)source，最終狀態(tài)dest;Push(source, OPEN);While(!OPEN.isEmpty()FindFirstElementOfOpen();cuNode=Pop(OPEN);If isTheSame(cuNode,dest)Then exit;Push(cuNode,close)Extend(cuNode);ExtendNewNode(NewNode)IfCLOSE.NOTcontains(NewNode)ThenIfOPEN.NOTcontains(NewNode)Push(NewNode,OPEN);ElseIf OPEN.g

5、et(NewNode).f>NewNode.fThenPush(NewNode,OPEN);3. 算法實(shí)現(xiàn)3.1 實(shí)驗(yàn)環(huán)境與問題規(guī)模本文采用java語言進(jìn)行程序設(shè)計(jì)，在圖形界面上可以顯示八數(shù)碼格局，并可以隨機(jī)生成新的起始狀態(tài)和目標(biāo)狀態(tài)。問題規(guī)模為8，解決八數(shù)碼問題，但可以比較容易就能修改為對(duì)15數(shù)碼問題的求解。3.2 數(shù)據(jù)結(jié)構(gòu)1.類Node，表示一個(gè)結(jié)點(diǎn)，也即搜索過程中的某一個(gè)狀態(tài)，其內(nèi)部數(shù)據(jù)成員有ID（可以唯一地表示一個(gè)狀態(tài)結(jié)點(diǎn)），parentID（該狀態(tài)結(jié)點(diǎn)的母結(jié)點(diǎn)，保存這個(gè)值是為了在找到目標(biāo)結(jié)點(diǎn)時(shí)可以回溯其路徑），a（一個(gè)二維數(shù)組，用于存放當(dāng)前八數(shù)碼的狀態(tài)），g（表示從起始狀態(tài)結(jié)點(diǎn)

6、開始到當(dāng)前狀態(tài)結(jié)點(diǎn)所走過的步數(shù)），h（表示從當(dāng)前狀態(tài)結(jié)點(diǎn)到目標(biāo)狀態(tài)結(jié)點(diǎn)有可能還要走多少步數(shù)），f（就是g值與h值的和）。2.OPEN表，實(shí)現(xiàn)的時(shí)候使用的是HashMap，以保證所存的每一個(gè)狀態(tài)的唯一性；Open表的用途是存放產(chǎn)生的可能的新狀態(tài)，這些新狀態(tài)有待于擴(kuò)展。3.CLOSE表，實(shí)現(xiàn)的時(shí)候使用的是HashMap，以保證所存的每一個(gè)狀態(tài)的唯一性；存放ID=>Node結(jié)點(diǎn)鍵值對(duì)， 用途是記錄已經(jīng)訪問過的狀態(tài)。3.3 實(shí)驗(yàn)結(jié)果起始狀態(tài)2 1 0 7 8 5 4 3 6 終結(jié)狀態(tài)0 1 2 3 4 5 6 7 8 目標(biāo)可達(dá)，總執(zhí)行步數(shù)為21步，搜索算法所耗時(shí)間為31毫秒3.4 系統(tǒng)中間及最終

7、輸出結(jié)果（要求有屏幕顯示）1.無解時(shí)的情形：2.有解時(shí)的情形：起始狀態(tài)：自動(dòng)演示時(shí)的移動(dòng)過程截圖：最后達(dá)到目標(biāo)狀態(tài)：參考文獻(xiàn)人工智能游戲編程真言 (美) Steve Rabin主編Java項(xiàng)目開發(fā)實(shí)踐 陸正武, 張志立編著Java SE 6.0編程指南 吳亞峰, 紀(jì)超編著數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實(shí)現(xiàn)與習(xí)題解答 汪杰等編著Swing Hacks:100個(gè)業(yè)界最尖端的技巧和工具 Joshua Marinacci, Chris Adamson著Java綜合實(shí)例經(jīng)典 吳其慶編著附錄源代碼及其注釋（算法部分，不包括界面設(shè)計(jì)的代碼）：package MyAI;import java.util.HashMap;im

8、port java.util.Iterator;import java.util.Map;import java.util.Vector;import java.util.Map.Entry;class Node Long ID;Long parentID;int a;int g;int h;int f;Node(long ID, long parentID, int a, int g, int h) this.ID = ID;this.parentID = parentID;this.a = a;this.g = g;this.h = h;this.f = g + h;public clas

9、s EightNumber private Map<Long, Node> open = new HashMap<Long, Node>();private Map<Long, Node> close = new HashMap<Long, Node>();private int source=null;private int dest=null;public EightNumber(int source,int dest) this.source=source;this.dest=dest;public Vector<Node> p

10、rocess() Node s = new Node(computeID(source), 0, source, 0, computeH(source,dest);/ 令起始結(jié)點(diǎn)的母結(jié)點(diǎn)ID為0Node d = new Node(computeID(dest), 0, dest, 0, 0);/ 目標(biāo)狀態(tài)的母結(jié)點(diǎn)未知，g值未知System.out.println("起始狀態(tài)");printNode(s);System.out.println("終結(jié)狀態(tài)");printNode(d);if (!resolvable(this.source,this.des

11、t) return null;push(s, open);Node cuNode = s;/int count = 0;while (!open.isEmpty() /count+;cuNode = pop(open);if (isTheSame(cuNode, d) System.out.println("找到目標(biāo)");break;push(cuNode, close);extendNode(cuNode, d);return printResult(cuNode);private Vector<Node> printResult(Node cuNode) i

12、nt count=0;Vector<Node> result=new Vector<Node>();while (cuNode.parentID != 0) count+;result.add(cuNode);printNode(cuNode);cuNode = close.get(cuNode.parentID);printNode(cuNode);System.out.println("總共經(jīng)過"+count+"步數(shù)");return result;private void printNode(Node cuNode) for

13、 (int i = 0; i < 3; i+) for (int j = 0; j < 3; j+) System.out.print(cuNode.aij + " ");System.out.println();System.out.println("-");private void extendNode(Node cuNode, Node dest) int heng = 0, zong = 0;/ i,j分別為0的橫縱坐標(biāo)for (int i = 0; i < 3; i+)for (int j = 0; j < 3; j+)

14、if (cuNode.aij = 0) heng = i;zong = j;break;if (zong - 1 >= 0) / 如果0可以往左邊移動(dòng)int state = new int33;for (int i = 0; i < 3; i+)for (int j = 0; j < 3; j+)stateij = cuNode.aij;statehengzong = cuNode.ahengzong - 1;statehengzong - 1 = 0;extend(state, cuNode, dest);if (zong + 1 <= 2) / 如果0可以往右邊移動(dòng)

15、int state = new int33;for (int i = 0; i < 3; i+)for (int j = 0; j < 3; j+)stateij = cuNode.aij;statehengzong = cuNode.ahengzong + 1;statehengzong + 1 = 0;extend(state, cuNode, dest);if (heng - 1 >= 0) / 如果0可以往上邊移動(dòng)int state = new int33;for (int i = 0; i < 3; i+)for (int j = 0; j < 3; j

16、+)stateij = cuNode.aij;statehengzong = cuNode.aheng - 1zong;stateheng - 1zong = 0;extend(state, cuNode, dest);if (heng + 1 <= 2) / 如果0可以往下邊移動(dòng)int state = new int33;for (int i = 0; i < 3; i+)for (int j = 0; j < 3; j+)stateij = cuNode.aij;statehengzong = cuNode.aheng + 1zong;stateheng + 1zong

17、= 0;extend(state, cuNode, dest);private void extend(int state, Node cuNode, Node dest) Node node = new Node(computeID(state), cuNode.ID, state, cuNode.g + 1,computeH(state, dest.a);if (!close.containsKey(node.ID) if (!open.containsKey(node.ID)push(node, open);else if (open.get(node.ID).f > node.f

18、)push(node, open);private boolean isTheSame(Node cuNode, Node d) if (cuNode.ID.equals(d.ID)return true;return false;private void push(Node a, Map<Long, Node> open2) open2.put(a.ID, a);private Node pop(Map<Long, Node> open2) Iterator<Entry<Long, Node>> it = open.entrySet().ite

19、rator();Map.Entry<Long, Node> e = it.next();int fmin = e.getValue().f;Node node = e.getValue();while (it.hasNext() e = it.next();if (e.getValue().f < fmin) fmin = e.getValue().f;node = e.getValue();return open2.remove(node.ID);public static boolean resolvable(int source,int dest) int count1

20、 = 0;int count2 = 0;int starts = transform1(source);int ends = transform1(dest);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; j+)if (endsi < endsj &&

21、endsi != 0)count2+; / 統(tǒng)計(jì)目標(biāo)狀態(tài)的逆序數(shù)if (count1 % 2 = count2 % 2) System.out.println("-有解-");return true; else System.out.println("-無解-");return false;private long computeID(int a) long sum = 0;for (int i = 0; i < 3; i+)for (int j = 0; j < 3; j+) sum = sum * 10 + aij;return sum;private int computeH(int node, int dest) int count = 0;for (int i = 0; i <= 2; i+)for (int j = 0; j <= 2; j+)for (int g = 0; g <= 2; g+)for (int k = 0; k <= 2; k+) if (nodeij = destgk