当前位置: 首页 > >

启发式搜索算法

发布时间:

人工智能基础实验报告

实验名称:八数码问题 姓名:张俊 学号:2220092333 指导老师:邓安生

启发式搜索算法
1. 实验内容: 使用启发式搜索算法求解 8 数码问题。 ⑴ 编制程序实现求解 8 数码问题 A? 算法,采用估价函数
?w ? n ? ? , f ? n? ? d ? n? ? ? ? p ? n? ?

其中: d ? n ? 是搜索树中结点 n 的深度; w ? n ? 为结点 n 的数据库中错放的棋子个数; p ? n ? 为 结点 n 的数据库中每个棋子与其目标位置之间的距离总和。 ⑵ 分析上述⑴中两种估价函数求解 8 数码问题的效率差别, 给出一个是 p ? n ? 的上界的

h ? n ? 的定义,并测试使用该估价函数是否使算法失去可采纳性。
2. 实验目的 熟练掌握启发式搜索 A? 算法及其可采纳性。 3. 实验原理 八数码问题是在 3 行和 3 列构成的九宫棋盘上放置数码为 1 到 8 的 8 个棋盘,剩下一 个空格的移动来不断改变棋盘的布局,求解这类问题的方法是:给定初始布局(即初始状 态)和目标布局(即目标状态) ,定义操作算子的直观方法是为每个棋牌制定一套可能的走 步》上,下,左,右四种移动,再根据所定义的启发式搜索函数在搜索过程中选择最合适 的操作算子,得到最优的路径。 4.源代码 #include <iomanip> #include <stdlib.h> #include <time.h> #include <iostream> #include <stdio.h> #include <conio.h> #include <math.h>//以上为 C++源文件 using namespace std; static int space=0; int target[9]; class EightNum//定义一个 EightNum 类 {

public:

int num[9]; int f;//初始状态与目标状态相比,棋子错放个数 int deap;//深度 int evalfun;//状态的估价值 EightNum *parent; //以下为类内成员函数的声明 EightNum(int nnum[9]); int get_evalfun(); int get_deapfun(); void eval_func(int id); int Canspread(int n); void Spreadchild(int n); void getnum(int num1[9]); void setnum(int num1[9]); void show(void); int operator ==(EightNum& NewEightN); int operator ==(int num2[9]); int Shownum(); };

//-----------------------以下为 EightNum 类成员函数定义-----------------// class Stack { private: EightNum * eightnum; public: Stack * next; EightNum * Minf(); EightNum * Belong(EightNum * suc); void Putinto(EightNum * suc); };

EightNum::EightNum(int nnum[9]){//此函数功能为:初始化 num[]; for(int i=0;i<9;i++) num[i]=nnum[i]; f=0; deap=0; parent=NULL; }

int EightNum::get_evalfun(){ return evalfun; }

int EightNum::get_deapfun(){ return deap; }

void EightNum::eval_func(int id){//此函数为估价函数 int i,qifa; qifa=0; switch(id){ case 1:{ for(i=0;i<9;i++){ if(num[i]!=target[i]) qifa++; } break; }

case 2:{

int j, h1,h2; for(i=0;i<9;i++){ for(j=0;j<9;j++){ if(num[j]==i)h1=j; if(target[j]==i)h2=j; } qifa+=(int)(fabs((double)(h1/3 - h2/3)) + fabs((double)(h1%3 - h2%3))); } break; } case 3:{ int j, h1,h2; for(i=0;i<9;i++){ for(j=0;j<9;j++){ if(num[j]==i)h1=j; if(target[j]==i)h2=j; } qifa+=(int)(fabs((double)(h1/3 - h2/3)) + fabs((double)(h1%3 - h2%3))); } qifa=3*qifa; break; } default :break; } f=qifa; if(this->parent==NULL) deap=0; else deap=this->parent->deap+1; evalfun=deap+f; }

int EightNum::Canspread(int n) {//判断空格"0"可否移动 int i,flag = 0; for(i = 0;i < 9;i++) if(this->num[i] == 0)break; switch(n) { case 1: if(i/3 != 0)flag = 1;break; case 2: if(i/3 != 2)flag = 1;break; case 3: if(i%3 != 0)flag = 1;break; case 4: if(i%3 != 2)flag = 1;break; default:break; } return flag ; } void EightNum::Spreadchild(int n) {//扩展 child 节点的子节点 int i,loc,qifa; for(i = 0;i < 9;i++) this->num[i] = this->parent->num[i]; for(i = 0;i < 9;i++) if(this->num[i] == 0)break; if(n==0) loc = i%3+(i/3 - 1)*3; else if(n==1) loc = i%3+(i/3 + 1)*3; else if(n==2)

loc = i%3-1+(i/3)*3; else loc = i%3+1+(i/3)*3; qifa = this->num[loc]; this->num[i] = qifa; this->num[loc] = 0;

}

void EightNum::getnum(int num1[9]){ for(int i=0;i<9;i++) num1[i]=num[i]; }

void EightNum::setnum(int num1[9]){ for(int i=0;i<9;i++) num[i]=num1[i]; }

void EightNum::show(){//输出函数 for(int i=0;i<9;i++){ cout<<num[i]<<" if((i+1)%3==0) cout<<"\n"; } cout<<"--------------------"; } ";

int EightNum::Shownum() {

if(this == NULL)return 0; else { int n = this->parent->Shownum(); this->show(); cout<<endl; return n+1; } }

int EightNum::operator ==(EightNum& NewEightN){ int compere=1; for(int i=0;i<9;i++) if(num[i]!=NewEightN.num[i]){ compere=0; break; } if(compere==0) return 0; else return 1; }

//-----------------------以下为分函数的定义---------------------//

//判断是否有解的函数 int solve(int num[9],int target[9]){ int i,j; int num_con=0,tar_con=0; for(i=0;i<9;i++) for(j=0;j<i;j++){ if(num[j]<num[i] && num[j]!=0)

num_con++; if(target[j]<target[i] && target[j]!=0) tar_con++; } num_con=num_con%2; tar_con=tar_con%2; if((num_con==0 && tar_con==0)||(num_con==1 && tar_con==1)) return 1; else return 0; } EightNum * Stack::Minf() { Stack * qifa =this->next; Stack * min = this->next; Stack * minp = this; EightNum * minx; while(qifa->next != NULL) { if((qifa->next->eightnum->get_evalfun()) < (min->eightnum->get_evalfun())) { min = qifa->next; minp = qifa; } qifa = qifa->next; } minx = min->eightnum; qifa = minp->next; minp->next = minp->next->next; free(qifa); return minx;

}

//判断节点是否属于 OPEN 表或 CLOSED 表 EightNum * Stack::Belong(EightNum * suc) { Stack * qifa = this-> next ; if(qifa == NULL)return NULL; while(qifa != NULL) { if(suc==qifa->eightnum)return qifa ->eightnum; qifa = qifa->next; } return NULL; }

//把节点存入 OPEN 或 CLOSED 表中 void Stack::Putinto(EightNum * suc) { Stack * qifa; qifa =(Stack *) malloc(sizeof(Stack)); qifa->eightnum = suc; qifa->next = this->next; this->next = qifa; }

int BelongProgram(EightNum * suc ,Stack goal,int m ) { EightNum * qifa = NULL; int flag = 0;

*Open ,Stack

*Closed ,EightNum

if((Open->Belong(suc) != NULL) || (Closed->Belong(suc) != NULL)) { if(Open->Belong(suc) != NULL) qifa = Open->Belong(suc); else qifa = Closed->Belong(suc); flag=1; } else { Open->Putinto(suc); suc->eval_func(m); } return flag; }

//扩展后继节点总函数 void Spread(EightNum * suc, Stack * Open, Stack * Closed, EightNum goal,int m) { int i; EightNum * child; for(i = 0; i < 4; i++) { if(suc->Canspread(i+1)) { space++; child = (EightNum *) malloc(sizeof(EightNum)); child->parent = suc; child->Spreadchild(i); child->eval_func(m); if(BelongProgram(child, Open, Closed, goal,m)) //判断子节点是否属于 OPEN 或 CLOSED 表 free(child);

} } }

//执行函数 EightNum * Process(EightNum * org, EightNum goal, Stack * Open, Stack * Closed,int m) { while(1) { if(Open->next == NULL)return NULL; EightNum * minf =Open->Minf(); Closed->Putinto(minf); if((*minf)==goal)return minf; Spread(minf, Open, Closed, goal,m); } }

//------------------------A*算法搜索函数----------------------// void A(int id,EightNum start,EightNum Target) { EightNum * result; space=0; float time; Stack *Open = (Stack *) malloc(sizeof(Stack)); Open->next = NULL; Stack *Closed = (Stack *) malloc(sizeof(Stack)); Closed->next = NULL; clock_t startt,finisht; startt=clock();//开始时间 start.eval_func(id);

Open->Putinto(&start); result = Process(&start, Target, Open, Closed,id); //进行剩余的操作 cout<<"\n 搜索过程:\n"<<result->Shownum()<<endl; finisht=clock(); time=(float)(finisht-startt); cout<<endl<<id<<"算法处理结果:所耗时间:"; cout<<time; cout<<"ms, "; cout<<"所耗空间:"; cout<<space; cout<<"块, "<<endl<<endl; }

//-----------------------------主函数-----------------------------// int main(void)//主函数 { int i,j; int flag; int num[9]; int error; do{ error=0; cout<<"请输入八数码问题的初始状态(0 代表空格, 棋子” “ 间用空格隔开):"<<endl; for(i=0;i<9;i++){ flag=0; cin>>num[i]; for(j=0;j<i;j++) if(num[j]==num[i]) flag=1; if(num[i]<0||num[i]>8||flag==1){ error++;

} } if(error!=0) cout<<"输入数据错误!请重新输入!"<<endl; }while(error!=0);//输入八数码问题的初始状态(0 代表空格,“棋子”间用空格隔开) ;

int error1; do{ error1=0; cout<<"请输入新的目标状态(用 0 代表空格,“棋子”间用空格隔开):"<<endl; for(i=0;i<9;i++){ flag=0; cin>>target[i]; for(j=0;j<i;j++) if(target[j]==target[i]) flag=1; if(target[i]<0||target[i]>9||flag==1){ error1++; } } if(error1!=0) cout<<"输入数据错误!请重新输入!"<<endl; }while(error1!=0);//输入八数码问题的目标状态(用 0 代表空格,中间用空格隔开) ;

EightNum start(num),Target(target);

int m=solve(num,target);//判断初始状态到目标状态是否有解, 有解返回 1, 误解返回 0; if(m==0){ cout<<"此状态无解!"<<endl;

return 0; } int id=0; while(id!=3){ cout<<"1. 错 放 的 棋 子 个 数 为 ;\n2. 每 个 棋 子 与 目 标 位 置 之 间 的 距 离 总 和 为;"<<endl; cout<<"3.结束,退出程序!"<<endl; cout<<"\n 请选择功能,分别输入“1” “3”进行选择:"<<endl; “2” cin>>id; switch(id){ case 1:{ cout<<"错放的棋子个数结果为:\n(以下逐一展示搜索过程:)"<<endl; A(1,start,Target); break;} case 2:{ cout<<"每个棋子与其目标位置之间的距离总和为:\n(以下逐一展示搜索过 程:)"<<endl; A(2,start,Target); break;}

default: break; } } cout<<"啊啊….程序结束!!"; } 实验截图

实验中遇到的问题 1:开始程序只能运行一种方式即按照错位个数搜索,后经过查找相关资料,修改后可 程序可进行选择,两种方法结合在一起根据选择运行。 实验总结 通过本次实验让我对八数码问题有了进一步的了解,也对一般图搜索和启发式搜索问 题的解决有了更深的理解,启发式函数是通过考虑搜索算法的可采纳性,根据定义的评价 函数选择最佳路径的一种方法,根据不同的函数可能得到不同的搜索路径,通过这次实验 让我对这类游戏行的程序更加有兴趣,也让我的编程更加熟练和编程的思维更清晰了点, 从而对学*编程更加有兴趣了。




友情链接: