启发式搜索算法
人工智能基础实验报告
实验名称：八数码问题
姓名：张俊
学号：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
#include
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< 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< 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 if(num[j] num_con++; if(target[j] 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 *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"< finisht=clock(); time=(float)(finisht-startt); cout< cout< cout<<"ms, "; cout<<"所耗空间:"; cout< cout<<"块, "< } //-----------------------------主函数-----------------------------// int main(void)//主函数 { int i,j; int flag; int num[9]; int error; do{ error=0; cout<<"请输入八数码问题的初始状态(0代表空格,“棋子”间用空格隔开):"< for(i=0;i<9;i++){ flag=0; cin>>num[i]; for(j=0;j if(num[j]==num[i]) flag=1; if(num[i]<0||num[i]>8||flag==1){ error++; } } if(error!=0) cout<<"输入数据错误!请重新输入!"< }while(error!=0);//输入八数码问题的初始状态(0代表空格,“棋子”间用空格隔开）； int error1; do{ error1=0; cout<<"请输入新的目标状态(用0代表空格,“棋子”间用空格隔开):"< for(i=0;i<9;i++){ flag=0; cin>>target[i]; for(j=0;j if(target[j]==target[i]) flag=1; if(target[i]<0||target[i]>9||flag==1){ error1++; } } if(error1!=0) cout<<"输入数据错误!请重新输入!"< }while(error1!=0);//输入八数码问题的目标状态(用0代表空格,中间用空格隔开）； EightNum start(num),Target(target); int m=solve(num,target);//判断初始状态到目标状态是否有解，有解返回1，误解返回0；if(m==0){ cout<<"此状态无解!"< return 0; } int id=0; while(id!=3){ cout<<"1. 错放的棋子个数为;\n2.每个棋子与目标位置之间的距离总和为;"< cout<<"3.结束，退出程序！"< cout<<"\n请选择功能,分别输入“1”“2”“3”进行选择："< cin>>id; switch(id){ case 1:{ cout<<"错放的棋子个数结果为:\n(以下逐一展示搜索过程：)"< A(1,start,Target); break;} case 2:{ cout<<"每个棋子与其目标位置之间的距离总和为:\n(以下逐一展示搜索过程：)"< A(2,start,Target); break;} default: break; } } cout<<"啊啊….程序结束!!"; } 实验截图 实验中遇到的问题 1：开始程序只能运行一种方式即按照错位个数搜索，后经过查找相关资料，修改后可程序可进行选择，两种方法结合在一起根据选择运行。 实验总结 通过本次实验让我对八数码问题有了进一步的了解，也对一般图搜索和启发式搜索问题的解决有了更深的理解，启发式函数是通过考虑搜索算法的可采纳性，根据定义的评价函数选择最佳路径的一种方法，根据不同的函数可能得到不同的搜索路径，通过这次实验让我对这类游戏行的程序更加有兴趣，也让我的编程更加熟练和编程的思维更清晰了点，从而对学习编程更加有兴趣了。 启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ，A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度，深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。 实验名称:启发式搜索算法 1、实验环境 Visual C++ 6.0 2、实验目的和要求 （复述问题）使用启发式算法求解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) 实验一启发式搜索算法 学号：2220103430 班级：计科二班 姓名：刘俊峰 一、实验内容： 使用启发式搜索算法求解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 的定义，并测试使用该估价函数是否使算法失去可采纳性。 二、实验目的： 熟练掌握启发式搜索A * 算法及其可采纳性。 三、实验原理： （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个 两点间所有路径的遍历算法 中国海洋大学信息科学与工程学院熊建设梁磊 摘要：本文首先简单介绍图的深度优先遍历算法，接着根据图的深度优先遍历算法求出连通图中两点间所有路径。 一、深度优先遍历(Depth-First Traversal) 1．图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 2、深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x 不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 二、求两点间所有路径的算法 假设简单连通图如图1所示，那么它的邻接表存储结构如图2所示。假设我们要找出结点3到结点6的所有路径，那么，我们就设结点3为起点，结点6为终点。我们需要的存储结构有：一个保存路径的栈、一个保存已标记结点的数组，那么找到结点3到结点6的所有路径步骤如下： 1、程序源代码 #include 编号 南京航空航天大学毕业论文 题目启发式搜索算法在N数码问 题中的应用 学生姓名 学号 学院 专业 班级 指导教师 二〇一三年六月 南京航空航天大学 本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：启发式搜索算法在N数码问题中的应用）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。 作者签名：年月日 （学号）： 启发式搜索算法在N数码问题中的应用 摘要 N数码问题是人工智能领域中的经典问题，N数码可以有效的判断一个搜索算法的优劣。在低阶数码问题中，使用简单的宽搜或深搜就可以解决问题，但在高阶数码中，由于其巨大的搜索规模，我们必须采用更加智能的算法才能解决问题。与传统搜索相比，启发式搜索当前搜索过程中的信息，选择最为可行的状态进行拓展，从而大大提高了搜索的质量和效率。 本文通过建立N数码问题的存储机制和移动规则，使得N数码问题转化为了一个标准的搜索问题。并着重分析了A*算法和遗传算法在N数码中的应用，在A*算法中使用了两种不同的估价函数，目的是比较不同估价函数在N数码问题中的表现。在最后，本文进行了大量实验，综合分析了A*算法和遗传算法在不同规模数据下的优劣。 关键词：启发式搜索，数码问题，A*算法，遗传算法 The Application of Heuristic Search Algorithm on N-Puzzle Problem Abstract N-puzzle problem is a classic problem in artificial intelligence. N-puzzle problem can effectively judge the merits of a search algorithm. In the low order puzzle problem, using a Depth-First-Search or Breadth-First-Search can solve the problem, but in the higher order digital, because of the huge search space area,we must adopt a more intelligent https://www.sodocs.net/doc/b95125395.html,pared with the traditional search method, heuristic search uses the information in the search process, and it will choose the most feasible state, thus greatly improves the search quality and efficiency. This paper designs the storage mechanism and movement rules of N-puzzle problem, making the N-puzzle problem transforms to a standard search problem. This paper focuses on the application of A* algorithm and genetic algorithm in N-puzzle problem, and two different evaluation function used in A* algorithm. The objective is to compare the performance of different valuation function in N digital problem. In the end, this paper carries out a large number of experiments, a comprehensive analysis of the A* algorithm and genetic algorithm in different scale of data. Key Words：Heuristic Search;N-puzzle Problem;A* algorithm; Genetic algorithm 实验报告 课程名称算法与数据结构 姓名何劼 专业计算机科学与技术 部别 指导教员 日期年月日 实验项目列表 实验报告 姓名：何劼学号：专业：计算机科学与技术部别： 实验地点：实验时间： 2012、4、17 设备编号： 同组人员：指导教员签字：成绩：教员评语： 一、实验名称 遍历算法及应用 二、实验目的 1 ．掌握二叉树的递归构造方法 2 ．掌握二叉树的递归遍历方法 3 ．掌握二叉树的递归遍历的简单应用 三、实验内容和要求 编写完成如下功能的程序。 1 ．构造二叉树（中序加后序序列造树选做） 2 ．删除树中原来所有1 度的结点 3 ．求给定的任意结点的父亲 4 ．从根到叶的一条最长路经 5 ．计算树中叶结点数（选） 6 ．判定一棵树是否是正则树（选） 7 ．按层遍历树，并输出树宽（选） 要求： 1 ．先构造出二叉树，然后输出原树的三种遍历序列。 2 ．在删除原来所有1 度的结点后，再输出新二叉树的三种遍历序列。 3 ．直接输出给定结点的父结点的值。 4 ．输出这条最长的路径。 5 ．输出树中叶结点的数目。 6 ．输出一棵树是否是正则树的判定结论。 7 ．按层遍历树，并输出树宽 四、实验环境 1．硬件环境：PC机 2．软件环境：Windows操作系统，VC++集成开发环境 五、算法设计思想 题目一—构造二叉树。 为了使得程序能够更加具有通用性，设计者在构造二叉树时编写了三种造树方式，分别是先序扩充序列造树，先序加中序序列造树以及中序加后序造树。其中前两个程序已经在课上得到了实现。中序加后序造树，主要问题就是左右子树上下标界的确定，运用图示法能够较为形象准确的解决此问题。三种序列的输出这里不加赘述。 题目二——删除树中1度结点。 采用先序遍历递归。首先判断下一结点是否为1度结点，若为1度结点并且有右儿子，返回1；若为1度结点并且有左儿子，返回2；不为1度结点返回0。再根据返回值的情况进行勾连和结点的删除。 题目三——求结点的父亲。 采用后续遍历递归。设计者配合使用了类似于“红绿灯”的found 标记值。若为0则还未发现结点；若为1则找到该结点返回上一层输出其父亲，并置found为2。 题目四——输出从根到叶的一条最长路径。 首先找到最长路径对应的叶子（先序），再求取叶子的祖先（后序）。运用order数组存储其祖先，最后从后到前输出。这样得到的路径是符 2007-05-27 晴 //采用非递归深度优先遍历算法，可以将回溯法表示为一个非递归过程 #include }; private: int Bound(int i); void Backtrack(int i); int c; //背包容量 int n; //物品数 int *w; //物品重量数组int *p; //物品价值数组int cw; //当前重量 int cp; //当前价值 int bestp; //当前最优值int *bestx; //当前最优解int *x; //当前解 }; int Knap::Bound(int i) //装满背包 if(i<=n) b+=p/w*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp 启发式搜索——初识A*算法 A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，先说说何谓启发式算法。 一、何谓启发式搜索算法 在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一个解题的过程，应用这个过程可以从求解的开始得到问题的结果。由于求解问题的过程中分支有很多，主要是求解过程中求解条件的不确定性、不完备性造成的，使得求解的路径很多，这样就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。 深度优先是按照一定的顺序，先查找完一个分支，再查找另一个分支，直至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是：他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不可预测的情况下就不可取了。他们的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中搜索时，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直至找到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。 项目名称：各种查找算法的性能测试 项目成员： 组编号： 完成时间： 目录 前言 (2) 正文 (2) 第一章简介 (2) 1.1顺序查找问题描述 (2) 1.2二分查找问题描述 (2) 第二章算法定义 (2) 2.1顺序查找算法定义 (2) 2.2二分查找算法定义 (3) 第三章测试结果（Testing Results) (5) 3.1 实验结果表 (5) 3.2 散点图记录 (5) 第四章分析和讨论 (6) 4.1顺序查找分析 (6) 4.2二分查找分析 (6) 附录：源代码（基于C语言的) (7) 声明 (13) 前言 查找问题就是在给定的集合（或者是多重集，它允许多个元素具有相同的值）中找寻一个给定的值，我们称之为查找键。 对于查找问题来说，没有一种算法在任何情况下是都是最优的。有些算法速度比其他算法快，但是需要较多的存储空间；有些算法速度非常快，但仅适用于有序数组。查找问题没有稳定性的问题，但会发生其他的问题（动态查找表）。 在数据结构课程中，我们已经学过了几种查找算法，比较有代表性的有顺序查找（蛮力查找），二分查找（采用分治技术），哈希查找（理论上来讲是最好的查找方法）。 第一章：简介（Introduction） 1.1顺序查找问题描述： 顺序查找从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。 1.2二分查找问题描述： （1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。 （2）编写程序实现：在保存于数组a[i]有序数据元素中查找数据元素k是否存在。数元素k要包含两种情况：一种是数据元素k包含在数组中；另一种是数据元素k不包含在数组中 （3）数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。（4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。 第二章：算法定义（Algorithm Specification） 2.1顺序查找 从表的一端向另一端逐个进行记录的关键字和给定值（要查找的元素）的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查找记录；反之，若直至第一个记录，其关键 启发式图搜索算法 摘要：启发式搜索策略概述和有序搜索。启发式搜索弥补盲目搜索的不足，提高搜索效率。一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。进行搜索技术一般需要某些有关具体问题领域的特性的信息。 关键词：启发式搜索；估价函数；有序搜索；A*算法； 正文： 启发式图搜索的意义因为无信息图搜索算法的效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。所以引入了启发式图搜索算法。 启发式图搜索算法就是进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。关于图搜索的启发式搜索算法就叫做启发式图搜索算法。 启发式图搜索策略：假设初始状态、算符和目标状态的定义都是完全确定的，然后决定一个搜索空间。因此，问题就在于如何有效地搜索这个给定空间。 启发信息按其用途可分为下列3种： (1) 用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。 (2) 在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。 (3) 用于决定某些应该从搜索树中抛弃或修剪的节点。 启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索(ordered search)。有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。所谓的估价函数就是为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)——表示节点n的估价函数值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 有序搜索应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索 (best-first search)，而其算法就叫做有序搜索算法或最佳优先算法。尼尔逊曾提出一个有序搜索的基本算法。估价函数f是这样确定的：一个节点的希望程序越大，其f值就越小。被选为扩展的节点，是估价函数最小的节点。选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。 有序状态空间搜索算法 (1) 把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。 (2) 如果OPEN是个空表，则失败退出，无解。 (3) 从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。 算法设计：深度优先遍历和广度优先遍历实现 深度优先遍历过程 1、图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。 注意： 以下假定遍历过程中访问顶点的操作是简单地输出顶点。 2、布尔向量visited[0．．n-1]的设置 图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。 -------------------------- 深度优先遍历(Depth-First Traversal) 1．图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 2、深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的 启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案， 以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。 二、启发式算法类型 人工智能基础实验报告 实验名称：八数码问题 姓名：张俊 学号：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 实验二：A*算法 一、实验目的 了解启发式搜索算法的基本思想，掌握A*算法的基本原理和步骤。学会对于算法的正确应用，解决实际生活中的问题。学会区分与盲目搜索算法的不同之处。 二、实验环境 PC机一台，VC++6.0 三、实验原理 A*搜索算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC （Non-Player-ControlledCharacter）的移动计算，或线上游戏的BOT（ROBOT）的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS 一样，进行启发式的搜索。 A*算法是一种启发式搜索算法，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 A*算法的公式为：f(n)=g(n)+h(n)，g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。这个公式遵循以下特性：如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法 如果h(n)<=“n到目标的实际距离”，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。 对于函数h(n)，估算距离常用的方法有： 曼哈顿距离：定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标（x1,y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：|x1 - x2| + |y1 - y2|。 重庆邮电大学 数学大类专业 2008级《数学建模与数学实验》课程设计 设计题目：图的深度优先搜索遍历算法分析及其应用设计时间：2010.9.7-----2010.9. 12 班级： 学号： 指导教师： 图的深度优先搜索遍历算法分析及其应用 摘要:文章介绍了图论，图的基本概念及其图的表示方法。详细的分析了图中以邻接表为存储结构进行的图的深度优先搜索遍历的算法，并且在VC++环境中实现其算法的过程，对运行记过做了一定量的分析，最后介绍了基于该算法的一些应用。 关键词：图；深度优先搜索；遍历；算法 图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图（Graph）是一种较线性表和树更复杂的数据结构，图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，在研究有关图的问题时，要考虑图中每个顶点的信息，访问图中的各个顶点，而访问图中各个顶点的操作过程即使图的遍历，图的遍历算法是求解图的连通性问题，拓扑排序和求关键路径等算法的基础。 1图的三元组定义 图Ｇ是一个三元组由集合V，E和关联函数组成，记为：G=（V，E，W（G））。其中V是顶点的集合，表示V（G）={V1，V2，V3，……Vn}，V（Ｇ）≠ＮＵＬＬ。Ｅ是V中的点偶对的有穷集，表示为E（G）={e1，e2，e3……em}，其中ei为 1.遍历算法（遍历二叉树6种方法） 1.1.概述 遍历算法针对二叉树而言的，主要有先序、中序、后序三种遍历顺序，三种顺序又分别有递归和常规算法，二叉树遍历的主要思想是：遍历左子树，遍历右子树，访问根节点，由这三者的遍历顺序来确定是先序、中序还是后序。下面只要求掌握递归遍历算法，常规遍历算法见附录一。 1.2.先序遍历算法 遍历顺序：访问根节点，遍历左子树，遍历右子树。代码如下： void preOrder(BinaryTreeNode bt) { if (bt == null)// 如果当前树为空，则终止递归 return; System.out.print(bt.getData());// 先访问根节点 preOrder(bt.getLeftChild());// 再遍历左子树 preOrder(bt.getRightChild());// 再遍历右子树 } 1.3.中序遍历算法 遍历顺序：遍历左子树，访问根节点，遍历右子树。代码如下： void midOrder(BinaryTreeNode bt) { if (bt == null)// 如果当前树为空，则终止递归 return; preOrder(bt.getLeftChild());// 先遍历左子树 System.out.print(bt.getData());// 再访问根节点 preOrder(bt.getRightChild());// 再遍历右子树 } 1.4.后序遍历算法 遍历顺序：遍历左子树，遍历右子树，访问根节点。代码如下： void postOrder(BinaryTreeNode bt) { if (bt == null)// 如果当前树为空，则终止递归 return; preOrder(bt.getLeftChild());// 先遍历左子树 preOrder(bt.getRightChild());// 再遍历右子树 System.out.print(bt.getData());// 再访问根节点 } 1.5.层次遍历算法 5.3 图的遍历 和树的遍历类似，在此，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历(TraversingGraph)。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 然而，图的遍历要比树的遍历复杂得多。因为图的任一顶点都可能和其余的顶点相邻接。所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该顶点上。[例如]图7.1(b)中的G2，由于图中存在回路，因此在访问了v1,v2,v3,v4之后，沿着边(v4 , v1)又可访问到v1。为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，我们可以设一个辅助数组visited[0..n-1]，它的初始值置为“假”或者零，一旦访问了顶点vi，便置visited[i]为“真”或者为被访问时的次序号。 通常有两条遍历图的路径：深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。 5.3.1 深度优先搜索 深度优先搜索(Depth-First Search)遍历类似于树的先根遍历，是树的先根遍历的推广。 其基本思想如下：假定以图中某个顶点vi为出发点，首先访问出发点，然后选择一个vi的未访问过的邻接点vj，以vj为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。显然，这是一个递归的搜索过程。 现以图5-3-1中G为例说明深度优先搜索过程。假定v0是出发点，首先访问v0。因v0有两个邻接点v1、v2均末被访问过，可以选择v1作为新的出发点，访问v1之后，再找v1的末访问过的邻接点。同v1邻接的有v0、v3和v4，其中v0已被访问过，而v3、v4尚未被访问过，可以选择v3作为新的出发点。重复上述搜索过程，继续依次访问v7、v4 。访问v4之后，由于与v4相邻的顶点均已被访问过，搜索退回到v7。由于v7、v3和v1都是没有末被访问的邻接点，所以搜索过程连续地从v7退回到v3，再退回v1，最后退回到v0。这时再选择v0的末被访问过的邻接点v2，继续往下搜索，依次访问v2、v5和v6，止此图中全部顶点均被访问过。遍历过程见图5-3-1（b），得到的顶点的访问序列为：v0 → v1 →v3 → v7 → v4 → v2 → v5 → v7。 第二章部分习题参考答案 1.证明下列结论： 1）在一个无向图中，如果每个顶点的度大于等于2，则该该图一定含有圈； 2）在一个有向图D 中，如果每个顶点的出度都大于等于1，则该图一定含有一个有向圈。 1）证明：设无向图最长的迹,10k V V V P =每个顶点度大于等于2，故存在与1V 相异的点'V 与0V 相邻，若,'P V ?则得到比P 更长的迹，与P 的取法矛盾。因此，P V ∈'，是闭迹，从而存在圈.0'10V V V V （定义：迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。） 2）证明：设有向图最长的有向迹,10k V V V P =每个顶点出度大于等于1，故存在'V 为k V 的出度连接到点，'V V k 成为一条有向边，若,'P V ?则得到比P 更长的有向迹，与P 矛盾，因此必有P V ∈'，从而该图一定含有有向圈。 2.设D 是至少有三个顶点的连通有向图。如果D 中包含有向的Euler 环游（即是通过D 中每条有向边恰好一次的闭迹），则D 中每一顶点的出度和入度相等。反之，如果D 中每一顶点的出度与入度都相等，则D 一定包含有向的Euler 环游。这两个结论是正确的吗？请说明理由。如果G 是至少有三个顶点的无向图，则G 包含Euler 环游的条件是什么？ 证明：1）若图D 中包含有向Euler 环游，下证明每个顶点的入度和出度相等。 如果该有向图含有Euler 环游，那么该环游必经过每个顶点至少一次，每经过一次，必为“进”一次接着“出”一次，从而入度等于出度。从而，对于任意顶点，不管该环游经过该顶点多少次，必有入度等于出度。 2）若图D 中每个顶点的入度和出度相等，则该图D 包含Euler 环游。证明如下。 对顶点个数进行归纳。 当顶点数|v(D)|=2时，因为每个点的入度和出度相等，易得构成有向Euler 环游。启发式搜索 八数码问题
《人工智能基础》实验报告-实验名称：启发式搜索算法
实验一 启发式搜索算法
两点间所有路径的遍历算法
启发式搜索算法解决八数码问题(C语言)
启发式搜索算法在N数码问题中的应用
遍历算法及应用
采用非递归深度优先遍历算法
启发式搜索A星算法
各种查找算法的性能分析
人工智能启发式图搜索算法
算法设计：深度优先遍历和广度优先遍历
启发式优化算法综述
(完整版)启发式搜索算法
实验二、A＊搜索算法
图的深度优先搜索遍历算法分析及其应用
Java实现遍历、排序、查找算法及简要说明
图的两种图的遍历方法
图与遍历算法 习题参考答案