昆明理工大学信息工程与自动化学院学生实验报告
（ 20## — 20## 学年 第 1 学期 ）
课程名称：人工智能及其应用 开课实验室：信自楼444 2014年12月30日
一、上机目的及内容
1.上机内容：
求解八数码问题。
问题描述：八数码难题，问题描述：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态S1如图所示，可以使用的操作有：空格上移，空格左移，空格右移，空格下移。只允许位于空格左，上，右，下方的牌移入空格。用广度优先搜索策略寻找从初始状态到目标状态的解路径。
2.上机目的:
（1）复习程序设计和数据结构课程的相关知识；
（2）熟悉人工智能系统中的问题求解过程；
（3）熟悉对八码数问题的建模、求解及编程语言的运用。
二、实验原理及基本技术路线图（方框原理图或程序流程图）
（1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点的表中；
（2）建立一个叫做CLOSED的已扩展节点表，其初始为空表；
（3）LOOP:若OPEN表是空表，则失败退出；
（4）选择OPEN表上的第一个节点，把它从OPEN表移除并放进CLOSED表中，称此节点为节点n；
（5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的；
（6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点舔到图中；
（7）对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN表或CLOSED表上的成员，确定是否需要更改通到n的指针方向；
（8）按某一任意方式或按某个探视值，重排OPEN表。
宽度优先算法实现过程
（1）把起始节点放到OPEN表中；
（2）如果OPEN是个空表，则没有解，失败退出；否则继续；
（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；
（4）扩展节点n。如果没有后继节点，则转向（2）；
（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；
（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转（2）。
深度优先实现过程
（1）把起始节点S放入未扩展节点OPEN表中。如果此节点为一目标节点，则得一个解；
（2）如果OPEN为一空表，则失败退出；
（3）把第一个节点从OPEN表移到CLOSED表；
（4）如果节点n的深度等于最大深度，则转向（2）；
（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）；
（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
1台PC及VISUAL C++6.0软件
四、实验方法、步骤（或：程序代码或操作过程）
program 8no_bfs; {八数码的宽度优先搜索算法}
Const
Dir : array[1..4,1..2]of integer {四种移动方向，对应产生式规则}
= ((1,0),(-1,0),(0,1),(0,-1));
n=10000;
Type
T8no = array[1..3,1..3]of integer;
TList = record
Father : integer; {父指针}
dep : byte; {深度}
X0,Y0 : byte; {0的位置}
State : T8no; {棋盘状态 }
end;
Var
Source,Target : T8no;
List : array[0..10000] of TList; {综合数据库 }
Closed,open,Best : integer { Best表示最优移动次数}
Answer : integer; {记录解}
Found : Boolean; {解标志}
procedure GetInfo; {读入初始和目标节点}
var i,j : integer;
begin
for i:=1 to 3 do
for j:=1 to 3 do read(Source[i,j]);
for i:=1 to 3 do
for j:=1 to 3 do read(Target[i,j]);
end;
procedure Initialize; {初始化}
var x,y : integer;
begin
Found:=false;
Closed:=0;open:=1;
with List[1] do begin
State:=Source;dep:=0;Father:=0;
For x:=1 to 3 do
For y:=1 to 3 do
if State[x,y]=0 then Begin x0:=x;y0:=y; End;
end;
end;
Function Same(A,B : T8no):Boolean; {判断A,B状态是否相等 }
Var i,j : integer;
Begin
Same:=false;
For i:=1 to 3 do for j:=1 to 3 do if A[i,j]<>B[i,j] then exit;
Same:=true;
End;
Function not_Appear(new : tList):boolean;{判断new是否在List中出现 }
var i : integer;
begin
not_Appear:=false;
for i:=1 to open do if Same(new.State,List[i].State) then exit;
not_Appear:=true;
end;
procedure Move(n : tList;d : integer;var ok : boolean;var new : tList);
{将第d条规则作用于n得到new,OK是new是否可行的标志 }
var x,y : integer;
begin
X := n.x0 + Dir[d,1];
Y := n.y0 + Dir[d,2];
{判断new的可行性}
if not ((X > 0) and ( X < 4 ) and ( Y > 0 ) and ( Y < 4 )) then begin ok:=false;exit end;
OK:=true;
new.State:=n.State; {new=Expand(n,d)}
new.State[X,Y]:=0;
new.State[n.x0,n.y0]:=n.State[X,Y];
new.X0:=X;new.Y0:=Y;
end;
procedure Add(new : tList); {插入节点new}
begin
if not_Appear(new) then Begin {如果new没有在List出现 }
Inc(open); {new加入open表 }
List[open] := new;
end;
end;
procedure Expand(Index : integer; var n : tList); {扩展n的子节点}
var i : integer;
new : tList;
OK : boolean;
Begin
if Same(n.State , Target) then begin {如果找到解}
Found := true;
Best :=n.Dep;
Answer:=Index;
Exit;
end;
For i := 1 to 4 do begin {依次使用４条规则}
Move(n,i,OK,new);
if not ok then continue;
new.Father := Index;
new.Dep :=n.dep + 1;
Add(new);
end;
end;
procedure GetOutInfo; {输出}
procedure Outlook(Index : integer); {递归输出每一个解}
var i,j : integer;
begin
if Index=0 then exit;
Outlook(List[Index].Father);
with List[Index] do
for i:=1 to 3 do begin
for j:=1 to 3 do write(State[i,j],' ');
writeln;
end;
writeln;
end;
begin
Writeln('Total = ',Best);
Outlook(Answer);
end;
procedure Main; {搜索主过程}
begin
Repeat
Inc(Closed);
Expand(Closed,List[Closed]); {扩展Closed}
Until (Closed>=open) or Found;
if Found then GetOutInfo {存在解}
else Writeln('no answer'); {无解}
end;
Begin
Assign(Input,'input.txt');ReSet(Input);
Assign(Output,'Output.txt');ReWrite(Output);
GetInfo;
Initialize;
Main;
Close(Input);Close(Output);
End.
五、实验过程原始记录( 测试数据、图表、计算等)
六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）
人工智能这门课程综合了许多学科的知识，这些知识面十分广，以及它的应用也是十分广泛的，才刚开始学习的时候就会感觉有点复杂，因为它毕竟综合了一些我们还没有学过的知识。
通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。用广度优先算法实现八数码问题，其实是一种比较费劲的方式；然而深度优先将是一个很好的方法，利用深度优先不但减少了程序实现的时间，是一种不错的方式。但最好的方式是启发式搜索方式实现，在很大程度上相对于前两种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。
这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执行过程有了更一步的认识。也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验使我受益匪浅。
第二篇：实验文档模板-八数码问题
人工智能实验报告
一、问题描述：
在3×3的棋盘上，摆着8个将牌，每个将牌都刻有1～8数码中的某个数码。棋盘中留有一个空格，允许其周围的某个将牌向空格移动，这样通过移动将牌就可以不断改变棋牌的布局。
请用计算机实现算法解决八数码问题：提供输入初始将牌布局和目标将牌布局的功能，在接收输入之后，输出移动的步骤（方式）。
二、算法设计：
三、算法实现：
#include<iostream>
using namespace std;
struct Node
{
int data[4][4];
int g,h,f,r,c,last,from;
//blank location(r,c),last point to the parent node,from point out the blank's coming //direction
};
Node list[100000];//open and closed
//Node end;//the target node
void calculateF(Node &node,Node target)
{//calculate the f value
node.h=0;
for(int i=1;i<4;i++)
{
for(int j=1;j<4;j++)
{
if(i==target.r&&j==target.c)
{
continue;
}
if(node.data[i][j]!=target.data[i][j])
{
node.h++;
}
}
}
node.h=0;//calculate the h value above,delete this sentence if use the A* algorithm
node.f=node.g+node.h;
}
bool isTarget(Node node,Node target)
{//decide whether node is the answer
for(int i=1;i<4;i++)
{
for(int j=1;j<4;j++)
{
if(node.data[i][j]!=target.data[i][j])
{
return false;
}
}
}
return true;
}
void swap(Node node1,Node node2)
{//node1's value in exchange with node2's value
int temp=node1.c;
node1.c=node2.c;
node2.c=temp;
temp=node1.f;
node1.f=node2.f;
node2.f=temp;
temp=node1.g;
node1.g=node2.g;
node2.g=temp;
temp=node1.h;
node1.f=node2.h;
node2.h=temp;
temp=node1.r;
node1.r=node2.r;
node2.r=temp;
temp=node1.last;
node1.last=node2.last;
node2.last=temp;
for(int i=1;i<4;i++)
{
for(int j=1;j<4;j++)
{
temp=node1.data[i][j];
node1.data[i][j]=node2.data[i][j];
node2.data[i][j]=temp;
}
}
return;
}
void sort(int start,int end)
{//sort from the index value of start to the end,note that index end is invalid.
int times=0;;
bool flag=true;
while(flag)
{
times++;
flag=false;
for(int i=start;i<end-times;i++)
{
if(list[i].f>list[i+1].f)
{
swap(list[i],list[i+1]);
flag=true;
}
}
}
return;
}
void print(Node node)
{//print the reverse path
while(1)
{
for(int i=1;i<4;i++)
{
for(int j=1;j<4;j++)
{
cout<<node.data[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
if(node.last==-1)
{
break;
}
node=list[node.last];
}
cout<<endl;
return;
}
void algorithm(Node start,Node target)
{
int num=1,star=0;
while(num!=0)
{
if(isTarget(list[star],target))
{
cout<<"success,the answer is"<<endl;
print(list[star]);
break;
}
//develop
int r=list[star].r,c=list[star].c;
if(list[star].from!=0&&list[star].r!=1)
{//blank up
list[star+num]=list[star];
list[star+num].data[r][c]=list[star].data[r-1][c];
list[star+num].data[r-1][c]=0;
list[star+num].g=list[star].g+1;
list[star+num].last=star;
list[star+num].from=2;
list[star+num].r--;
calculateF(list[star+num],target);
num++;
}
if(list[star].from!=1&&list[star].c!=1)
{//blank left
list[star+num]=list[star];
list[star+num].data[r][c]=list[star].data[r][c-1];
list[star+num].data[r][c-1]=0;
list[star+num].g=list[star].g+1;
list[star+num].last=star;
list[star+num].from=3;
list[star+num].c--;
calculateF(list[star+num],target);
num++;
}
if(list[star].from!=2&&list[star].r!=3)
{//blank down
list[star+num]=list[star];
list[star+num].data[r][c]=list[star].data[r+1][c];
list[star+num].data[r+1][c]=0;
list[star+num].g=list[star].g+1;
list[star+num].last=star;
list[star+num].from=0;
list[star+num].r++;
calculateF(list[star+num],target);
num++;
}
if(list[star].from!=3&&list[star].c!=3)
{//blank right
list[star+num]=list[star];
list[star+num].data[r][c]=list[star].data[r][c+1];
list[star+num].data[r][c+1]=0;
list[star+num].g=list[star].g+1;
list[star+num].last=star;
list[star+num].from=1;
list[star+num].c++;
calculateF(list[star+num],target);
num++;
}
star++;
num--;
sort(star,star+num);
}
}
int main()
{
int i,j;
for(i=1;i<4;i++)
{// initialize the start node that is the index 0 of list
for(j=1;j<4;j++)
{
cin>>list[0].data[i][j];
if(list[0].data[i][j]==0)
{
list[0].r=i;
list[0].c=j;
}
}
}
list[0].g=0;
list[0].from=list[0].last=-1;
Node target;
for(i=1;i<4;i++)
{
for(j=1;j<4;j++)
{
cin>>target.data[i][j];
if(target.data[i][j]==0)
{
target.r=i;
target.c=j;
}
}
}
algorithm(list[0],target);
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////// 测试数据：
2 8 3 1 6 4 7 0 5
1 2 3 8 0 4 7 6 5
输出结果：
1 2 3
8 0 4
7 6 5
1 2 3
0 8 4
7 6 5
0 2 3
1 8 4
7 6 5
2 0 3
1 8 4
7 6 5
2 8 3
1 0 4
7 6 5
2 8 3
1 6 4
7 0 5