人工智能课内实验报告二 计算机15班 西安交通大学

人工智能实验-重排九宫问题

人工智能课内实验报告(一)

——A*算法实现重排九宫问题

班级：计算机15班

姓名：高君宇 学号：2110505112

报告完成日期：2013年11月23日- 1 -

1

人工智能实验-重排九宫问题

一.实验目的

熟悉启发式搜索的思想，加深对各种图搜索策略概念的理解； 二 .实验内容

在一个3×3的方格棋盘上放置8个标有1、2、3、4、5、6、7、8数字的将牌，留下一个空格（用0表示）。

规定：与空格相邻的将牌可以移入空格。

要求：寻找一条从初始状态到目标状态的将牌移动路线。

三．实验原理和算法描述

搜索的一般描述：

1. 把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G； 2. 检查OPEN表是否为空，若为空则问题无解，退出；

3. 把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n； 4. 考察节点n是否为目标节点。若是，则求得了问题的解，退出； 5. 扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中； 6. 针对M中子节点的不同情况，分别进行如下处理：

1. 对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）

2. 对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中）

3. 对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中）

7. 按某种搜索策略对OPEN表中的节点进行排序； 8. 转第2步。

A*搜索：

如果一般搜索过程满足如下限制，则它就称为A*算法：

(1) 把OPEN表中的节点按估价函数：

f(x)=g(x)+h(x)

f(x)的值从小至大进行排序（一般搜索过程的第7步）。

(2) g(x)是从初始节点S0到节点x的路径的代价，g(x)是对g*(x)的估计，g(x)>0。 (3) h(x)是h*(x)的下界，即对所有的x均有：h(x)≤h*(x)。

其中，g*(x)是从初始节点S0到节点x的最小代价；h*(x)是从节点x到目标节点的最小代价。 算法描述：

1. 把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；

- 2 -

2

人工智能实验-重排九宫问题

检查OPEN表是否为空，若为空则问题无解，退出；

把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n； 考察节点n是否为目标节点。若是，则求得了问题的解，退出； 扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中； 6. 针对M中子节点的不同情况，分别进行如下处理：

1. 对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）

2. 对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中,对g(x)进行更新）

3. 对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中, 对节点n子节点的子节点更新g(x) ）

7. 对OPEN表中的节点按估价函数进行排序； 8. 转第2步。

注：这里h（x）的值取当前状态和目标状态相应九宫格上位置相同而数字不同的个数。 四．实验结果

2. 3. 4. 5.

- 3 - 3

人工智能实验-重排九宫问题

- 4 - 4

人工智能实验-重排九宫问题

七．实验体会

广度优先搜索算法比较可靠，只要问题有解，这种算法总可以得到解，而且得到的是最优解。但同时也有很大的缺点，例如它的盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。

相比之下，使用到代价函数的A*搜索算法，的效率较高。 八．源代码 AStar类：

package jiugong;

import javax.swing.table.DefaultTableModel; import java.util.LinkedList;

public class AStar {

private static LinkedList open=new LinkedList(); private static LinkedList closed=new LinkedList(); private static LinkedList path=new LinkedList(); private static Node quicknode=null; private static class Node{

int value; int diff=0; int depth=-1; int data[][]; int row; int clumn; Node parent;

Node(int data[][],Node parent,int row,int clumn,int depth,int diff){

this.data=data; this.parent=parent;

- 5 -

5

private static int[][]d=new int[3][3];

人工智能实验-重排九宫问题

}

}

this.row=row; this.clumn=clumn; this.depth=depth; this.diff=diff; this.value=depth+diff;

private static int DiffValue(int[][] src,int[][] dest){ int diff=0;

for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(src[i][j]!=dest[i][j]){ diff++;

}

}

}

return diff; }

private static void AStarMoveExtend(Node current){ int depth=current.depth+1; int row=current.row; int clumn=current.clumn; Node child; if(clumn!=0){ if(current.parent.row!=row||current.parent.clumn!=clumn-1){

int data[][]=new int[3][3]; data=Method.copy(current.data); int diff=0;

if(data[row][clumn]==d[row][clumn]){ if(data[row][clumn-1]==d[row][clumn-1]){ diff=current.diff+2; }else{

diff=current.diff+1;

} }else{

if(data[row][clumn]==d[row][clumn-1]){ if(data[row][clumn-1]==d[row][clumn]){ diff=current.diff-2; }else{

diff=current.diff-1;

}

}else{

if(data[row][clumn-1]==d[row][clumn]){

- 6 -

6

人工智能实验-重排九宫问题

diff=current.diff-1;

}else{

if(data[row][clumn-1]==d[row][clumn-1]){ diff=current.diff+1; }else{

diff=current.diff; }

}

} }

int temp=data[row][clumn];

data[row][clumn]=data[row][clumn-1]; data[row][clumn-1]=temp;

child=new Node(data,current,row,clumn-1,depth,diff); if(diff==-1||diff==-2){ quicknode=child; }else{

open.add(child); } }

}

if(row!=0){ if(current.parent.row!=row-1||current.parent.clumn!=clumn){

int data[][]=new int[3][3]; data=Method.copy(current.data); int diff=0;

if(data[row][clumn]==d[row][clumn]){ if(data[row-1][clumn]==d[row-1][clumn]){ diff=current.diff+2; }else{

diff=current.diff+1;

} }else{

if(data[row][clumn]==d[row-1][clumn]){ if(data[row-1][clumn]==d[row][clumn]){ diff=current.diff-2; }else{

diff=current.diff-1;

}

}else{

if(data[row-1][clumn]==d[row][clumn]){ diff=current.diff-1;

}else{

if(data[row-1][clumn]==d[row-1][clumn]){

- 7 -

7

人工智能实验-重排九宫问题

diff=current.diff+1; diff=current.diff;

}else{

}

}

} }

int temp=data[row][clumn];

data[row][clumn]=data[row-1][clumn]; data[row-1][clumn]=temp;

child=new Node(data,current,row-1,clumn,depth,diff); if(diff==-1||diff==-2){ quicknode=child; }else{

open.add(child); } }

}

if(clumn!=2){ if(current.parent.row!=row||current.parent.clumn!=clumn+1){

int data[][]=new int[3][3]; data=Method.copy(current.data); int diff=0;

if(data[row][clumn]==d[row][clumn]){ if(data[row][clumn+1]==d[row][clumn+1]){ diff=current.diff+2; }else{

diff=current.diff+1;

} }else{

if(data[row][clumn]==d[row][clumn+1]){ if(data[row][clumn+1]==d[row][clumn]){ diff=current.diff-2; }else{

diff=current.diff-1;

}

}else{

if(data[row][clumn+1]==d[row][clumn]){ diff=current.diff-1;

}else{

if(data[row][clumn+1]==d[row][clumn+1]){ diff=current.diff+1; }else{

diff=current.diff;

}

- 8 -

8

人工智能实验-重排九宫问题

}

} }

int temp=data[row][clumn];

data[row][clumn]=data[row][clumn+1]; data[row][clumn+1]=temp;

child=new Node(data,current,row,clumn+1,depth,diff); if(diff==-1||diff==-2){ quicknode=child; }else{

open.add(child); } }

}

if(row!=2){ if(current.parent.row!=row+1||current.parent.clumn!=clumn){

int data[][]=new int[3][3]; data=Method.copy(current.data); int diff=0;

if(data[row][clumn]==d[row][clumn]){ if(data[row+1][clumn]==d[row+1][clumn]){ diff=current.diff+2; }else{

diff=current.diff+1;

} }else{

if(data[row][clumn]==d[row+1][clumn]){ if(data[row+1][clumn]==d[row][clumn]){ diff=current.diff-2; }else{

diff=current.diff-1; }

}else{

if(data[row+1][clumn]==d[row][clumn]){ diff=current.diff-1;

}else{

if(data[row+1][clumn]==d[row+1][clumn]){ diff=current.diff+1; }else{ diff=current.diff; }

}

} }

int temp=data[row][clumn];

- 9 -

9

人工智能实验-重排九宫问题

data[row][clumn]=data[row+1][clumn]; data[row+1][clumn]=temp;

child=new Node(data,current,row+1,clumn,depth,diff); if(diff==-1||diff==-2){ quicknode=child; }else{

open.add(child); } } }

public static void A_Star(MainFrame frame,DefaultTableModel src,DefaultTableModel

open=new LinkedList(); dest){

closed=new LinkedList(); path=new LinkedList();

int s[][];

int location[]=new int[2]; s=Method.toTwoArray(src); d=Method.toTwoArray(dest); location=Method.Location(s, 0);

private static void GetPath(Node node,Node supernode){ }

while(node.parent!=null){ }

path.addFirst(node); node=node.parent;

private static void SelectMin(){ }

int size=open.size(); int k=0;

for(int i=1;i

if(k!=0){ }

Node node=(Node)open.get(0); open.set(0, (Node)open.get(k)); open.set(k, node); if(((Node)open.get(k)).value>((Node)open.get(i)).value){

}

k=i;

}

if(Method.isSolutionExist(Method.toArray(src), Method.toArray(dest),s,d)){

- 10 -

10

人工智能实验-重排九宫问题

frame.jTextArea1.setText(\有解\\n\); Node current;

Node supernode=new Node(new int[3][3],null,-1,-1,-1,-1);

Node root=new Node(s,supernode,location[0],location[1],0,DiffValue(s,d));

open.add(root); long time_old=System.nanoTime(); while(open.size()!=0||quicknode!=null){ if(quicknode!=null){ current=quicknode; closed.add(quicknode); quicknode=null; }else{

SelectMin();

current=(Node)open.removeFirst();

closed.add(current); }

if(Method.equals(current.data, d)){ GetPath(current,supernode); break;

}else{

AStarMoveExtend(current); } }

long time_new=System.nanoTime(); long time=time_new-time_old; int length=path.size(); int h2=0;

frame.jTextArea1.append(\最优解：\\n\); while(path.size()!=0){

Node node=(Node)path.removeFirst();

frame.jTextArea1.append(\+h2+\估价值：\+node.value+\); Method.print(frame, node.data); frame.jTextArea1.append(\); h2++; }

frame.jTextArea1.append(\搜索总长度：\+(closed.size()-1)); frame.jTextArea1.append(\最短路径长：\+(length-1)); frame.jTextArea1.append(\搜索时间：\+time/1000+\); }else{

frame.jTextArea1.setText(\无解\); } }

}

- 11 -

11

人工智能实验-重排九宫问题

MainFrame类：

package jiugong;

import java.awt.*;

import javax.swing.*;

import javax.swing.table.DefaultTableModel; import java.awt.event.ActionListener; import java.awt.event.ActionEvent; import java.util.*;

public class MainFrame extends JFrame{ Object jiugong1[][]={{2,8,1},{3,0,4},{7,5,6}}; Object jiugong2[][]={{1,2,3},{8,0,4},{7,6,5}}; Object obj[]={\ JPanel contentPane;

JPanel jPanel1=new JPanel(); JPanel jPanel2=new JPanel(); JTable jTable1=new JTable(); JTable jTable2=new JTable(); JButton jButton1=new JButton(); JButton jButton4=new JButton(); JButton jButton5=new JButton(); JLabel jLabel1=new JLabel(); JLabel jLabel2=new JLabel(); JScrollPane jScrollPane1=new JScrollPane(); JTextArea jTextArea1=new JTextArea(); DefaultTableModel src=new DefaultTableModel(jiugong1,obj); DefaultTableModel dest=new DefaultTableModel(jiugong2,obj); public MainFrame(){ try{ setDefaultCloseOperation(EXIT_ON_CLOSE); jbInit(); }catch(Exception exception){ exception.printStackTrace(); } } private void jbInit() throws Exception{ contentPane=(JPanel)getContentPane(); contentPane.setLayout(null);

- 12 -

12

人工智能实验-重排九宫问题

this.getContentPane().setBackground(Color.pink); setSize(new Dimension(400,400));

contentPane.setBackground(Color.pink); jLabel1.setText(\初始状态：\

jLabel1.setFont(new java.awt.Font(\宋体\jLabel1.setBounds(20, 10, 80, 25);

jLabel2.setFont(new java.awt.Font(\宋体\jLabel2.setText(\目标状态：\jLabel2.setBounds(285, 10, 80, 25); jButton1.setText(\搜索\

jButton1.setBounds(120,40,155,25);

jButton1.setFont(new java.awt.Font(\宋体\jButton1.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent e){ src=(DefaultTableModel)jTable1.getModel(); dest=(DefaultTableModel)jTable2.getModel(); AStar.A_Star(MainFrame.this,src,dest); } });

jButton4.setText(\随机\

jButton4.setBounds(90, 10, 80, 25);

jButton4.setFont(new java.awt.Font(\宋体\jButton4.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent e){ Random random=new Random(); int array[]={-1,-1,-1,-1,-1,-1,-1,-1,-1}; int a = 0; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ a=random.nextInt(9); array[i*3+j]=a; src.setValueAt(a, i, j); } } } });

jButton5.setText(\随机\

jButton5.setBounds(200, 10, 80, 25);

jButton5.setFont(new java.awt.Font(\宋体\jButton5.addActionListener(new ActionListener(){ public void actionPerformed(ActionEvent e){ Random random=new Random(); int array[]={-1,-1,-1,-1,-1,-1,-1,-1,-1};

- 13 -

13

人工智能实验-重排九宫问题

int a = 0; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ // while(Method.IsAppear(array,(a=random.nextInt(9)),i*3+j)); a=random.nextInt(9); array[i*3+j]=a; dest.setValueAt(a, i, j); } } } }); jPanel1.setBackground(Color.pink); jPanel1.setBounds(20, 35, 90, 95); jPanel2.setBackground(Color.pink); jPanel2.setBounds(285, 35, 90, 95); jTextArea1.setFont(new java.awt.Font(\宋体\ jScrollPane1.setBounds(20,140,355,220); jTable1=new JTable(src); jTable1.setFont(new java.awt.Font(\宋体\ jTable1.setAutoResizeMode(JTable.AUTO_RESIZE_OFF); jTable2=new JTable(dest); jTable2.setFont(new java.awt.Font(\宋体\ jTable2.setAutoResizeMode(JTable.AUTO_RESIZE_OFF); for(int i=0;i<3;i++){ jTable1.getColumnModel().getColumn(i).setPreferredWidth(30); jTable2.getColumnModel().getColumn(i).setPreferredWidth(30); } jTable1.setRowHeight(30); jPanel1.add(jTable1); jTable2.setRowHeight(30); jPanel2.add(jTable2); jScrollPane1.getViewport().add(jTextArea1); contentPane.add(jPanel1); contentPane.add(jPanel2); contentPane.add(jButton1); contentPane.add(jButton4); contentPane.add(jButton5); contentPane.add(jLabel1); contentPane.add(jLabel2); contentPane.add(jScrollPane1); }

/*public static void main(String[] args) {

- 14 -

14

人工智能实验-重排九宫问题

MainFrame mf = new MainFrame(); mf.setVisible(true); }*/ }

Method类： package jiugong;

import java.util.Vector;

import javax.swing.table.DefaultTableModel;

public class Method { public static boolean Parity(int a[]){ boolean parity=true; for(int i=0;ia[j]){ k=j; } } if(k!=i){ int temp; temp=a[i]; a[i]=a[k]; a[k]=temp; parity=!parity; } } return parity; } public static boolean isSolutionExist(int src[],int dest[],int s[][],int d[][]){ int row1=0,row2=0,clumn1=0,clumn2=0; boolean flag1,flag2; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(s[i][j]==0){ row1=i; clumn1=j; }

- 15 -

15

人工智能实验-重排九宫问题

if(d[i][j]==0){ row2=i; clumn2=j; } } }

if((row1-row2+clumn1-clumn2)%2==0){ flag1=true; }else{

flag1=false; }

if(Parity(src)==Parity(dest)){ flag2=true; }else{

flag2=false; }

if(flag1==flag2){ return true; }else{

return false; }

}

public static int[] toArray(DefaultTableModel table){ Vector vct=table.getDataVector(); Vector vct1=(Vector)vct.get(0); Vector vct2=(Vector)vct.get(1); Vector vct3=(Vector)vct.get(2); int a[]=new int[9];

a[0]=new Integer(vct1.get(0).toString()); a[1]=new Integer(vct1.get(1).toString()); a[2]=new Integer(vct1.get(2).toString()); a[3]=new Integer(vct2.get(2).toString()); a[4]=new Integer(vct3.get(2).toString()); a[5]=new Integer(vct3.get(1).toString()); a[6]=new Integer(vct3.get(0).toString()); a[7]=new Integer(vct2.get(0).toString()); a[8]=new Integer(vct2.get(1).toString()); return a; }

public static int[][] toTwoArray(DefaultTableModel table){ int a[][]=new int[3][3];

Vector vct=table.getDataVector();

- 16 -

16

人工智能实验-重排九宫问题

for(int i=0;i<3;i++){ a[0][i]=new Integer(((Vector)vct.get(0)).get(i).toString()); a[1][i]=new Integer(((Vector)vct.get(1)).get(i).toString()); a[2][i]=new Integer(((Vector)vct.get(2)).get(i).toString()); } return a; } public static int[] Location(int a[][],int value){ int location[]=new int[2]; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(a[i][j]==value){ location[0]=i; location[1]=j; return location; } } } return location; } public static int[][] copy(int a[][]){ int array[][]=new int[3][3]; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ array[i][j]=a[i][j]; } } return array; } public static void print(MainFrame frame,int a[][]){ String str=\ for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ str=str+a[i][j]+\ \ } str=str+\ } frame.jTextArea1.append(str); } public static void print(MainFrame frame,DefaultTableModel table){

- 17 -

17

人工智能实验-重排九宫问题

Vector vct=table.getDataVector(); String str=\

for(int i=0;i<3;i++){

Vector vct1=(Vector)vct.get(i); for(int j=0;j<3;j++){ str=str+vct1.get(j).toString()+\ \ }

str=str+\ }

frame.jTextArea1.append(str);

}

public static boolean equals(int a[][],int b[][]){ for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(a[i][j]!=b[i][j]){ return false; } } }

return true; }

public static boolean IsAppear(int array[],int a,int n){ for(int i=0;i

return false; }

}

- 18 - 18

本文来源：https://www.bwwdw.com/article/caua.html