智能制造系统概论报告

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

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

3、问过的节点。算起点的估价值;将起点放入OPEN表;while(OPEN!=NULL) 从OPEN表中取估价值f最小的节点n;if(n节点=目标节点)break;for(当前节点n的每个子节点X) 算X的估价值;if(XinOPEN) if(X的估价值小于OPEN表的估价值)把n设置为X的父亲;更新OPEN表中的估价值;/取最小路径的估价值if(XinCLOSE)if(X的估价值小于CLOSE表的估价值)把n设置为X的父亲;更新CLOSE表中的估价值;把X节点放入OPEN; /取最小路径的估价值if(Xnotin both)把n设置为X的父亲;求X的估价值; 并将X插入OPEN表中;/还没有排序

4、 /endfor将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序;/实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。/endwhile(OPEN!=NULL)保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；三、具体实现1、结点编码对于8数码问题，每个结点有8个数字和一个空格，可以将空格看成0，那么一共有9个数字，可以将这9个数字组成一个9位数，即用一个整数表示一个结点对应的信息。2、open表的数据结构表示Open表设置成3*n的矩阵，第一行存储已生成但未扩展的节点，第二行存储第一行节点对应的父节点。3、closed表的数据结构表示clos

5、ed表存储已扩展的结点间的扩展关系，主要用于输出路径。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+i

6、nput(i,j)*10p; 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 endend/ 计算两节点之间的距离，这里距离定义为两节点矩阵对应位置不相等的将牌数之和。functio

7、n cnt=distance(mat1,mat2)cnt=0;for i=1:9 if mat1(i)=mat2(i) cnt=cnt+1; endendend/对节点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 nx0&nx0&nylength(cand) break; end cndl=find(can

8、d(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 o

9、f 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 gcurno

10、de=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; endend %steps(1)=d;nd=d;n=2;