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

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

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

4、alize OPEN、CLOSE、初始狀態source，最終狀態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. 算法實現3.1 實驗環境與問題規模本文采用java語言進行程序設計，在圖形界面上可以顯示八數碼格局，并可以隨機生成新的起始狀態和目標狀態。問題規模為8，解決八數碼問題，但可以比較容易就能修改為對15數碼問題的求解。3.2 數據結構1.類Node，表示一個結點，也即搜索過程中的某一個狀態，其內部數據成員有ID（可以唯一地表示一個狀態結點），parentID（該狀態結點的母結點，保存這個值是為了在找到目標結點時可以回溯其路徑），a（一個二維數組，用于存放當前八數碼的狀態），g（表示從起始狀態結點

6、開始到當前狀態結點所走過的步數），h（表示從當前狀態結點到目標狀態結點有可能還要走多少步數），f（就是g值與h值的和）。2.OPEN表，實現的時候使用的是HashMap，以保證所存的每一個狀態的唯一性；Open表的用途是存放產生的可能的新狀態，這些新狀態有待于擴展。3.CLOSE表，實現的時候使用的是HashMap，以保證所存的每一個狀態的唯一性；存放ID=>Node結點鍵值對， 用途是記錄已經訪問過的狀態。3.3 實驗結果起始狀態2 1 0 7 8 5 4 3 6 終結狀態0 1 2 3 4 5 6 7 8 目標可達，總執行步數為21步，搜索算法所耗時間為31毫秒3.4 系統中間及最終

7、輸出結果（要求有屏幕顯示）1.無解時的情形：2.有解時的情形：起始狀態：自動演示時的移動過程截圖：最后達到目標狀態：參考文獻人工智能游戲編程真言 (美) Steve Rabin主編Java項目開發實踐 陸正武, 張志立編著Java SE 6.0編程指南 吳亞峰, 紀超編著數據結構經典算法實現與習題解答 汪杰等編著Swing Hacks:100個業界最尖端的技巧和工具 Joshua Marinacci, Chris Adamson著Java綜合實例經典 吳其慶編著附錄源代碼及其注釋（算法部分，不包括界面設計的代碼）：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);/ 令起始結點的母結點ID為0Node d = new Node(computeID(dest), 0, dest, 0, 0);/ 目標狀態的母結點未知，g值未知System.out.println("起始狀態");printNode(s);System.out.println("終結狀態");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("找到目標");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("總共經過"+count+"步數");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的橫縱坐標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可以往左邊移動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可以往右邊移動

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可以往上邊移動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可以往下邊移動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+; / 統計初始狀態的逆序數for (int i = 0; i < 9; i+) for (int j = 0; j < i; j+)if (endsi < endsj &&

21、endsi != 0)count2+; / 統計目標狀態的逆序數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