《人工智能基础》实验报告-实验名称：启发式搜索算法

人工智能九宫格重移——搜索成员：赵春杰 2009210665羊森 2009210653黄鑫 2009210周成兵 2009210664王素娟 20092106441.问题描述：八数码问题也称为九宫问题。

在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。

棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

所谓问题的一个状态就是棋子在棋盘上的一种摆法。

棋子移动后，状态就会发生改变。

解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

2.九宫重移有无答案检查（逆序数）我们把每个9宫格横向展开，如第一个123456789，我们把左边数大于右边数的组数称为这个九宫格的逆序数，显然123456789的逆序数为0；考虑横向平移，那么逆序数的增量为2或0或-2；纵向平移，逆序数的增量为4或0或-4；但147258369的逆序数为奇数。

所以147258369是无解的情况。

由此也可以类推当将9宫格展开后，如果数据序列的逆序数为奇数，则此数据序列对应的九宫格是无解的。

3.BFS算法队列： Queue open = new Queue();存放待扩展的节点List： List<Bfstr> closed = new List<Bfstr>();存放已被扩展过的节点ArrayList map = new ArrayList();//存放答案HashTale： Hashtable table = new Hashtable();构造哈希表以方便查找3.1．BFS算法介绍广度优先搜索算法BFS基本思想：从图中某顶点v出发，逐层对节点进行拓展，并考察是否为目标节点，在第n层节点没有全部扩展并考察前，不对第n+1层节点进行扩展。

《人工智能》实验一题目实验一 启发式搜索算法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.数据结构与算法设计 该搜索为一个搜索树。

为了简化问题，搜索树节点设计如下：typedef struct Node//棋盘{//节点结构体int data[9];double f,g;struct Node * parent; //父节点}Node,*Lnode;int data[9]; 数码数组：记录棋局数码摆放状态。

struct Chess * Parent; 父节点：指向父亲节点。

下一步可以通过启发搜索算法构造搜索树。

1、局部搜索树样例：2、搜索过程搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。

搜索过程如下：（1）、把原棋盘压入队列；（2）、从棋盘取出一个节点；（3）、判断棋盘估价值，为零则表示搜索完成，退出搜索；（4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃；（5）、跳到步骤（2）；3、算法的评价完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。

现存在的一些优缺点。

1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。

<!--[if !supportLists]-->2、<!--[endif]-->内存泄漏。

****大学人工智能基础课程实验报告（2011-2012学年第一学期）启发式搜索王浩算法班级： *********** 学号： ********** 姓名： ****** 指导教师： ******成绩：2012年 1 月 10 日实验一 启发式搜索算法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. 实验原理使用启发式信息知道搜索过程，可以在较大的程度上提高搜索算法的时间效率和空间效率；启发式搜索的效率在于启发式函数的优劣，在启发式函数构造不好的情况下，甚至在存在解的情形下也可能导致解丢失的现象或者找不到最优解，所以构造一个优秀的启发式函数是前提条件。

4.实验内容 1.问题描述在一个3*3的九宫格 里有1至8 八个数以及一个空格随机摆放在格子中，如下图：初始状态 目标状态现需将图一转化为图二的目标状态，调整的规则为：每次只能将空格与其相邻的一个数字进行交换。

实质是要求给出一个合法的移动步骤，实现从初始状态到目标状态的转变。

2.算法分析 (1)解存在性的讨论对于任意的一个初始状态，是否有解可通过线性代数的有关理论证明。

按数组存储后，算出初始状态的逆序数和目标状态的逆序数，若两者的奇偶性一致，则表明有解。

（2）估价函数的确定通过对八数码的特性的研究，找出一个相对好的函数，f(n)=d(n)+h(n)其中h(n)=2*compare(n)+3*S(n);d(n)为已搜索的深度；（compare（n）为当前节点与目标结点相同位置不相同的个数，S(n)为当前节点的无序度。

人工智能的启发式算法
遗传算法是一种受自然选择启发的优化算法，它通过模拟生物
进化的过程，利用交叉、变异和选择等操作来搜索最优解。

模拟退
火算法则模拟金属退火的过程，通过接受较差解的概率来跳出局部
最优解，从而更有可能找到全局最优解。

蚁群算法则模拟蚂蚁寻找
食物的过程，利用信息素和启发式规则来引导搜索。

遗传规划算法
结合了遗传算法和规划方法，用于解决优化问题和规划问题。

启发式算法在解决NP难题和大规模优化问题时具有一定的优势，因为它们能够在可接受的时间内找到较好的解。

然而，启发式算法
并不保证找到最优解，而是找到一个较好的近似解。

因此，在应用
启发式算法时，需要权衡计算资源和解的质量。

除了上述提到的算法之外，还有许多其他启发式算法，它们在
不同的问题领域和应用场景中发挥着重要作用。

启发式算法的发展
也是一个活跃的研究领域，研究者们不断提出新的算法和改进现有
算法，以应对不断变化的复杂问题。

总的来说，启发式算法在人工
智能领域具有重要意义，为解决现实世界中的复杂问题提供了一种
有效的方法。

人工智能基础实验报告实验名称：八数码问题姓名：张俊学号：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：开始程序只能运行一种方式即按照错位个数搜索，后经过查找相关资料，修改后可程序可进行选择，两种方法结合在一起根据选择运行。

人工智能课内实验报告（二） ----重排九宫（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步。

实验一 启发式搜索算法姓名：徐维坚 学号：2220103484 日期：2012/6/29一、实验目的：熟练掌握启发式搜索A *算法及其可采纳性。

二、实验内容：使用启发式搜索算法求解8数码问题。

1) 编制程序实现求解8数码问题A *算法，采用估价函数()()()()w n f n d n p n ⎧⎪=+⎨⎪⎩， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。

2) 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界 的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。

三、实验原理：1. 问题描述：八数码问题也称为九宫问题。

在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。

棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

所谓问题的一个状态就是棋子在棋盘上的一种摆法。

解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

2. 原理描述：2.1 有序搜索算法：（1）原理：在搜索过程中，OPEN 表中节点按照其估价函数值以递增顺序排列，选择OPEN 表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。

在本例中，估价函数中的)(n g 取节点深度)(n d ，)(n h 为节点n 的状态与目标状态之间错放的个数，即函数)(n ω。

（2）算法描述：① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ；② 如果OPEN 是空表，则失败退出，无解；③ 从OPEN 表中选择一个f 值最小的节点i 。

如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ；④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中；⑤ 如果i 是个目标节点，则成功退出，求得一个解；⑥ 扩展节点i ，生成其全部后继节点。

实验报告姓名：***学号：**********班级：软件二班实验名称：启发式搜索课程名称：人工智能实验日期：2015.11.09实验环境：Visual C++实验目的以及内容：1、实验内容：使用启发式搜索算法求解八数码问题。

（1）编制程序实现求解八数码问题A*算法，采用估价函数其中：d(n)是搜索树中节点n的深度；w(n)为节点n的数据库中错放的棋子个数；p(n)为节点n的数据库中的每个棋子与其目标位置之间的距离的总和。

（2）分析上述（1）中的两种估价函数求解八数码问题的效率差别，给出一个是p(n)的上界的h(n)的定义，并测试使用该估价函数是否使算法失去可采纳性。

2、实验目的：熟练的掌握启发式搜索A*算法及其可采纳性。

3. 实验原理：八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。

代码：#include"stdio.h"#define num 3void show(int begin[num][num]){for(int i = 0; i < num; i++){for(int j = 0; j < num; j++)printf("%d ", begin[i][j]);printf("\n");}printf("\n");}void exchange(int begin[num][num], int row_one, int column_one, int row_two, int column_two){int temp;temp = begin[row_two][column_two] ;begin[row_two][column_two] = begin[row_one][column_one];begin[row_one][column_one] = temp;}int judge(int begin[num][num], int end[num][num]){int count=0;for(int i = 0; i < num; i++)for(int j = 0; j < num; j++){if(begin[i][j] == end[i][j] && end[i][j] != 0)count++;}return count;}int yidong(int begin[num][num], int end[num][num], int right, int jishu, int ji_shu[50][3][3], int biaoji, int row, int column){int temp_zhi;show(begin);if(jishu >= 20)return 0;int node;int temp;for(int q=0; q<jishu; q++){node = 1;for(int w=0; w<num && node; w++)for(int r=0; r<num && node; r++)if(ji_shu[q][w][r] != begin[w][r])node = 0;if(node == 1){return 0;}}for(int i = 0; i < num; i++)for(int j = 0; j < num; j++)ji_shu[jishu][i][j] = begin[i][j];if(right == num * num - 1)return 1;if(row > 0 && biaoji != 0){exchange(begin, row - 1, column, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row - 1, column, row , column);else if(temp >= right){temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 2, row-1, column);if( temp_zhi == 1)return 1;exchange(begin, row - 1, column, row , column);}}if(column > 0 && biaoji != 1){exchange(begin, row, column - 1, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row, column - 1, row , column);else if(temp >= right){temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu ,3, row, column -1);if(temp_zhi == 1)return 1;exchange(begin, row, column - 1, row , column);}}if(row < num-1 && biaoji != 2){exchange(begin, row + 1, column, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row + 1, column, row , column);else if(temp >= right){temp_zhi =yidong(begin, end, temp, jishu+1, ji_shu, 0, row+1, column);if(temp_zhi == 1)return 1;exchange(begin, row + 1, column, row , column);}}if(column < num-1 && biaoji != 3){exchange(begin, row, column + 1, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row, column + 1, row , column);else if(temp >= right){temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 1, row, column+1);if(temp_zhi == 1)return 1;exchange(begin, row, column + 1, row , column);}}return 0;}void shuru(int begin[][num],int blank[]){int temp, node, zero = 0;for (int i = 0; i < num; i++)for(int j = 0; j < num; j++){node = 1;printf("请输入第%d行，第%d列的元素的值：", i+1, j+1);scanf("%d", &temp);for (int q = 0; q <= i && node == 1; q++)for (int w = 0; w < j; w++)if(temp == begin[q][w]){printf("输入重复，请重新输入\n");node = 0;j--;break;}if(temp < 0 || temp > num*num-1){printf("请输入从%d到%d的数\n", zero, num*num-1);node = 0;j--;}if(node == 1){if(temp == 0){blank[0] = i;blank[1] = j;}begin[i][j] = temp;}}}int main(){int jishu = 0, ji_shu[50][3][3];int row;int column;int begin[num][num], blank[2],count=1;int end[num][num] = {1, 2, 3, 8, 0, 4, 7, 6, 5};printf ("-------8数码游戏开始！--------\n");shuru(begin, blank);row = blank[0];column = blank[1];if(yidong (begin, end,judge(begin,end),jishu,ji_shu,4,row,column) == 0)printf("\n此8数码的问题可能无解！");elseshow(begin);getchar();getchar();return 0;}实验截图：实验总结：1、A*搜索算法：取g(n)=d(n)，h(n)=w(n)，其中w(n)表示以目标为基准，结点n的状态中每一个数码牌与其目标位置之间的距离（不考虑夹在其间的数码牌）的总和，由于从结点n转换成目标结点至少需要w(n)步，所以对任意n，恒有w(n) ≤h*(n)。

启发式搜索实验报告2015-2016第1学期《人工智能基础》实验报告实验名称:启发式搜索算法专业班级学号姓名1、实验环境Visual C++ 6.02、实验目的和要求(复述问题)使用启发式算法求解8数码问题(1) 编制程序实现求解8数码问题A*算法，采用估价函数f(n)=d(n)+p(n)其中:d(n)是搜索树中结点n的深度;w(n)为节点n的数据库中错放的旗子个数;p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。

(2) 分析上述(1)中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界h(n)的定义，并测试该估价函数是否使算法失去可采纳性。

实验目的:熟练掌握启发式搜索A*算法及其可采纳性。

3、解题思路、代码3.1解题思路八数码问题的求解算法(1) 盲目搜索宽度优先搜索算法、深度优先搜索算法(2) 启发式搜索启发式搜索算法的基本思想是:定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。

先定义下面几个函数的含义:f*(n)=g*(n)+h*(n) (1)式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值;h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。

评价函数的形式可定义如(2)式所示:f(n)=g(n)+h(n) (2)其中n是被评价的当前节点。

f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。

利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。

在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。

采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下:F(n)=d(n)+p(n) (4)1 / 112015-2016第1学期《人工智能基础》实验报告其中A*算法中的g(n)根据具体情况设计为d(n)，意为n节点的深度，而h(n)设计为p(n)，意为放错的数码与正确的位置距离之和。

人工智能实验报告实验一在搜索策略实验群实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。

搜索图算法比较广度优先深度优先A*Open表节点G，节点10节点G，节点6节点3，节点9，节点G，节点10，节点8Close表节点s，节点1，节点2，节点3，节点4，节点5，节点6，节点7，节点8，节点9节点s,节点1，节点3，节点7，节点4，节点8，节点2，节点5，节点9节点s，节点2，节点1，节点5，节点6，节点4估价函数无无搜索节点次序记录节点s，节点1，节点2，节点3，节点4，节点5，节点6，节点7，节点8，节点9,节点G节点s,节点1，节点3，节点7，节点4，节点8，节点2，节点5，节点9，节点G节点s，节点2，节点1，节点5，节点6，节点4，节点G观测结果经过11步搜索得到目标节点经过10步搜索得到目标节点经过7步搜索得到目标节点学生结论宽度优先搜索能保证在搜索树中找到一条通向目标节点的最短路径，但由于盲目性大所以当搜索数据比较多的时候该方法较为费时。

深度优先搜索要沿路径一条一条的走到底，如果目标在前几条路径中那么该搜索会较为快捷，在本搜索树中虽然比宽度优先少一步，但是若第一条路径或者某几条路径很深，则该搜索会相当耗时且不能保证成功。

A*算法是启发式算法的一种能通过路径的权值找出代价最为小的一条，所以很具优越性，但是算法本身计算较为复杂，要考虑以前的和将来两方面的代价，进行估算，所以没有前两种方法简单。

实验二：产生式系统实验实验目的熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。

推理方法□ 正向推理 □ 反向推理建立规则库 建立事实库该动物是哺乳动物 <- 该动物有毛发.该动物是哺乳动物 <- 该动物有奶.该动物是鸟 <- 该动物有羽毛.该动物是鸟 <- 该动物会飞&会下蛋.该动物是食肉动物 <- 该动物吃肉.该动物是食肉动物 <- 该动物有犬齿&有爪&眼盯前方.该动物是有蹄类动物 <- 该动物是哺乳动物&有蹄.该动物是有蹄类动物 <- 该动物是哺乳动物& 是嚼反刍动物.该动物是金钱豹 <- 该动物是哺乳动物&是食肉动物&是黄褐色&身上有暗斑点.该动物是虎 <- 该动物是哺乳动物&是食肉动物&是黄褐色&身上有黑色条纹.该动物是长颈鹿 <- 该动物是有蹄类动物&有长脖子&有长腿&身上有暗斑点.该动物是斑马 <- 该动物是有蹄类动物&身上有黑色条纹.该动物是鸵鸟 <- 该动物是鸟&有长脖子&有长腿&不会飞&有黑白二色.该动物是企鹅 <- 该动物是鸟&会游泳&不会飞&有黑白二色.该动物是信天翁 <- 该动物是鸟&善飞.%------动物识别系统事实集： %--该动物是企鹅 会游泳.不会飞.有黑白二色.%该动物是鸟.%-------- %--该动物是鸟该动物会飞.会下蛋.%----该动物是金钱豹 <- 该动物是哺乳动物&是食肉动物&是黄褐色&身上有暗斑点.该动物有毛发.%是食肉动物.是黄褐色.身上有暗斑点.该动物吃肉.%----该动物是虎 <- 该动物是哺乳动物&是食肉动物&是黄褐色&身上有黑色条纹.该动物是哺乳动物.%是食肉动物.是黄褐色.身上有黑色条纹.%----该动物是长颈鹿 <- 该动物是有蹄类动物&有长脖子&有长腿&身上有暗斑点.%该动物是有蹄类动物.有长脖子.有长腿.身上有暗斑点.%----该动物是有蹄类动物 <- 该动物是哺乳动物&有蹄. %有蹄.预测结果 在相关询问：该动物是哺乳动物？ 该动物是鸟？ 该动物是食肉动物？ 该动物是金钱豹？该动物是鸵鸟？该动物是企鹅？时为真，其余为假。

人工智能概论大作业学院：电子工程学院专业：智能科学与技术题目一：搜索算法编程及实验报告一．算法题目八数码难题的求解。

二．实验目的从盲目搜索和启发式搜索方法中分别选择一种解决八数码难题，给出搜索树和从起始节点到目标节点的路径。

三．实验设备及软件环境Win7的笔记本电脑，VS2013（使用c语言编程）。

四．实验方法1.盲目搜索——宽度优先搜索。

（1）.算法描述如果搜索是以接近其实节点的程度来依次扩展节点，那么这中搜索就叫宽度优先搜索。

这种搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

(1）把起始节点放到OPEN表中（如果该起始节点为一目标节点，则求得一个解答）。

（2）如果OPEN是个空表，则没有解，失败退出；否则继续。

（3）把第一个节点（节点 n）从OPEN表移出，并把它放入CLOSED扩展节点表中。

（4）扩展节点n。

如果没有后继节点，则转向上述第（2）步。

（5）把n 的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。

（6）如果n 的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第（2）步。

（2）.算法流程图（3）.程序代码#include "stdio.h"#include "conio.h"#include "string.h" struct pic{char data[10];char imoperate;int father;char extend; };char end[10] = "1238 4765";int result[100];int n;int m;pic base[100];char *w;int find(int x){for (int i = 0; i < 10; i++)if (base[x].data[i] != end[i])return 0;return 1;}void showline(int x){int i = 0;while (base[x].father != -1){result[i] = x;x = base[x].father;i++;}result[i] = 0;result[i + 1] = '\0';m = i;printf("\n搜索路径");for (i = m; i >= 0; i--){printf("\n\n\n");printf("%c\t%c\t%c\n", base[result[i]].data[0], base[result[i]].data[1], base[result[i]].data[2]);printf("%c\t%c\t%c\n", base[result[i]].data[3], base[result[i]].data[4], base[result[i]].data[5]);printf("%c\t%c\t%c", base[result[i]].data[6], base[result[i]].data[7], base[result[i]].data[8]);}}int left(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] == ' ')break;if (i == 0 || i == 3 || i == 6)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i] = base[x].data[i - 1];base[n].father = x;base[n].imoperate = 'R';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}int right(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] == ' ')break;if (i == 2 || i == 5 || i == 8)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i + 1] = base[x].data[i];base[n].father = x;base[n].imoperate = 'L';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}int up(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] == ' ')break;if (i == 0 || i == 1 || i == 2)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i - 3] = base[x].data[i];base[n].data[i] = base[x].data[i - 3];base[n].father = x;base[n].imoperate = 'D';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}int down(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] ==' ')break;if (i == 6 || i == 7 || i == 8)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i + 3] = base[x].data[i];base[n].data[i] = base[x].data[i + 3];base[n].father = x;base[n].imoperate = 'U';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}void main(){void showtree(int x);n = 1;int i;strcpy_s(base[0].data, "2831 4765");base[0].imoperate = 'N';base[0].father = -1;base[0].extend = 'Y';for ( i = 0; i < 100; i++){if (base[i].extend == 'Y'){if (base[i].imoperate == 'L'){if (right(i) == 1)break;if (up(i) == 1)break;if (down(i) == 1)break;continue;}if (base[i].imoperate == 'R') {if (left(i) == 1)break;if (up(i) == 1)break;if (down(i) == 1)break;continue;}if (base[i].imoperate == 'U') {if (left(i) == 1)break;if (right(i) == 1)break;if (down(i) == 1)break;continue;}if (base[i].imoperate == 'D') {if (right(i) == 1)break;if (up(i) == 1)break;if (left(i) == 1)break;continue;}if (base[i].imoperate == 'N') {if (left(i) == 1)break;if (right(i) == 1)break;if (up(i) == 1)break;if (down(i) == 1)break;continue;}}}printf("搜索结束\n");showline(n - 1);showtree(n - 1);getchar();}void showtree(int x){printf("\n\n\n搜索树\n\n\n");int i;for (i = 0; i <= x; i++){if (i == 0){printf("\t\t\t %c%c%c\n", base[i].data[0], base[i].data[1], base[i].data[2]);printf("\t\t\t %c%c%c\n", base[i].data[3], base[i].data[4], base[i].data[5]);base[i].data[7], base[i].data[8]);printf("\t\t\t |\n");printf(" ");for (int j = 0; j < 49; j++)printf("-");printf("\n");printf(" |");printf(" |");printf(" |");printf(" |\n");continue;}if (i>0 && i <= 4){printf(" %c%c%c", base[i].data[0],base[i].data[1], base[i].data[2]);printf("\t %c%c%c", base[i+1].data[0], base[i+1].data[1], base[i+1].data[2]);printf("\t %c%c%c", base[i+2].data[0], base[i+2].data[1], base[i+2].data[2]);printf("\t %c%c%c\n", base[i+3].data[0], base[i+3].data[1], base[i+3].data[2]);printf(" %c%c%c", base[i].data[3],base[i].data[4], base[i].data[5]);base[i+1].data[4], base[i+1].data[5]);printf("\t %c%c%c", base[i+2].data[3], base[i+2].data[4], base[i+2].data[5]);printf("\t %c%c%c\n", base[i+3].data[3], base[i+3].data[4], base[i+3].data[5]);printf(" %c%c%c", base[i].data[6],base[i].data[7], base[i].data[8]);printf("\t %c%c%c", base[i+1].data[6], base[i+1].data[7], base[i+1].data[8]);printf("\t %c%c%c", base[i+2].data[6], base[i+2].data[7], base[i+2].data[8]);printf("\t %c%c%c\n", base[i+3].data[6], base[i+3].data[7], base[i+3].data[8]);printf(" |");printf(" |");printf(" |");printf(" |\n");printf(" ---------");printf(" ---------");printf(" ---------");printf(" ---------\n");printf(" | |");printf(" | |");printf(" | |");printf(" | |\n");i = 4;continue;}if (i > 4 && i <= 12){printf(" %c%c%c", base[i].data[0], base[i].data[1], base[i].data[2]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i+j].data[0],base[i+j].data[1], base[i+j].data[2]);printf("\n %c%c%c", base[i].data[3],base[i].data[4], base[i].data[5]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[3], base[i + j].data[4], base[i + j].data[5]);printf("\n %c%c%c", base[i].data[6],base[i].data[7], base[i].data[8]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[6], base[i + j].data[7], base[i + j].data[8]);printf("\n | |");printf(" | |");printf(" | |");printf(" | |\n");i = 12;continue;}if (i > 12 && i <= 20){printf(" %c%c%c", base[i].data[0], base[i].data[1], base[i].data[2]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[0], base[i + j].data[1], base[i + j].data[2]);printf("\n %c%c%c", base[i].data[3],base[i].data[4], base[i].data[5]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[3], base[i + j].data[4], base[i + j].data[5]);printf("\n %c%c%c", base[i].data[6],base[i].data[7], base[i].data[8]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[6], base[i + j].data[7], base[i + j].data[8]);printf("\n | |");printf(" | |");printf(" | |");printf(" | |\n");printf(" -----");for (int j = 0; j < 7;j++)printf(" -----");printf("\n | |");for (int j = 0; j < 7; j++)printf(" | |");i = 20;continue;}if (i>20 && i <= 36){printf("\n%c%c%c", base[i].data[0], base[i].data[1], base[i].data[2]);for (int j = 1; j < 11; j++)printf(" %c%c%c", base[i + j].data[0], base[i + j].data[1], base[i + j].data[2]);printf("\n%c%c%c", base[i].data[3], base[i].data[4], base[i].data[5]);for (int j = 1; j < 11; j++)printf(" %c%c%c", base[i + j].data[3], base[i + j].data[4], base[i + j].data[5]);printf("\n%c%c%c", base[i].data[6], base[i].data[7], base[i].data[8]);for (int j = 1; j < 11; j++)printf(" %c%c%c", base[i + j].data[6], base[i + j].data[7], base[i + j].data[8]);i = 36;continue;}}}2.启发式搜索——有序搜索（1）算法描述有序搜索又称最好优先搜索，他总是选择最有希望的节点作为下一个要扩展的节点。

《人工智能导论》上机实验八数码问题求解专业班级：姓名：学号：指导教师：基于人工智能的状态空间搜索策略研究——八数码问题求解一、实验软件VC6.0编程语言或其它编程语言二、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。

三、需要的预备知识1. 熟悉VC6.0 编程语言；2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法；3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用；4. 熟悉计算机常用人机接口设计。

四、实验数据及步骤1. 实验内容八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

例如：2 5 4 1 2 33 7 8 41 8 6 7 6 5(a) 初始状态 (b) 目标状态图1 八数码问题示意图请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（A 算法或A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。

2. 实验步骤（1）分析算法基本原理和基本流程；（2）确定对问题描述的基本数据结构，如Open表和Closed表等；（3）编写算符运算、目标比较等函数；（4）编写输入、输出接口；（5）全部模块联调；（6）撰写实验报告。

五、实验报告要求所撰写的实验报告必须包含以下内容：1. 算法基本原理和流程框图；2. 基本数据结构分析和实现；3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等；4. 程序运行结果，含使用的搜索算法及搜索路径等；5. 实验结果分析；6. 结论；7. 提供全部源程序及软件的可执行程序。

六、操作实现该设计采用启发式搜索方法编写程序。

实验报告课程名称人工智能应用技术实验项目启发式搜索程序设计实验仪器Windows/VisualStudio学院信息管理学院专业信息安全班级/学号信安1401/学生姓名Cony实验日期2016-5-17成绩指导教师赵刚北京信息科技大学信息管理学院（课程上机）实验报告5.实验过程：#include<stdio.h>#include<malloc.h>#include<assert.h>//#include "rand.h"#include<stdlib.h>#include<time.h>#define RANDINIT() srand(time(NULL))#define RANDOM() ((float)rand() / (float)RAND_MAX)#define RANDMAX(x) (int)((float)(x)*rand()/(RAND_MAX+1.0))#define MAX_BOARD9#define ALPHA(double)1.0 /* Depth Bias */#define BETA(double)2.0 /* Misplaced Tile Bias */#define MAX_DEPTH26struct board_s;typedef struct board_s {struct board_s *pred;double f;double g;double h;char array[MAX_BOARD];char blank;char depth;} board_t;/* Node Functions */board_t *nodeAlloc( void ){board_t *board_p;board_p = (board_t *)malloc( sizeof(board_t) );assert(board_p);board_p->pred = NULL;board_p->f = board_p->g = board_p->h = (double)0.0;return board_p;}void nodeFree( board_t *board_p ){assert(board_p);free(board_p);return;}/* List Functions */#define MAX_LIST_ELEMENTS100000typedef struct {int numElements;board_t *elements[MAX_LIST_ELEMENTS];} list_t;#define listCount(x) ((x)->numElements)list_t openList_p;list_t closedList_p;void initList( list_t *list_p ){int i;assert(list_p);list_p->numElements = 0;for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) { list_p->elements[i] = (board_t *)0;}return;}int onList( list_t *list_p, char *board_p, int *pos ) {int i, j;assert(list_p); assert(board_p);for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) {if (list_p->elements[i] != (board_t *)0) {for (j = 0 ; j < MAX_BOARD ; j++) {if (list_p->elements[i]->array[j] != board_p[j]) break; }if (j == MAX_BOARD) {if (pos) *pos = i;return 1;}}}return 0;}board_t *getListBest( list_t *list_p ){int i, first=1;int best=-1;double best_f;board_t *board_p;for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) {if (list_p->elements[i]) {if (first) {best = i;best_f = list_p->elements[best]->f;first = 0;} else {if (list_p->elements[i]->f < best_f) {best = i;best_f = list_p->elements[best]->f;}}}}assert( best != -1 );board_p = list_p->elements[best];list_p->elements[best] = (board_t *)0;list_p->numElements--;return board_p;}board_t *getList( list_t *list_p, char *board_p ) {int pos, ret;board_t *retboard_p = (board_t *)0;assert(list_p); assert(board_p);ret = onList( list_p, board_p, &pos );if (ret) {retboard_p = list_p->elements[pos];list_p->elements[pos] = (board_t *)0;list_p->numElements--;}return retboard_p;}void putList( list_t *list_p, board_t *board_p ) {int i;assert(list_p); assert(board_p);for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) {if (list_p->elements[i] == (board_t *)0) {list_p->elements[i] = board_p;list_p->numElements++;return;}}assert(0);}void cleanupList( list_t *list_p ){int i;assert(list_p);for (i = 0 ; i < MAX_LIST_ELEMENTS ; i++) {if (list_p->elements[i] != (board_t *)0) {nodeFree(list_p->elements[i]);list_p->numElements--;}}return;}double evaluateBoard( board_t *board_p ){int i;const int test[MAX_BOARD-1]={1, 2, 3, 4, 5, 6, 7, 8 };int score=0;for (i = 0 ; i < MAX_BOARD-1 ; i++) {score += (board_p->array[i] != test[i]); }return (double)score;}int countInversions( char *array ){int i, j, inversions = 0;for (j = 0 ; j < MAX_BOARD-1 ; j++) {for (i = j+1 ; i < MAX_BOARD ; i++) {if (array[j] > array[i]) inversions++;}}return inversions;}board_t *initPuzzle( void ){int i, inversions;board_t *board_p;board_p = nodeAlloc();for (i = 0 ; i < MAX_BOARD-1 ; i++) {board_p->array[i] = i+1;}board_p->array[i] = 0;do {/* Randomize the board */for (i = 0 ; i < MAX_BOARD ; i++) {int x = RANDMAX(MAX_BOARD);int y = RANDMAX(MAX_BOARD);int temp = board_p->array[x];board_p->array[x] = board_p->array[y];board_p->array[y] = temp;}inversions = countInversions( board_p->array ); } while (inversions & 1);/* Find the blank space (we need to track it) */for (i = 0 ; i < MAX_BOARD ; i++) {if (board_p->array[i] == 0) {board_p->blank = i;break;}}board_p->f = board_p->h = evaluateBoard( board_p );/* Depth is zero -- top of the tree */board_p->depth = 0;return board_p;}void emitPuzzleBoard( board_t *board ){int i;assert(board);for (i = 0 ; i < MAX_BOARD ; i++) {if ((i%3) == 0) printf("\n");if (board->array[i] == 0) printf(" ");else printf("%c", 'A'+board->array[i]-1);}printf("\n");return;}#define MAX_VECTOR 4typedef struct {unsigned int len;unsigned int vector[MAX_VECTOR];} move_t;const move_t moves[MAX_BOARD] = {/* 0 */ { 2, {1, 3} },/* 1 */ { 3, {0, 2, 4} },/* 2 */ { 2, {1, 5} },/* 3 */ { 3, {0, 4, 6} },/* 4 */ { 4, {1, 3, 5, 7} },/* 5 */ { 3, {2, 4, 8} },/* 6 */ { 2, {3, 7} },/* 7 */ { 3, {4, 6, 8} },/* 8 */ { 2, {5, 7} } };board_t *getChildBoard( board_t *board_p, int index ){board_t *child_p = (board_t *)0;int blankSpot;int i;blankSpot = board_p->blank;if (index < moves[blankSpot].len) {int moveFrom;child_p = nodeAlloc();/* Copy board from parent to child */for (i = 0 ; i < MAX_BOARD ; i++) {child_p->array[i] = board_p->array[i];}child_p->blank = board_p->blank;moveFrom = moves[blankSpot].vector[index];child_p->array[ (int)child_p->blank ] = child_p->array[ moveFrom ];child_p->array[ moveFrom ] = 0;child_p->blank = moveFrom;}return child_p;}void showSolution( board_t *goal ){board_t *revList[MAX_LIST_ELEMENTS];int i = 0, j;printf("Solution:\n");while (goal) {revList[i++] = goal;goal = goal->pred;}for (j = i-1 ; j >= 0 ; j--) {emitPuzzleBoard( revList[j] );printf("\n");}return;}void astar( void ){board_t *cur_board_p, *child_p, *temp;int i;/* While items are on the open list */while ( listCount(&openList_p) ) {/* Get the current best board on the open list */ cur_board_p = getListBest( &openList_p );putList( &closedList_p, cur_board_p );/* Do we have a solution? */if (cur_board_p->h == (double)0.0) {showSolution( cur_board_p );return;} else {/* Heuristic - average number of steps is 22 for a 3x3, so don't go * too deep.*/if (cur_board_p->depth > MAX_DEPTH) continue;/* Enumerate adjacent states */for (i = 0 ; i < 4 ; i++) {child_p = getChildBoard( cur_board_p, i );if (child_p != (board_t *)0) {if ( onList(&closedList_p, child_p->array, NULL) ) {nodeFree( child_p );continue;}child_p->depth = cur_board_p->depth + 1;child_p->h = evaluateBoard( child_p );child_p->g = (double)child_p->depth;child_p->f = (child_p->g * ALPHA) + (child_p->h * BETA);/* New child board on the open list? */if ( onList(&openList_p, child_p->array, NULL) ) {assert( !onList(&closedList_p, child_p->array, NULL) );temp = getList(&openList_p, child_p->array);if (temp->g < child_p->g) {nodeFree(child_p);putList(&openList_p, temp);continue;}nodeFree( temp );} else {/* Child board either doesn't exist, or is better than a * previous board. Hook it to the parent and place on the * open list.*/child_p->pred = cur_board_p;putList( &openList_p, child_p );}}}}}return;}int main(){board_t *initial_p;RANDINIT();initList( &openList_p );initList( &closedList_p );initial_p = initPuzzle();putList( &openList_p, initial_p );astar();1.实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好，然后作为实验报告模版供学生使用；2.实验准备由学生在实验或上机之前填写，教师应该在实验前检查；3.实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；4.实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等；5.源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页。

****大学人工智能基础课程实验报告（2011-2012学年第一学期）启发式搜索王浩算法班级： *********** 学号： ********** 姓名： ****** 指导教师： ******成绩：2012年 1 月 10 日实验一 启发式搜索算法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. 实验原理使用启发式信息知道搜索过程，可以在较大的程度上提高搜索算法的时间效率和空间效率；启发式搜索的效率在于启发式函数的优劣，在启发式函数构造不好的情况下，甚至在存在解的情形下也可能导致解丢失的现象或者找不到最优解，所以构造一个优秀的启发式函数是前提条件。

4.实验内容1.问题描述在一个3*3的九宫格 里有1至8 八个数以及一个空格随机摆放在格子中，如下图：初始状态 目标状态现需将图一转化为图二的目标状态，调整的规则为：每次只能将空格与其相邻的一个数字进行交换。

实质是要求给出一个合法的移动步骤，实现从初始状态到目标状态的转变。

2.算法分析(1)解存在性的讨论对于任意的一个初始状态，是否有解可通过线性代数的有关理论证明。

按数组存储后，算出初始状态的逆序数和目标状态的逆序数，若两者的奇偶性一致，则表明有解。

（2）估价函数的确定通过对八数码的特性的研究，找出一个相对好的函数，f(n)=d(n)+h(n)其中h(n)=2*compare(n)+3*S(n);d(n)为已搜索的深度；（compare（n）为当前节点与目标结点相同位置不相同的个数，S(n)为当前节点的无序度。

1
3实验三 启发式搜索
内容：
1 以8数码或15数码为例，实现其A 算法求解程序。

2 写出实验报告：包括做实验的目的、方法、过程等；分析估价函数对搜索算法的影响，画出A 算法流程图，根据A 算法分析启发式搜索的特点。

（一）实验名称：
启发式搜索
（二）目的：
熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A 算法求解N 数码难题，理解求解流程和搜索顺序。

（三）原理：
A 算法是一种有序搜索算法，其特点在于对估价函数的定义上。

对于一般的有序搜索，总是选择f 值最小的节点作为扩展节点。

因此，f 是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n 的估价函数值为两个分量：从起始节点到节点n 的代价以及从节点n 到达目标节点的代价。

（四）步骤：
（五）实验结果与分析：
八数码问题
估价函数为：f (n ) = g (n ) + h (n
)
其中: g(n)：节点n的深度
h(n)：节点n中错放的棋子个数
相同值时，后扩展的节点放在前面；带圆圈的数字表示估价函数的值不带圆圈的数字表示扩展顺序。

2。

人工智能实验报告人工智能课内实验报告主观贝叶斯方法的研究一、实验题目主观Bayes方法的研究。

二、实验目的在证据不确定的情况下，根据充分性量度LS、必要性量度LN、E的先验概率P(E)和H 的先验概率P(H)作为前提条件，分析P(H/S)和P(E/S)的关系。

三、实验原理1、证据不确定性的表示1. 在主观Bayes方法中，证据的不确定性用概率表示。

对于证据E，由用户根据观察S给出P(E|S)，即动态强度。

用P(E|S)描述证据的不确定性（证据E 不是可以直接观测的）。

2. 证据肯定存在时，P(E|S)=1；3. 证据肯定不存在时， P(E|S)=0；4. 证据具有不确定性时， 01．当证据E愈是支持H为真时，则应是使相应的LS值愈大。

若证据E 对H愈是必要，则相应LN的值愈小。

2. 不能出现LS>1且LN>1的取值因为： LS>1：表明证据E是对H有利的证据。

LN>1：表明证据?E是对H有利的证据。

3. 不能出现LS<1且LN<1的取值因为：LS<1: 表明证据 E是对H不利的证据。

LN<1：表明证据?E是对H不利的证据。

4. 一般情况下，取LS>1， LN<1。

3、证据不确定的情况在现实中，证据肯定存在和肯定不存在的极端情况是不多的，更多的是介于二者之间的不确定情况。

对初始证据来说，由于用户对客观事物或现象的观察不是很精确，因而所提供的证据是不确定的；另外，一条知识的证据往往来源于另一条知识推出的结论，一般也具有某种程度的不确定性。

所以我们要在S对E的观察的先验概率0进一步讨论：P(H/S)?P(H/E)*P(E/S)?P(H/?E)*P(?E/S)分四种情况讨论这个公式： 1. P(E/S)=1当P(E/S)=1时，P(-E/S)=0。

此时公式变成(肯定存在的情况)：P(H/S)?P(H/E)?LS*P(H)(LS?1)*P(H)?12. P(E/S)=0当P(E/S)=0时，P(-E/S)=1.此时公式变成(肯定不存在的情况)：P(H/S)?P(H/?E)?LN*P(H)(LN?1)*P(H)?13. P(E/S)=P(E) 当P(E/S)=P(E)时，表示E与S无关。