华 中 师 范 大 学 计 算 机 学 院

实 验 报 告 书

实验题目 ： 八数码问题求解

课程名称 ： 人工智能

主讲教师 ： **

班 级 ：

试验时间 ：

1.问题描述：

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

2.初始状态

1 0 3

7 2 4

6 8 5

3.目标状态

1 2 3,

8 0 4,

7 6 5

4.搜索策略

启发式搜索技术

（1） 原理：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

（2） 估价函数

计算一个节点的估价函数，可以分成两个部分：

1、 已经付出的代价（起始节点到当前节点）；

2、 将要付出的代价（当前节点到目标节点）。

节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即= +。

是从初始节点到达当前节点n的实际代价；

是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。

所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。

本实验中我们使用函数，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然比更接近于，因为不仅考虑了错位因素，还考虑了错位的距离。

5.算法

Begin：

读入初始状态和目标状态，并计算初始状态评价函数值f；

根据初始状态和目标状态，判断问题是否可解；

If(问题可解)

把初始状态假如open表中；

While（未找到解&&状态表非空）

①在open表中找到评价值最小的节点，作为当前结点；

②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③；

③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；

④对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；

⑤把当前结点从open表中移除；

End while

End if

输出结果；

End

6.源代码

#include＜stdio.h＞

#include＜malloc.h＞

#include＜stdlib.h＞

#define Overflow 1

#define N 3

int goal[N][N]={1,2,3,8,0,4,7,6,5};

int zero[2],NodeQTY=0;

int *z=zero;//记录0的位置，zero[0]:r行；zero[1]:c列

typedef int Piece;

struct Chessboard{//棋盘信息

Piece pos[N][N];//记录每个数码a的位置r行c列

int d,f,move;//d:深度；f:启发函数值 ；move:父节点移动到该节点的方式

};

struct LNode{

Chessboard board;

LNode *parent,*next;

bool flag;

};

typedef LNode* List;

int* Findzero(LNode* &Node)

{

int i,j,zr[2];

int *z=zr;

for(i=0;i＜N;i++){

for(j=0;j＜N;j++){

if(Node-＞board.pos[i][j]==0){

zr[0]=i+1;

zr[1]=j+1;

break;

}

}

}

return z;

}

int pick(LNode *Node)

{

int w=0,i,j,ii,jj;

for(i=0;i＜N;i++){

for(j=0;j＜N;j++){

if(Node-＞board.pos[i][j]!=goal[i][j]&&Node-＞board.pos[i][j]!=0){

for(ii=0;ii＜N;ii++)

for(jj=0;jj＜N;jj++)

if(Node-＞board.pos[i][j]==goal[ii][jj]){

w=w+abs(ii-i)+abs(jj-j);

break;

}

}

}

}

return w;

}

LNode* extend(LNode *Node,int depth,int zero[2],int moveflag,int Choose)

{

LNode* NewNode=new LNode;

for(int i=0;i＜N;i++){

for(int j=0;j＜N;j++){

NewNode-＞board.pos[i][j]=Node-＞board.pos[i][j];

}

}

switch(moveflag)

{

case 1: //向左移，不能出界：zero[1]＞=2

NewNode-＞board.pos[zero[0]-1][zero[1]-1]=NewNode-＞board.pos[zero[0]-1][zero[1]-2];

NewNode-＞board.pos[zero[0]-1][zero[1]-2]=0;

break;

case 2: //向右移，不能出界：zero[1]＜=2

NewNode-＞board.pos[zero[0]-1][zero[1]-1]=NewNode-＞board.pos[zero[0]-1][zero[1]];

NewNode-＞board.pos[zero[0]-1][zero[1]]=0;

break;

case 3: //向上移，不能出界：zero[0]＞=2

NewNode-＞board.pos[zero[0]-1][zero[1]-1]=NewNode-＞board.pos[zero[0]-2][zero[1]-1];

NewNode-＞board.pos[zero[0]-2][zero[1]-1]=0;

break;

case 4: //向下移，不能出界：zero[0]＜=2

NewNode-＞board.pos[zero[0]-1][zero[1]-1]=NewNode-＞board.pos[zero[0]][zero[1]-1];

NewNode-＞board.pos[zero[0]][zero[1]-1]=0;

break;

}

NewNode-＞board.d=depth+1;

switch(Choose){

case 1:NewNode-＞board.f=NewNode-＞board.d+pick(NewNode);break;

}

NewNode-＞board.move=moveflag;

NewNode-＞parent=Node;

NodeQTY++;

return NewNode;

}

void InitList(LNode* &Open,LNode* &Close)

{

Open=(List)malloc(sizeof(LNode));

Close=(List)malloc(sizeof(LNode));

if(!Open&&!Close)

exit(Overflow);

Open-＞next=NULL;

Close-＞next=NULL;

}

int ListInsert(List &L,LNode* NewNode)

{

List p=L;

while(p-＞next){

p=p-＞next;

}

NewNode-＞next=p-＞next;

p-＞next=NewNode;

return true;

}

LNode* Getminf(List &L)

{

List p=L,q=L-＞next,r=L,min;

min=q;//p,q寻找f最小值的指针，r指向表L中min前一个元素

if(!q)

return NULL;

while(q)

{

if(min-＞board.f＞q-＞board.f){

r=p;

min=q;

}

p=q;

q=q-＞next;

}

r-＞next=min-＞next;

min-＞next=NULL;

return min;

}

int main()

{

int i,j,choose;

List Open,Close;

LNode *Best,*current;

LNode *Start=new LNode;

printf("\t\t\t八 数 码 问 题 求 解\n");

printf("\n请输入初始状态：");

for(i=0;i＜N;i++){

for(j=0;j＜N;j++){

scanf("%d",&(Start-＞board.pos[i][j]));

}

}

printf("(注:The flag of movement--1:左移;2:右移;3:上移;4:下移)\n");

printf("初始棋盘状态：\n");

for(i=0;i＜N;i++){

for(j=0;j＜N;j++){

printf("|%d",Start-＞board.pos[i][j]);

}

printf("|\n");

}

InitList(Open,Close);

printf("A*算法:");

scanf("%d",&choose);

Start-＞board.d=0;

switch(choose){

case 1:Start-＞board.f=Start-＞board.d+pick(Start);break;

}

Start-＞board.move=0;

Start-＞parent=NULL;

Start-＞next=NULL;

Start-＞flag=1;

ListInsert(Open,Start);//将S加入到Open表中

while(Open-＞next){

Best=Getminf(Open);

ListInsert(Close,Best);

if(!(Best-＞board.f-Best-＞board.d)){

printf("$$$******有解！******$$$\n");

break;

}

z=Findzero(Best);

zero[0]=*(z+0);zero[1]=*(z+1);

if(zero[1]＞=N-1&&Best-＞board.move!=2)

ListInsert(Open,extend(Best,Best-＞board.d,zero,1,choose));

if(zero[1]＜=N-1&&Best-＞board.move!=1)

ListInsert(Open,extend(Best,Best-＞board.d,zero,2,choose));

if(zero[0]＞=N-1&&Best-＞board.move!=4)

ListInsert(Open,extend(Best,Best-＞board.d,zero,3,choose));

if(zero[0]＜=N-1&&Best-＞board.move!=3)

ListInsert(Open,extend(Best,Best-＞board.d,zero,4,choose));

}

printf("\t最佳路径如下所示：\n");

if(Open-＞next)

{

while(Best-＞parent){

Best-＞flag=1;

Best=Best-＞parent;

}

List p=Close-＞next,q=Close-＞next;

if(p==Start) q=p-＞next;

else exit(1);

int Step=0;

while(p&&q)//在Close表中依标记找到路径

{

if(q-＞flag==1&&q-＞parent==p){

printf("Step %d:0 move as the %d-flag of movement.\n",++Step,q-＞board.move);

for(i=0;i＜N;i++){

for(j=0;j＜N;j++){

printf("|%d",q-＞board.pos[i][j]);

}

printf("|\n");

}

p=q;//记住父节点

}

q=q-＞next;

}

printf("到达目标状态！\n");

}

else printf("该问题无法求解！\n");

}

7.实验心得

通过本次实验，我更加深入的了解了A*算法、启发函数以及搜索方法。启发式搜索有很多种方法，比如：局部择优搜索法，最好优先搜索法等等，其中也包括了A*算法，这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。A*是众多搜索方法中综合效果最好的。使用A*算法，也要懂得构建估价函数，不同的估计函数对实验结果影响很大。比如该实验，对于f(n)的考虑最简单的便是比较每个状态与目标状态相比错位的牌数。这个启发意味着如果其他条件相同，那么错位的牌数最少的状态可能最接近目标状态。然而这个启发没有使用从棋盘格局中可以得到的所有信息，因为它没有把牌必要的移动距离纳入考虑。一个“更好一点”的启发是对错位的牌必须要移动的距离求和，为了达到这个目的，每张牌必须要移动的每个方格算为一个距离单位。这两种启发都存在一种不足，就是没有认识到点到牌的难度。也就是说，如果两张牌是彼此相邻的，而且目标是要求互相颠倒它们的位置，那么要把它们放到适当的位置需要远不止两次的移动，因为各张牌必须相互绕来绕去。

 

第二篇：昆明理工大学人工智能八数码难题实验报告

昆明理工大学信息工程与自动化学院学生实验报告

（ 20XX — 20XX 学年 第 1 学期 ）

课程名称：人工智能 开课实验室：信自楼445

20XX年10月 25日

一、上机目的及内容

1.上机内容

用确定性推理算法求解教材65-66页介绍的八数码难题。

2.上机目的

（1）复习程序设计和数据结构课程的相关知识，实现课程间的平滑过渡；

（2）掌握并实现在小规模状态空间中进行图搜索的方法；

（3）理解并掌握图搜索的技术要点。

二、实验原理及基本技术路线图（方框原理图或程序流程图）

（1）设计并实现程序，求解出正确的解答路径；

（2）对所设计的算法采用大O符号进行时间复杂性和空间复杂性分析；

（3）对一般图搜索的技术要点和技术难点进行评述性分析。

三、所用仪器、材料（设备名称、型号、规格等或使用软件）

1台PC及VISUAL C++6.0软件

四、实验方法、步骤（或：程序代码或操作过程）

1、先创建项目，新建Source File文件：main.cpp。

#include ＜iostream＞

#include "Node.h"

#include "Queue.h"

#include "Search.h"

#include "Tree.h"

void CreateNode1(std::vector＜int＞& s)

{

s.push_back(2);

s.push_back(8);

s.push_back(3);

s.push_back(1);

s.push_back(0);

s.push_back(4);

s.push_back(7);

s.push_back(6);

s.push_back(5);

}

void CreateNode4(std::vector＜int＞& d)

{

d.push_back(2);

d.push_back(8);

d.push_back(3);

d.push_back(1);

d.push_back(6);

d.push_back(4);

d.push_back(7);

d.push_back(0);

d.push_back(5);

}

void CreateNode8(std::vector＜int＞& d)

{

d.push_back(0);

d.push_back(2);

d.push_back(3);

d.push_back(1);

d.push_back(8);

d.push_back(4);

d.push_back(7);

d.push_back(6);

d.push_back(5);

}

void CreateNode20(std::vector＜int＞& d)

{

d.push_back(2);

d.push_back(0);

d.push_back(8);

d.push_back(1);

d.push_back(4);

d.push_back(3);

d.push_back(7);

d.push_back(6);

d.push_back(5);

}

void CreateNode27(std::vector＜int＞& d)

{

d.push_back(1);

d.push_back(2);

d.push_back(3);

d.push_back(8);

d.push_back(0);

d.push_back(4);

d.push_back(7);

d.push_back(6);

d.push_back(5);

}

void CreateNode_test1(std::vector＜int＞& d)

{

d.push_back(7);

d.push_back(6);

d.push_back(5);

d.push_back(4);

d.push_back(0);

d.push_back(1);

d.push_back(3);

d.push_back(8);

d.push_back(2);

}

void test_expand()

{

std::vector＜int＞ s;

CreateNode1(s);

std::vector＜int＞ d;

CreateNode4(d);

Node source(s);

Node dest(d);

source.Display();

Search search(&source);

std::cout ＜＜ source.Expand(dest, search);

}

void test_search()

{

std::vector＜int＞ s;

CreateNode1(s);

std::vector＜int＞ d;

CreateNode4(d);

Node source(s);

Node dest(d);

source.Display();

dest.Display();

Search search(&source);

search.Find( & dest);

search.DisplayRoute();

}

void test_search2level()

{

std::vector＜int＞ s;

CreateNode1(s);

std::vector＜int＞ d;

CreateNode8(d);

Node source(s);

Node dest(d);

source.Display();

dest.Display();

Search search(&source);

search.Find( & dest);

search.DisplayRoute();

}

void test_search_lab1()

{

std::vector＜int＞ s;

CreateNode1(s);

std::vector＜int＞ d;

CreateNode27(d);

Node source(s);

Node dest(d);

source.Display();

dest.Display();

Search search(&source);

search.Find( & dest);

search.DisplayRoute();

}

int main(int argc, char** argv)

{

// test_expand();

// test_search();

// test_search2level();

// test_search_lab1();

std::vector＜int＞ s;

CreateNode1(s);

std::vector＜int＞ d;

CreateNode27(d);

Node source(s);

Node dest(d);

source.Display();

dest.Display();

Search search(&source);

search.Find( & dest);

search.DisplayRoute();

return 0;

}

2、新建Source File文件：Node.cpp

#ifndef PROGECT_1_NODE

#define PROGECT_1_NODE

#include ＜vector＞

#include "Search.h"

enum OP

{

EMPTY,

UP,

DOWN,

LEFT,

RIGHT

};

bool IsOpposite(OP opa, OP opb);

class Node

{

public:

Node(std::vector＜int＞ const& state);

bool Expand(Node const& destNode, Search& search);

void Display() const;

void DisplayRoute() const;

bool operator==(Node const& v) const;

private:

Node* CreateChild(OP op);

int FindEmptySpaceId() const;

std::vector＜OP＞ GenerateLegalOperators(int spaceId) const;

int CalIdBasedOP(OP op, int spaceId) const;

bool IsWithinRange(OP op, int spaceId) const;

std::vector＜int＞ m_state;

Node *m_pParent;

std::vector＜Node*＞ m_children;

OP m_op;

};

#endif // PROGECT_1_NODE

3新建Heard File文件：node.h。

代码：#include ＜iostream＞

#include ＜math.h＞

#include "Node.h"

bool IsOpposite(OP opa, OP opb)

{

if (LEFT==opa && RIGHT == opb)

return true;

if (RIGHT==opa && LEFT == opb)

return true;

if (UP==opa && DOWN == opb)

return true;

if (DOWN==opa && UP == opb)

return true;

return false;

}

Node::Node(std::vector＜int＞ const& state)

: m_state(state)

, m_pParent(NULL)

, m_children()

, m_op(EMPTY)

{

}

void ShowOP(OP op)

{

switch (op)

{

case EMPTY:

std::cout ＜＜ "EMPTY";

break;

case UP:

std::cout ＜＜ "UP";

break;

case DOWN:

std::cout ＜＜ "DOWN";

break;

case LEFT:

std::cout ＜＜ "LEFT";

break;

case RIGHT:

std::cout ＜＜ "RIGHT";

break;

default:

exit(-1);

}

}

void ShowOPs(std::vector＜OP＞ const& ops)

{

for (int id=0; id＜ops.size(); ++id)

{

ShowOP(ops[id]);

std::cout ＜＜ " ";

}

std::cout ＜＜ std::endl;

}

bool Node::Expand(Node const& destNode, Search& search)

{

int spaceId = FindEmptySpaceId();

std::cout ＜＜ "space is at " ＜＜ spaceId ＜＜ std::endl;

std::vector＜OP＞ legalOPs = GenerateLegalOperators(spaceId);

ShowOPs(legalOPs);

while ( legalOPs.size() ＞ 0 )

{

OP op = legalOPs[ legalOPs.size() - 1 ];

legalOPs.pop_back();

Node* pChild = CreateChild(op);

if ( *pChild == destNode )

{

search.SetDestPt(pChild);

return true;

}

search.GetQueue().EnQueue(pChild);

}

return false;

}

void Node::Display() const

{

for(int i=0; i＜m_state.size(); ++i)

{

std::cout ＜＜ m_state[i] ＜＜ " ";

}

std::cout ＜＜ std::endl;

std::cout ＜＜ " pParent: " ＜＜ m_pParent ＜＜ std::endl;

std::cout ＜＜ " op: ";

ShowOP(m_op);

std::cout ＜＜ std::endl;

std::cout ＜＜ " ";

for(int j=0; j＜m_children.size(); ++j)

{

std::cout ＜＜ m_children[j] ＜＜ " ";

}

std::cout ＜＜ std::endl;

}

void Node::DisplayRoute() const

{

std::vector＜OP＞ routeOps;

Node const* pNode = this;

while ( NULL != pNode )

{

routeOps.push_back(pNode-＞m_op);

pNode = pNode-＞m_pParent;

}

for(int id=routeOps.size()-2; id＞=0 ; --id)

{

ShowOP( routeOps[id] );

std::cout ＜＜ " ";

}

std::cout ＜＜ std::endl;

}

bool Node::operator==(Node const& v) const

{

for (int id=0; id＜m_state.size(); ++ id)

{

if ( m_state[id] != v.m_state[id] )

return false;

}

return true;

}

Node* Node::CreateChild(OP op)

{

std::vector＜int＞ childState = m_state;

int exchangePos1 = FindEmptySpaceId();

int exchangePos2 = CalIdBasedOP(op, exchangePos1);

int temp = childState[exchangePos1];

childState[exchangePos1] = childState[exchangePos2];

childState[exchangePos2] = temp;

Node* child = new Node(childState);

child-＞m_pParent = this;

child-＞m_op = op;

m_children.push_back(child);

return child;

}

int Node::FindEmptySpaceId() const

{

for (int id=0; id＜m_state.size(); ++id)

{

if ( 0 == m_state[id] )

{

return id;

}

}

return -1;

}

std::vector＜OP＞ Node::GenerateLegalOperators(int spaceId) const

{

std::vector＜OP＞ allPossibleOps;

allPossibleOps.push_back(UP);

allPossibleOps.push_back(DOWN);

allPossibleOps.push_back(LEFT);

allPossibleOps.push_back(RIGHT);

std::vector＜OP＞ ops;

for (int id=0; id＜allPossibleOps.size(); ++id)

{

OP op = allPossibleOps[id];

if( IsOpposite(op, m_op) )

{

continue;

}

if ( IsWithinRange(op, spaceId) )

{

ops.push_back(op);

}

}

return ops;

}

int Node::CalIdBasedOP(OP op, int spaceId) const

{

switch (op)

{

case UP:

spaceId -= int( sqrt( m_state.size() ) );

break;

case DOWN:

spaceId += int( sqrt( m_state.size() ) );

break;

case LEFT:

--spaceId;

break;

case RIGHT:

++spaceId;

break;

default:

return -1;

}

return spaceId;

}

bool Node::IsWithinRange(OP op, int spaceId) const

{

spaceId = CalIdBasedOP(op, spaceId);

if (spaceId ＞= 0 && spaceId ＜ m_state.size())

{

return true;

}

return false;

}

4、新建Source File文件：Queue.cpp，

代码：#include "Queue.h"

void Queue::EnQueue(Node* pNode)

{

m_queue.push_back(pNode);

}

Node* Queue::DeQueue()

{

if ( m_queue.size() == 0 )

{

return NULL;

}

Node* pNode = m_queue[0];

m_queue.pop_front();

return pNode;

}

5新建Heard File文件：Queue.h。

代码：

#ifndef PROGECT_1_QUEUE

#define PROGECT_1_QUEUE

#include ＜deque＞

class Node;

class Queue

{

public:

void EnQueue(Node* pNode);

Node* DeQueue();

private:

std::deque＜Node*＞ m_queue;

};

#endif // PROGECT_1_QUEUE

6、新建Source File文件：Search.cpp，

代码：

#include "Search.h"

#include "Node.h"

Search::Search(Node* root)

: m_queue()

, m_pDestNode( NULL )

{

m_queue.EnQueue(root);

}

Node* Search::Select()

{

return m_queue.DeQueue();

}

void Search::Find(Node* destNode)

{

bool isFound = false;

while ( !isFound )

{

Node* pNode = Select();

pNode-＞Display();

isFound = pNode-＞Expand(*destNode, *this);

}

}

void Search::DisplayRoute() const

{

m_pDestNode-＞DisplayRoute();

}

7新建Heard File文件：Search.h。

代码：

#ifndef PROGECT_1_SEARCH

#define PROGECT_1_SEARCH

#include "Queue.h"

class Node;

class Search

{

public:

Search(Node* root);

Queue& GetQueue()

{

return m_queue;

}

void Find(Node* destNode);

Node* Select();

void SetDestPt(Node* pDestNode)

{

m_pDestNode = pDestNode;

}

void DisplayRoute() const;

private:

Queue m_queue;

Node* m_pDestNode;

};

#endif // PROGECT_1_SEARCH

8、新建Source File文件：Tree.cpp，

代码：

#include "Tree.h"

9新建Heard File文件：Tree.h。

代码：

#ifndef PROGECT_1_TREE

#define PROGECT_1_TREE

#endif // PROGECT_1_TREE

五、实验过程原始记录( 测试数据、图表、计算等)

六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）

通过完成这次八数码难题试验报告，我对编程的理解更深刻了，以前做的很多编程仅仅是

几十行的一个函数的代码，而这次的工作量明显大了很多，需要构建几个

好多文件才能完成，在试验中虽然遇到很多的困难，但在老师同学的帮助下，还是学到了很多知识，这次的试验使我在以后的编程中，思路更加开阔了