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

（ 20## —2013 学年第  1  学期）

课程名称：人工智能        开课实验室：信自楼445      20## 年11月 8日

一、上机目的及内容

1.上机内容：

用深度优先、广度优先、或者是其它方法实现八数码问题

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或MATLAB软件

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

方法一：用C语言实现

#include <stdio.h>

#include <string.h>

#include<stdlib.h>

typedef long UINT64;

typedef struct

{

  char x; //位置x和位置y上的数字换位

  char y; //其中x是0所在的位置

} EP_MOVE;

#define SIZE 3 //8数码问题，理论上本程序也可解决15数码问题，

#define NUM SIZE * SIZE //但move_gen需要做很多修改，输入初始和结束状态的部分和check_input也要修改

#define MAX_NODE 1000000

#define MAX_DEP 100

#define XCHG(a, b) { a=a + b; b=a - b; a=a - b; }

#define TRANS(a, b)

/*{ long iii; (b)=0; for(iii=0; iii < NUM; iii++) (b)=((b) << 4) + a[iii]; }*/ //将数组a转换为一个64位的整数b

#define RTRANS(a, b) \

{ \

long iii; \

UINT64 ttt=(a); \

for(iii=NUM - 1; iii >= 0; iii--) \

{ \

b[iii]=ttt & 0xf; \

ttt>>=4; \

} \

} //将一个64位整数a转换为数组b

//

typedef struct EP_NODE_Tag

{ UINT64 v; //保存状态，每个数字占4个二进制位，可解决16数码问题

struct EP_NODE_Tag *prev; //父节点

struct EP_NODE_Tag *small, *big;

} EP_NODE;

EP_NODE m_ar[MAX_NODE];

EP_NODE *m_root;

long m_depth; //搜索深度

EP_NODE m_out[MAX_DEP]; //输出路径

//

long move_gen(EP_NODE *node, EP_MOVE *move)

{long pz; //0的位置

UINT64 t=0xf;

for(pz=NUM - 1; pz >= 0; pz--)

{if((node->v & t) == 0)

{ break; //找到0的位置

}

t<<=4;

}

switch(pz)

{case 0:

move[0].x=0;

move[0].y=1;

move[1].x=0;

move[1].y=3;

return 2;

case 1:

move[0].x=1;

move[0].y=0;

move[1].x=1;

move[1].y=2;

move[2].x=1;

move[2].y=4;

return 3;

case 2:

move[0].x=2;

move[0].y=1;

move[1].x=2;

move[1].y=5;

return 2;

case 3:

move[0].x=3;

move[0].y=0;

move[1].x=3;

move[1].y=6;

move[2].x=3;

move[2].y=4;

return 3;

case 4:

move[0].x=4;

move[0].y=1;

move[1].x=4;

move[1].y=3;

move[2].x=4;

move[2].y=5;

move[3].x=4;

move[3].y=7;

return 4;

case 5:

move[0].x=5;

move[0].y=2;

move[1].x=5;

move[1].y=4;

move[2].x=5;

move[2].y=8;

return 3;

case 6:

move[0].x=6;

move[0].y=3;

move[1].x=6;

move[1].y=7;

return 2;

case 7:

move[0].x=7;

move[0].y=6;

move[1].x=7;

move[1].y=4;

move[2].x=7;

move[2].y=8;

return 3;

case 8:

move[0].x=8;

move[0].y=5;

move[1].x=8;

move[1].y=7;

return 2;

}

return 0;

}

long mov(EP_NODE *n1, EP_MOVE *mv, EP_NODE *n2)

//走一步，返回走一步后的结果

{

char ss[NUM];

RTRANS(n1->v, ss);

XCHG(ss[mv->x], ss[mv->y]);

TRANS(ss, n2->v);

return 0;

}

long add_node(EP_NODE *node, long r)

{

EP_NODE *p=m_root;

EP_NODE *q;

while(p)

{ q=p;

if(p->v == node->v) return 0;

else if(node->v > p->v) p=p->big;

else if(node->v < p->v) p=p->small;

}

m_ar[r].v=node->v;

m_ar[r].prev=node->prev;

m_ar[r].small=NULL;

m_ar[r].big=NULL;

if(node->v > q->v)

{ q->big= &m_ar[r];

}

else if(node->v < q->v)

{ q->small= &m_ar[r];

}

return 1;

}

/*得到节点所在深度*/

long get_node_depth(EP_NODE *node)

{ long d=0;

while(node->prev)

{ d++;

node=node->prev;

}

return d;

}

/*返回值：成功－返回搜索节点数，节点数不够－(-1)，无解－(-2)*/

long bfs_search(char *begin, char *end)

{ long h=0, r=1, c, i, j;

EP_NODE l_end, node, *pnode;

EP_MOVE mv[4]; //每个局面最多4种走法

TRANS(begin, m_ar[0].v);

TRANS(end, l_end.v);

m_ar[0].prev=NULL;

m_root=m_ar;

m_root->small=NULL;

m_root->big=NULL;

while((h < r) && (r < MAX_NODE - 4))

{ c=move_gen(&m_ar[h], mv);

for(i=0; i < c; i++)

{ mov(&m_ar[h], &mv[i], &node);

node.prev= &m_ar[h];

if(node.v == l_end.v)

{ pnode= &node;

j=0;

while(pnode->prev)

{ m_out[j]=*pnode;

j++;

pnode=pnode->prev;

}

m_depth=j;

return r;

}

if(add_node(&node, r)) r++; //只能对历史节点中没有的新节点搜索，否则会出现环

}

h++;

printf("\rSearch...%9d/%d @ %d", h, r, get_node_depth(&m_ar[h]));

}

if(h == r)

{ return -2; }

else

{return -1; }

}

long check_input(char *s, char a, long r)

{ long i;

for(i=0; i < r; i++)

{ if(s[i] == a - 0x30) return 0; }

return 1;

}

long check_possible(char *begin, char *end)

{ char fs;

long f1=0, f2=0;

long i, j;

for(i=0; i < NUM; i++)

{ fs=0;

for(j=0; j < i; j++)

{

if((begin[i] != 0) && (begin[j] != 0) && (begin[j] < begin[i])) fs++;

}

f1+=fs;

fs=0;

for(j=0; j < i; j++)

{ if((end[i] != 0) && (end[j] != 0) && (end[j] < end[i])) fs++;

}

f2+=fs;

}

if((f1 & 1) == (f2 & 1)) return 1;

else

return 0;

}

void output(void)

{ long i, j, k;

char ss[NUM];

for(i=m_depth - 1; i >= 0; i--)

{ RTRANS(m_out[i].v, ss);

for(j=0; j < SIZE; j++)

{ for(k=0; k < SIZE; k++)

{ printf("%2d", ss[SIZE * j + k]);

}

printf("\n");

}

printf("\n");

}

}

int main(void)

{ char s1[NUM];

char s2[NUM];

long r;

char a;

printf("请输入开始状态:");

r=0;

while(r < NUM)

{ a=getchar();

if(a >= 0x30 && a < 0x39 && check_input(s1, a, r))

{ s1[r++]=a - 0x30;

printf("%c", a);

}

}

printf("\n请输入结束状态:");

r=0;

while(r < NUM)

{ a=getchar();

if(a >= 0x30 && a < 0x39 && check_input(s2, a, r))

{ s2[r++]=a - 0x30;

printf("%c", a);

}

}

printf("\n");

if(check_possible(s1, s2))

{ r=bfs_search(s1, s2);

printf("\n");

if(r >= 0)

{ printf("查找深度=%d,所有的方式=%ld\n", m_depth, r);

output();

}

else if(r == -1)

{ printf("没有找到路径.\n");

}

else if(r == -2)

{printf("这种状态变换没有路径到达.\n");

}

else

{printf("不确定的错误.\n");

}

}

else

{ printf("不允许这样移动!\n");

}

return 0;

}

方法二：用MATLAB实现

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.

五、实验结果

六、实验总结

通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。

用广度优先算法实现八数码问题，其实是一种比较费劲的方式；然而深度优先将是一个很好的方法，利用深度优先不但减少了程序实现的时间，是一种不错的方式。但最好的方式是启发式搜索方式实现，在很大程度上相对于前两种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。

     通过这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执行过程有了更一步的认识。也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验使我受益匪浅。