人工智能十五数码实验报告.doc

人工智能十五数码实验报告

目录
1 实验概述 2
2 十五数码问题分析 2
2.1十五数码问题简介 2
2.2可行性分析 3
3问题的求解策略 3
3.1算法分析 3
3.2 A*算法设计 4
4 实验总结 5
4.1 实验可视化界面 5
4.2个人体会 6
4.3 详细代码： 7

1 实验概述
十五数码问题来源于美国的科学魔术大师萨姆.洛伊德（Sam I.oyd）在1978年推出的著名的“14-15”智力玩具。 这个游戏曾经风靡欧美大陆" 。洛伊德的发明其实只是将重排九宫（即八数码问题）中的3阶方阵扩大到4 阶方阵罢了。 由于这个细微的变化，十五数码问题的规模远远大于八数码问题，八数码问题的规模较小，总的状态数为9！（=362880）个，而十五数码问题的状态,数为16！（）个。 故十五数码问题更能评价一个算法的“智能”水平。
2 十五数码问题分析
2.1十五数码问题简介
15数码问题又叫移棋盘问题，是人工智能中的一个经典问题。所谓的15数码问题：就是在一个4×4的16宫格棋盘上，摆放有15个将牌，每一个将牌都刻有1～15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种求解的问题是：给定一种初始的将牌布局或结构(称初始状态)和一个目标布局(称目标状态)，问如何移动数码，实现从初始状态到目标状态的转变，如下图所示 。问题的实质就是寻找一个合法的动作序列

2.2可行性分析
十五数码问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义如下：把四行数展开排成一行,并且丢弃数字 0 不计入其中,ηi是第 i 个数之前比该数小的数字的个数,则 η=Σηi 是该状态的逆序数,例如：对于初始状态：5、1、2、4、9、6、3、8、13、15、10、11、14、7、12.其η=0+0+1+2+4+4+2+6+8+9+8+9+11+6+11=81；对于目标状态：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15，其η=0+1+2+3+4+5+6+7+8+9+10+11+12+13+14=105。初始状态和目标状态的奇偶性相同，故存在解路径。
3问题的求解策略
3.1算法分析
十五数码问题的解空间树属排列树，用于排列树搜索的方法主要有两大类：
一类是盲目搜索，如深度优先搜索DFS 和广度优先搜索BFS；另一类是启发式搜索，如 A* 算法。
对于十五数码问题，深度优先搜索的状态空间搜索树的深度可能为无限深， 或者可能至少要比某个可接受的解答序列的已知深度上限还要深。 应用此策略很可能得不到解。 宽度优先搜索的优势在于当问题有解时， 一定能找到解， 且能找到最优解。但其搜索时需要保存所有的待扩展结点，这样很容易扩展那些没有用的结点，造成状态的指数增长，甚至“组合爆炸”。这对宽度优先搜索很不利。这两种搜索方法的共同缺点是结点排序杂乱无章，往往在搜索了大量无关结点后才能得到目的结点，只适合于复杂度较低的问题的求解。
启发式搜索利用特定问题自身所携带的启发信息在一定程度上避免了盲目搜索的不足，适合于解决十五数码问题。 其核心思想是引入一个启发式函数（或称为评估函数）利用评估函数为生成的结点估值%并按估值的大小对结点进行排序，优先搜索估值小的结点。 该评估函数根据问题的启发信息建立，评估了解决问题所需的最小费用，其基本形式是f(n) = g(n)+h(n)。 其中g(n)：从初始状态 s 到中间状态n 的最佳代价g*(n)的估值，h（n）：从中间状态 n 到目标状态 t 的最佳代价h*（n）的估值，利用评估函数来进行的图搜索算法称为 A算法，若还有h（n）<= h*（n）则称为A*算法。
在八数码问题中，通常g（n）是搜索树中当前结点n的深度，是从根结点到当前结点n的最短路径长度；h（n）的取值则有多种，如错位将牌数、曼哈顿距离。这里主要是h（n）体现了启发信息，h（n）设计的好坏体现了算法的“智能”水平。本课设借鉴这些算法h（n）采用曼哈顿距离。
3.2 A*算法设计
（1）根据初始排列生成初始结点s，并判断问题的可解性。若可解则转（2）否则退出。
（2）初始化open，closed表，并将初始节点加入open表。
（3）从open表中取出第一个节点。
（4）若是目标节点则成功退出。
（5）把该节点从open表删除，并添加到closed表中。
（6）对该节点进行扩展，其生成节点mi分成三种情况，mj，mk，ml。mj：新生成的节点既不在open表中也不在closed表中，直接把生成的节点添加到open表即可。Mk：新生成的节点出现在open表中且新生成节点的f（n）小于open表中该节点的f（n），则更改open表中的f（n）的值。Ml：新生成的节点在closed表中并且新生成节点的f（n）小于closed表中对应节点的f（n）的值，则把该节点从open表中删除，添加到open表中并写该其f值为新生成节点的f值。
（7）对open表中的节点按f值从小到大的顺序进行排列。
（8）转到（3）。

4 实验总结
4.1 实验可视化界面

4.2个人体会
初学人工智能时，最先联想到的便是机器人，一直感觉机器人是非常智能且神秘的，这也令人工智能在我的思想里笼罩了一层非同寻常的面纱，非常迫切的想要了解他的内涵。经过三十多个学时的学习，我对人工智能已经有了初步的了解，也深深的被它吸引，尤其通过本次课程设计，对人工智能的学习兴趣更加浓厚了！
15数码问题是人工智能的一个经典的问题。本文中通过设计一个基于A*算法的状态空间搜索程序，对于给定的初始状态，采用f(n)=h(n)+g(n)表示以当前节点及其目标节点相应位置不相同元素的个数及搜索深度之和作为启发函数的度量，并用面相对象的编程语言java来实现该问题。在程序的设计及实现过程中，遇到了很多的问题。首先由于初学人工智能，理解上有一定的困难，对A*算法的深入学习是一个曲折的过程。其次，在程序真正的设计及实现过程中，的确需要花费大量的精力来思考，反复试验。所设计的程序能够运行，但缺陷还是非常之大的，如其中重排OPEN表时，没有进行真正意义上的重新排列，只是选出代价最小的放在最先的位置，这实际上对程序的运行效率有很大的影响。 同时通过输入大量的初始状态和目标状态发现，在一般情况下都可以找到最优的动作序列。但对某些稍微复杂的初始状态虽能得到正确解却不能完全得到最短的搜索路径，对于某些极其复杂的状态，甚至得不到解。这是有待进一步学习并改进的地方。 但本程序还是有些值得肯定之处。界面设计比较友好，容易操作。而且在程序开始时，就判断目标状态是否可达，这样可节约大量的时间。虽然很多地方设计的不尽如意，但这是针对十五数码这个具体问题的一点优化。
4.3 详细代码：
public class Main {
public static final int N = 4;
static int num[][] = {{5,1,2,4},{9,6,3,8},{13,15,10,11},{14,0,7,12}};
static int standard[][] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};
public static void main(String[] args){
int totalnum = 0;
Node node = new Node(num);
if(!Data.isDataOk(num, standard)){
System.out.println("此种方案无解");
System.exit(-1);
}
System.out.println("数据的变化情况如下所示：\n");
Node resultnode = FifteenNum.moveManHa(node);
for(int i=1; i<=resultnode.getPnodes().size(); i++){
Interface f = new Interface();
f.P1(resultnode.getPnodes().get(i-1).data,i-1);
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
resultnode.getPnodes().get(i-1).print();
System.out.println();
System.out.println();
System.out.println("第"+i+"步");
totalnum = i;
}
Interface f = new Interface();
f.P1(resultnode.data,totalnum);
resultnode.print();
}
}
import java.util.ArrayList;
import java.util.List;
public class Node {
public static final int N = 4;
private int f ;
private int h ;
private int w ;
List<Node> pnodes = new ArrayList<Node>();
FifteenNum.Direction last_Dirction ;
int data[][] = new int[N][N];
public Node(int data[][]){
this.h = 0;
this.w = 0;
this.f = 0;
this.last_Dirction = null;
Data.arrayCopy(this.data, data);
//pnodes.add(this);
}
public List<Node> getPnodes() {
return pnodes;
}
public FifteenNum.Direction getLast_Dirction() {
return last_Dirction;
}
public void setLast_Dirction(FifteenNum.Direction lastDirction) {
last_Dirction = lastDirction;
}
public int getF() {
return f;
}
public void setF(int f) {
this.f = f;
}
public int getH() {
return h;
}
public void setH(int h) {
this.h = h;
}
public int getW() {
return w;
}
public void setW(int w) {
this.w = w;
}
public void print(){
System.out.println();
for(int i=0; i<8; i++){
System.out.print("* ");
}
System.out.println();
for(int i=0; i<N; i++){
System.out.print("* ");
for(int j = 0; j<N; j++){
if(data[i][j] == 0){
System.out.print(" ");
}else if(data[i][j] < 10){
System.out.print(data[i][j]+" ");
}
else{
System.out.print(data[i][j]+" ");
}
}
System.out.println("*");
}
for(int i=0; i<8; i++){
System.out.print("* ");
}

System.out.println();
}
public boolean isequal( Node node){
boolean flag = true;
for(int i=0; i<N; i++){
for(int j = 0; j<N; j++){
if(data[i][j] != node.data[i][j]){
flag = false;
break;
}
}
if(!flag) break;
}
return flag;
}
public Node getSameStateFrom(List<Node> list){
for(int i=0; i<list.size(); i++){
if(this.isequal(list.get(i))) return list.get(i);
}
return null;
}
}
import java.util.Scanner;
public class Data {
public static int n = Main.N;
static Scanner sc = new Scanner(System.in);
public static void inputNum(int num[][]){
int k=0;
for(int i=0; i<n; i++){
for(int j = 0; j<n; j++){
num[i][j] = sc.nextInt();
}
}
}
public static void arrayCopy(int a[][], int b[][]){
for(int i=0; i<n; i++){
for(int j = 0; j<n; j++){
a[i][j] = b[i][j];
}
}
}
public static int inverseNum(int data[][]){
int index = 0;
int num = 0;
int tempnum = 0;
int temp[] = new int[n*n-1];
for(int i=0; i<n; i++){
for(int j = 0; j<n; j++){
if(data[i][j] != 0){
temp[index] = data[i][j];
//System.out.print(temp[index]+" ");
index++;
}

}
}
System.out.println();
for(int i=0; i<n*n-1; i++){
tempnum = 0;
for(int j=0; j<i; j++){
if(temp[j]<temp[i]){
tempnum++;
}
}
num += tempnum;
}
return num;
}
public static int WrongLocationNum(int temp[][]){
int count = 0;
for(int i=0; i<n; i++){
for(int j = 0; j<n; j++){
if(temp[i][j] != 0){
if(temp[i][j] != Main.standard[i][j]){
count++;
}
}
}
}
return count;
}
public static int manHa(int temp[][]){
int d = 0;
boolean flag = false;
for(int x1=0; x1<n; x1++){
for(int y1=0; y1<n; y1++){
if(temp[x1][y1] != 0){
flag = false;
for(int x2=0; x2<n; x2++){
for(int y2=0; y2<n; y2++){

if(temp[x1][y1] == Main.standard[x2][y2]){
d += Math.abs(x1 - x2) + Math.abs (y1 - y2);
flag = true;
}
if(flag ) break;
}
if(flag ) break;
}
}
}
}
return d;
}
public static boolean sameOdevity(int m, int n){
if(m%2 == n%2) return true;
else return false;
}
public static boolean isDataOk(int a[][], int b[][]){
return sameOdevity(inverseNum(a), inverseNum(b));
}
}
import java.util.ArrayList;
import java.util.List;
public class FifteenNum {
public static int openNum = 0;
public static int closedNum = 0;
public enum Direction {UP,RIGHT,DOWN,LEFT};
public static final int n = Main.N;
static List<Node> open = new ArrayList<Node>();
static List<Node> closed = new ArrayList<Node>();
public static boolean changeTo(Direction direction,int i, int j, int data_temp[][]){
int temp;
boolean flag = true;
switch(direction){
case UP: {
if(i>=1){
temp = data_temp[i][j];
data_temp[i][j] = data_temp[i-1][j];
data_temp[i-1][j] = temp;
}else{
flag = false;
}
break;
}
case RIGHT: {
if(j<=2){
temp = data_temp[i][j];
data_temp[i][j] = data_temp[i][j+1];
data_temp[i][j+1] = temp;
}else{
flag = false;
}
break;
}
case DOWN: {
if(i<=2){
temp = data_temp[i][j];
data_temp[i][j] = data_temp[i+1][j];
data_temp[i+1][j] = temp;
}else{
flag = false;
}
break;
}
case LEFT: {
if(j>=1){
temp = data_temp[i][j];
data_temp[i][j] = data_temp[i][j-1];
data_temp[i][j-1] = temp;
}else{
flag = false;
}
break;
}
}
return flag;
}
public static boolean oppositeDirection(Direction d1, Direction d2){
if(d1==Direction.UP && d2 == Direction.DOWN || d1==Direction.DOWN && d2 == Direction.UP){
return true;
}else if(d1==Direction.RIGHT && d2 == Direction.LEFT || d1==Direction.LEFT && d2 == Direction.RIGHT){
return true;
}
return false;
}
public static Node moveManHa(Node node1){
Direction direction[] ={ Direction.UP, Direction.RIGHT, Direction.DOWN, Direction.LEFT};
int i = 0;
int j = 0;
int wrongNum;
boolean isOver = false;
//设定初始节点的参数
node1.setH(0);
node1.setW(Data.manHa(node1.data)); //曼哈顿
node1.setF(node1.getW()+node1.getH());
Node node = null;
open.add(node1);
node = open.remove(0);
int a =0;
while(node.getW() != 0){
//定位要扩展节点的空格所在的位置
for(int x=0; x<n; x++){
for(int y = 0; y<n; y++){
if(node.data[x][y] == 0){
i = x;
j = y;
//System.out.println("空格的坐标="+i+"j="+j);
break;
}
}
}

int temp[][] = new int[n][n];

//对刚才从open表中取出的节点试探性的进行四个方向的扩展
for(int dir_index = 0; dir_index < 4; dir_index++){
if(FifteenNum.oppositeDirection(node.getLast_Dirction(), direction[dir_index])){
continue;
}
Data.arrayCopy(temp, node.data);
if(FifteenNum.changeTo(direction[dir_index], i, j,temp)){
wrongNum = Data.manHa(temp); //曼哈顿距离
Node node_temp = new Node(temp); //由父节点生成新的节点
node_temp.setH(node.getH()+1);
node_temp.setW(wrongNum);
node_temp.setF(node_temp.getH()+node_temp.getW());
node_temp.setLast_Dirction(direction[dir_index]);//记录该节点的的移动方向，以便其孩子节点不再及该节点移动的方向相反
/**
* 把新生成节点的祖先节点放入到新生成节点里
*/
for(int k=0; k<node.getPnodes().size(); k++){
node_temp.getPnodes().add(node.getPnodes().get(k));
}
node_temp.getPnodes().add(node);
/**
*
* 判断当前节点n生成的节点mi属于mj、mk、ml的哪一种 判断顺序为 ：mk->ml->mj
*/
Node node_ml = null ;
Node node_mk = null;//open表中或closed表中 （及新生成的节点状态一样 ）的节点
if((node_mk = node_temp.getSameStateFrom(open)) != null){
if(node_temp.getH() > node_mk.getH()){

open.remove(node_temp);
open.add(node_temp);
}
}else if((node_ml = node_temp.getSameStateFrom( closed)) != null){
if(node_temp.getH() > node_ml.getH()){
closed.remove(node_ml);
open.add(node_temp);
openNum++;
}
}else{
open.add(node_temp);
openNum++;
}
if(Data.manHa(node_temp.data) == 0){ //曼哈顿
isOver = true;
node = node_temp;
break;
}
}else{
//不可达的方向，错位将牌数取为10
wrongNum = 10;
}
}//for结束
if(isOver) {
break; //如果已经是目标状态退出程序
}
closed.add(node);
closedNum++;
sort(open);
node = open.remove(0);
openNum--;
//把open表中的第一个节点从open表中删除，添加到closed表中

} //while结束
int produce = closedNum + openNum;
//System.out.println("扩展节点数closednum="+closedNum+"生成节点数produce="+produce);
return node;
}
public static void sort(List<Node> list){
for(int i=0; i<list.size(); i++ ){
int k = i;
for(int j=i+1; j<list.size(); j++){
if(list.get(k).getF()>list.get(j).getF()){
k = j;
}
}
if(k != i){
Node node1;
Node node2;
node1 = list.get(i);
node2 = list.get(k);
list.set(i, node2);
list.set(k, node1);

}
}
}
}
import java.awt.BorderLayout;
import java.awt.Button;
import java.awt.Color;
import java.awt.Font;
import java.awt.GridLayout;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
public class Interface extends JFrame{
JPanel p1 = new JPanel();
JPanel p2 = new JPanel();
public Interface(){
this.setTitle("15数码问题");
this.setVisible(true);
this.setBounds(100, 100, 150, 150);
this.setLayout(new BorderLayout());
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
public void P1(int data[][], int j){
p1.setBackground(Color.blue);
p1.setVisible(true);
p1.setLayout(new GridLayout(4,4));
for(int i=0; i<16; i++){
Button bi = new Button(""+data[i/4][i%4]);
if(data[i/4][i%4] == 0){
bi.setBackground(Color.pink);
}
Font f=new Font("华文行楷",Font.BOLD,15);//根据指定字体名称、样式和磅值大小，创建一个新 Font。
bi.setFont(f);
p1.add(bi);
}
add(p1,BorderLayout.CENTER);
P2(j);
}
/*
* 用来显示走步
*/
public void P2(int i){
p2.setBackground(Color.yellow);
p2.setVisible(true);
add(p2,BorderLayout.SOUTH);
JLabel l = new JLabel("第"+i+"步");
p2.add(l);

}
}

28 / 28