下载文档原格式
《人工智能》实验大作业实验题目：启发式搜索一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A算法求解九宫问题，理解求解流程和搜索顺序。
二、实验方法：1.先熟悉启发式搜索算法；2.用C、C++或JA V A 语言编程实现实验内容。
三、实验背景知识：1.估价函数在对问题的状态空间进行搜索时，为提高搜索效率需要和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。
这些控制信息反映在估价函数中。
估价函数的任务就是估计待搜索节点的重要程度，给这些节点排定次序。
估价函数可以是任意一种函数，如有的定义它是节点x处于最佳路径的概率上，或是x节点和目标节点之间的距离等等。
在此，我们把估价函数f(n)定义为从初始节点经过n节点到达目标节点的最小代价路径的代价估计值，它的一般形式是：f(n) = g(n) + h(n)其中g(n)是从初始节点到节点n的实际代价，g(n)可以根据生成的搜索树实际计算出来；h(n)是从n到目标节点的最佳路径的代价估计，h(n)主要体现了搜索的启发信息。
2. 启发式搜索过程的特性（1）可采纳性当一个搜索算法在最短路径存在的时候能保证能找到它，我们就称该算法是可采纳的。
所有A*算法都是可采纳的。
（2）单调性一个启发函数h是单调的，如果a）对所有的状态n i和n j，其中n j是n i的子孙，h(n i )- h(n j )≤cost(n i,n j ),其中cost(n i,n j )是从n i到n j 实际代价。
b）目标状态的启发函数值为0，即h(Goal)=0.具有单调性的启发式搜索算法在对状态进行扩展时能保证所有被扩展的状态的f值是单调递增（不减）。
（3）信息性比较两个启发策略h1和h2，如果对搜索空间中的任何一个状态n都有h1(n) ≤h2(n)，就说h2比h1具有更多的信息性。
一般而言，若搜索策略h2比h1有更多的信息性，则h2比h1考察的状态要少。
但必须注意的是更多信息性需要更多的计算时间，从而有可能抵消减少搜索空间所带来的益处。
人工智能基础实验报告实验名称：八数码问题姓名：张俊学号：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;elseloc = 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;elsereturn 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 *Open ,Stack *Closed ,EightNum goal,int m ){EightNum * qifa = NULL;int flag = 0;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”“2”“3”进行选择："<<endl;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：开始程序只能运行一种方式即按照错位个数搜索，后经过查找相关资料，修改后可程序可进行选择，两种方法结合在一起根据选择运行。
