人工智能课内实验报告2

人工智能课内实验报告（二）----重排九宫（A*算法）一、实验目的1.熟悉启发式搜索的思想，加深对各种图搜索策略概念的理解； 2.运用搜索算法重排九宫使之从初始状态到底目标状态，并求解最短路径。二、实验内容在三种不同的搜索算法中任选一种实现重排九宫。这三种方法分别是：A*算法、有界深度优先搜索和广度优先搜索。具体描述：在一个3×3的方格棋盘上放置8个标有1、2、3、4、5、6、7、8数字的将牌，留下一个空格（用0表示）。

规定：与空格相邻的将牌可以移入空格。

要求：寻找一条从初始状态到目标状态的将牌移动路线。三、实验原理启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。A*算法是一种启发式搜索。

广度优先搜索按照“先扩展出的节点先被考察”的原则进行搜索。

深度优先搜索按照“后扩展出的节点先被考察”的原则进行搜索。

有界深度优先搜索的原则与深度优先搜索相同，但是它规定了深度限界，使搜索不得无限制地向纵深方向发展。（一）搜索的一般描述：

1.

把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；2.

检查OPEN表是否为空，若为空则问题无解，退出；

3.

把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；

4.

考察节点n是否为目标节点。若是，则求得了问题的解，退出；

5.

扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；

6.

针对M中子节点的不同情况，分别进行如下处理：

（1）对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）

（2）对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中）

（3）

对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中）

7.按某种搜索策略对OPEN表中的节点进行排序；

8.

转第2步。（二）A*算法描述：

1.

把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；

2.

检查OPEN表是否为空，若为空则问题无解，退出；

3.

把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；

4.

考察节点n是否为目标节点。若是，则求得了问题的解，退出；

5.

扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；

6.

针对M中子节点的不同情况，分别进行如下处理：

（1）对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）

（2）对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中,对g(x)进行更新）

（3）对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中,

对节点n子节点的子节点更新g(x)

）

7.对OPEN表中的节点按估价函数进行排序；8.

转第2步。A*算法实验程序及运行结果程序如下：#include"iostream.h"#include<time.h>#include<stdio.h>#include<dos.h>#include<conio.h>staticinttarget[9]={1,2,3,8,0,4,7,6,5};//classdefinitionclasseight_num{private: intnum[9]; intnot_in_position_num; intdeapth; inteva_function;public: eight_num*parent; eight_num*leaf_next; eight_num*leaf_pre;eight_num(intinit_num[9]); eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9) { num[0]=num1; num[1]=num2; num[2]=num3; num[3]=num4; num[4]=num5; num[5]=num6; num[6]=num7; num[7]=num8; num[8]=num9; } eight_num(void) { for(inti=0;i<9;i++) num[i]=i; }voidcul_para(void);voidget_numbers_to(intother_num[9]); intget_nipn(void) {returnnot_in_position_num;} intget_deapth(void) {returndeapth;} intget_evafun(void) {returneva_function;} voidset_num(intother_num[9]);voidshow(void); eight_num&operator=(eight_num&); eight_num&operator=(intother_num[9]); intoperator==(eight_num&); intoperator==(intother_num[9]);};//计算启发函数g(n)的值voideight_num::cul_para(void){ inti; inttemp_nipn=0; for(i=0;i<9;i++) if(num[i]!=target[i]) temp_nipn++; not_in_position_num=temp_nipn; if(this->parent==NULL) deapth=0; else deapth=this->parent->deapth+1; eva_function=not_in_position_num+deapth;}//构造函数1eight_num::eight_num(intinit_num[9]){ for(inti=0;i<9;i++) num[i]=init_num[i];}//显示当前节点的状态voideight_num::show(){ cout<<num[0]; cout<<""; cout<<num[1]; cout<<""; cout<<num[2]; cout<<"\n"; cout<<num[3]; cout<<""; cout<<num[4]; cout<<""; cout<<num[5]; cout<<"\n"; cout<<num[6]; cout<<""; cout<<num[7]; cout<<""; cout<<num[8]; cout<<"\n";}//复制当前节点状态到一个另数组中voideight_num::get_numbers_to(intother_num[9]){ for(inti=0;i<9;i++) other_num[i]=num[i];}//设置当前节点状态(欲设置的状态记录的other数组中)voideight_num::set_num(intother_num[9]){ for(inti=0;i<9;i++) num[i]=other_num[i];}eight_num&eight_num::operator=(eight_num&another_8num){ for(inti=0;i<9;i++) num[i]=another_8num.num[i]; not_in_position_num=another_8num.not_in_position_num; deapth=another_8num.deapth+1; eva_function=not_in_position_num+deapth; return*this;}eight_num&eight_num::operator=(intother_num[9]){ for(inti=0;i<9;i++) num[i]=other_num[i]; return*this;}inteight_num::operator==(eight_num&another_8num){ intmatch=1; for(inti=0;i<9;i++) if(num[i]!=another_8num.num[i]) { match=0; break; } if(match==0) return0; else return1;}inteight_num::operator==(intother_num[9]){ intmatch=1; for(inti=0;i<9;i++) if(num[i]!=other_num[i]) { match=0; break; } if(match==0) return0; else return1;}//classdefinitionover//空格向上移intmove_up(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i<3) return0; else { num[i]=num[i-3]; num[i-3]=0; return1; }}//空格向下移intmove_down(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i>5) return0; else { num[i]=num[i+3]; num[i+3]=0; return1; }}//空格向左移intmove_left(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i==0||i==3||i==6) return0; else { num[i]=num[i-1]; num[i-1]=0; return1; }}//空格向右移intmove_right(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i==2||i==5||i==8) return0; else { num[i]=num[i+1]; num[i+1]=0; return1; }}//判断可否解出inticansolve(intnum[9],inttarget[9]){ inti,j; intcount_num,count_target; for(i=0;i<9;i++) for(j=0;j<i;j++) { if(num[j]<num[i]&&num[j]!=0) count_num++; if(target[j]<target[i]&&target[j]!=0) count_target++; } if((count_num+count_target)%2==0) return1; else return0;}//判断有无重复intexisted(intnum[9],eight_num*where){ eight_num*p; for(p=where;p!=NULL;p=p->parent) if(*p==num) return1; return0;}//寻找估价函数最小的叶子节点eight_num*find_OK_leaf(eight_num*start){ eight_num*p,*OK; p=OK=start; intmin=start->get_evafun(); for(p=start;p!=NULL;p=p->leaf_next) if(min>p->get_evafun()) { OK=p; min=p->get_evafun(); } returnOK;}//主函数开始intmain(void){ doubletime; clock_tStart,Finish; intmemery_used=0,step=0; intnum[9]; intflag=0;//是否输入错误标志，1表示输入错误 intbingo=0;//是否查找成功标志，1表示成功 inti,j; //cout<<"重排九宫\n\n"; cout<<"初始状态:\n"; for(i=0;i<9;i++) { flag=0; cin>>num[i]; for(j=0;j<i;j++) if(num[i]==num[j]) flag=1; if(num[i]<0||num[i]>8||flag==1) { i--; cout<<"包含无效的数字!\n"; } } eight_numS(num),Target(target); S.parent=S.leaf_next=S.leaf_pre=NULL; S.cul_para(); memery_used++; cout<<"初始状态为:\n"; S.show(); cout<<"目标状态为:\n"; Target.show(); if(!icansolve(num,target)) { cout<<"输入的初始状态无法到达目标状态!\n"; cin>>i; return1; } else{cout<<"变换过程为:\n";} Start=clock(); eight_num*OK_leaf=&S,*leaf_start=&S,*new_8num,*p; while(OK_leaf!=NULL&&bingo!=1) { OK_leaf=find_OK_leaf(leaf_start); if(*OK_leaf==Target) { bingo=1; break; } p=OK_leaf->leaf_pre; OK_leaf->get_numbers_to(num); if(move_up(num)&&!existed(num,OK_leaf)) { new_8num=neweight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; else p->leaf_next=new_8num; p=new_8num; memery_used++; } OK_leaf->get_numbers_to(num); if(move_down(num)&&!existed(num,OK_leaf)) { new_8num=neweight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; else p->leaf_next=new_8num; p=new_8num; memery_used++; } OK_leaf->get_numbers_to(num); if(move_left(num)&&!existed(num,OK_leaf)) { new_8num=neweight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; else p->leaf_next=new_8num; p=new_8num; memery_used++; } OK_leaf->get_numbers_to(num); if(move_right(num)&&!existed(num,OK_leaf)) {new_8num=neweight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_st