智能制造系统概论报告.doc

一、问题描述
8数码问题又称9宫问题，与游戏“华容道”类似。意在给定的33´棋格的8个格子内分别放一个符号，符号之间互不相同，余下的一格为空格。并且通常把8个符号在棋格上的排列顺序称作8数码的状态。开始时，规则给定一个初始状态和一个目标状态，并要求被试者对棋格内的符号经过若干次移动由初始状态达到目标状态，这个过程中只有空格附近的符号可以朝空格的方向移动，且每次只能移动一个符号。为方便编程和表示，本文中8个格子内的符号分别取1—8的8个数字表示，空格用0表示。并给定8数码的初始状态和目标状态分别如图1、2所示。

1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
0
7
8

图2 目标状态
图1 初始状态

则要求以图1为初始状态，通过交换0和0的上、下、左、右四个方位的数字（每次只能和其中一个交换），达到图2所示目标状态。
二、算法设计
根据任务要求，本文采用A*搜索算法。但要在计算机上通过编程解决该问题，还应当解决该问题在计算机上表示的方式，并设计合适的启发函数，以提高搜索效率。
采用A*算法求解8位码：
估价函数：f（n）=g（n）+h（n），其中
g（n）：从目标节点到当前节点的花费——与初始节点s相比，当前节点n中“不在位”的将牌个数之和，
h（n）：当前节点n到目标节点的花费——与目标节点d相比，当前节点n中“不在位”的将牌个数之和。
主要搜索过程伪代码如下：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值; 
将起点放入OPEN表; 
while(OPEN!=NULL)
{  
   从OPEN表中取估价值f最小的节点n;    
if(n节点==目标节点)
{    
break;    
}  

for(当前节点n 的每个子节点X)   
 { 
   算X的估价值;    
if(X in OPEN)   
{  
   if( X的估价值小于OPEN表的估价值 )
{    
把n设置为X的父亲;
更新OPEN表中的估价值; //取最小路径的估价值 
}  
} 
if(X inCLOSE)
{  
if( X的估价值小于CLOSE表的估价值 )
{   
把n设置为X的父亲;   
 更新CLOSE表中的估价值;  
把X节点放入OPEN;  //取最小路径的估价值 
 }   
}
if(X not in both)
{   
把n设置为X的父亲;   
求X的估价值;  
   并将X插入OPEN表中; //还没有排序 
 }  
  }//end for 
将n节点插入CLOSE表中;  
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。  
 }//end while(OPEN!=NULL) 
 保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；

三、具体实现
1、 结点编码 
对于8数码问题，每个结点有8个数字和一个空格，可以将空格看成0，那么一共有9个数字，可以将这9个数字组成一个9位数，即用一个整数表示一个结点对应的信息。
2、 open表的数据结构表示 
Open表设置成3*n的矩阵，第一行存储已生成但未扩展的节点，第二行存储第一行节点对应的父节点。
3、closed表的数据结构表示 
closed表存储已扩展的结点间的扩展关系，主要用于输出路径。Closed表也是3*n的矩阵，其每一列中三个元素与open表中的意义相同，closed表存储open表中已被扩展的节点。
4、程序设计
//读入，将8数码矩阵（或整数表示的节点）转换为整数（或矩阵）表示，flag ==1时，将8数码矩阵转换为整数，flag==0时，将整数表示的节点转换为整数。
function output=read(input,flag)
if flag==1
output=0;
p=1;
for i=1:3
for j=1:3
if input(i,j)==0
index=(i-1)*3+j;
else
output=output+input(i,j)*10^p;
p=p+1;
end
end
end
output=output+index;
else
output=zeros(3,3);
index=mod(input,10);
input=(input-index)/10;
for i=1:3
for j=1:3
if index==(i-1)*3+j
output(i,j)=0;
else
mid=mod(input,10);
output(i,j)=mid;
input=(input-mid)/10;
end
end
end
end

// 计算两节点之间的距离，这里距离定义为两节点矩阵对应位置不相等的将牌数之和。
function cnt=distance(mat1,mat2)
cnt=0;
for i=1:9
if mat1(i)~=mat2(i)
cnt=cnt+1;
end
end
end

//对节点n进行扩展
function re=findnode(node)
mat=read(node,0);
[x,y]=find(mat==0);
xtran=[-1, 0, 1, 0];
ytran=[0, 1, 0, -1];
re=[];
for i=1:4
% |1
% 4------2
% |3
nx = x + xtran(i);
ny = y + ytran(i);
if nx>0&&nx<4&&ny>0&&ny<4
tmat=mat;
tmat(x,y)=tmat(nx,ny);
tmat(nx,ny)=0;
mid=read(tmat,1);
re=[re,mid];
end
end

end

//主程序：
function unicode_astar()
%
% astar for 3*3M
%
%%
start=[1,2,3;4,5,6;7,8,0];
target=[1,2,3;4,5,6;0,7,8];
%init
clc;
s=read(start,1);
d=read(target,1);
%1. Add the source node to the open list
openlist = [s s 0]';
closedlist = [];
% Define what is targe is in closed list (tiscl)
tiicl=0;
openlempty=0; ts=0;
%%
while ( tiicl==0 || openlempty==0)

ts=ts+1;
[widop,lenol]=size(openlist);
olcst=zeros(4,lenol);
% Generate Cost function for Open list (open list cost) storing G H F
olcst(1,:)=openlist(1,:);
for col=1:lenol
mat=read(openlist(1,col),0);
fmat=read(openlist(2,col),0);
% Calculate G for the Open list
olcst(2,col)=distance(mat,fmat)+openlist(3,col);
% Caculate H for the open list
olcst(3,col)=distance(mat,target);
% Calculate F = G + H
olcst(4,col)=olcst(3,col)+olcst(2,col);
end

% a) Look for the lowest F cost square on the open list. We refer to
% this as the current square.
x=find(olcst(4,:)==min(olcst(4,:)),1);
curnode=openlist(1,x);

curnodecst=openlist(3,x);
% b) Switch it to the closed list.%
[clw,lencl]=size(closedlist);
% add node and its parent to closed list
closedlist(:,lencl+1)=openlist(:,x);
% Remove it from the open list
openlist(:,x)=[];

% c) For each of the squares adjacent to this current square ?
% If it is not walkable or if it is on the closed list, ignore it.
% *
cand=findnode(curnode); % Walkable nodes from cur node

for cnn=1:length(cand) % Remove from list if on closed list already
if cnn>length(cand)
break;
end
cndl=find(cand(cnn)==closedlist(1,:), 1);
if isempty(cndl)~=1
cand(cnn)=[];
end
end
% Otherwise do the following.
for cn2=1:length(cand)
isinol=find(openlist(1,:)==cand(cn2), 1);
% If it is not on the open list, add it to the open list. Make the
% current square the parent of this square. Record the F, G, and H
% costs of the square.
cnmat=read(cand(cn2),0);
curmat=read(curnode,0);
if isempty(isinol)==1
candcst=curnodecst+distance(curmat,cnmat)+distance(cnmat,target);
[widop,lenol]=size(openlist);
openlist(:,lenol+1)=[cand(cn2) curnode candcst]';
end

isinol=find(openlist(1,:)==cand(cn2));
n=length(isinol);
for i=1:n
gcurnode=distance(target,curmat);
oldmat=read(openlist(2,isinol(i)),0);
goldp=distance(target,oldmat);

if gcurnode<=goldp
openlist(2,isinol(i))=curnode;
openlist(3,isinol(i))=curnodecst+distance(curmat,cnmat)+distance(cnmat,target);
end
end
end
if ~isempty(find(closedlist(1,:)==d, 1))
tiicl=1;
end
if ~isempty(openlist==0)
openlempty=1;
end
end

%%
steps(1)=d;
nd=d;
n=2;
while nd~=s
x=find(closedlist(1,:)==nd, 1);
nd=closedlist(2,x);
steps(n)=nd;
n=n+1;
end
%%
n=length(steps);
for i=1:n
mat=read(steps(i),0);
disp(mat);
end
end

程序运行结果如下图：