重庆交通大学计算机与信息学院验证性实验报告
班级：计软专业 13 级 1 班
学号： 631306050123
姓名：黄嘉城
实验项目名称：谓词演算
实验项目性质：验证性实验
实验所属课程：人工智能
实验室(中心)：软件中心实验室（语音楼8楼）指导教师：朱振国
实验完成时间： 2016 年 6 月 10 日
一、实验目的
理解和掌握谓词演算
二、实验内容及要求
在一个空房间中，机器人将A桌子上的盒子搬移到B桌子上，用选定的编程语言编写程序，演示谓词演算过程。
三、实验设备及软件
visual studio
四、设计方案
㈠题目
机器人搬盒子
㈡设计的主要思路
设在房内c处有一个机器人，在a及b处各有一张桌子，
a桌上有一个盒子。为了让机器人从c处出发把盒子从a处
拿到b处的桌上，然后再回到c处，需要制订相应的行动规划。
现在用一阶谓词逻辑来描述机器人的行动过程。
㈢主要功能
实现机器人搬盒子移动
五、主要代码
#include "stdio.h"
//定义初始状态
char state[10][20]={"AT(robot,c)","EMPTY(robot)",
"ON(box,a)","TABLE(a)","TABLE(b)"};
//定义目标状态
char end_state[5][20]={"AT(robot,c)","EMPTY(robot)", "ON(box,b)","TABLE(a)","TABLE(b)"};
int state_num=5;
int number;//记录某字符串在总数据库中的位置
bool IsInState(char *S1) /*判断字符串（状态）是否在总数据库中*/ {
int i,j;
bool flag;
//printf("S1:%s\n state[0]: %s state[1]: %s\n",S1,state[0],state[1]);
//printf("%d\n",state_num);
for(i=0;i { j=0; flag=true; while(S1[j]!='\0') { if(S1[j]!=state[i][j]) { flag=false; break; } j++; } if(flag && state[i][j]=='\0') { //printf("%d\n",i); number=i; return true; } } return false; } void Delete(int k)/*删除总数据库中的第k个状态（字符串）*/ { if(k>=state_num) { printf("The appointed state is not in the state set!"); return; } int i,j; for(i=k;i { for(j=0;*(state[i+1]+j)!='\0';j++) state[i][j]=state[i+1][j]; state[i][j]='\0'; } state_num--; } void Insert(char *S)/*将状态（字符串S）插入到总数据库中*/ { if(state_num>=10) { printf("The state space is overwrited!"); return; } int j; for(j=0;S[j]!='\0';j++) state[state_num][j]=S[j]; state[state_num][j]='\0'; state_num++; } bool GoTo(char x,char y) { char S1[20]="AT(robot,x)",S2[20]="AT(robot,x)"; //printf("%s,%s\n",S1,S2); S1[9]=x; S2[9]=y; //printf("%s,%s\n",S1,S2); if(IsInState(S1)) { Delete(number); Insert(S2); return true; } else { printf("Cannot go from %c to %c\n",x,y); return false; } } bool PickUp(char x) { char S[5][20]={"ON(box,x)","TABLE(x)","AT(robot,x)","EMPTY(robot)","HOLDS(robot,box)"}; S[0][7]=x; S[1][6]=x; S[2][9]=x; if(IsInState(S[1]) && IsInState(S[2])) { if(IsInState(S[0])) Delete(number); else { printf("Cannot pickup %c",x); return false; } if(IsInState(S[3])) Delete(number); else { printf("Cannot pickup %c",x); return false; } Insert(S[4]); return true; } { printf("Cannot pickup %c",x); return false; } } bool SetDown(char x) { char S[5][20]={"AT(robot,x)","TABLE(x)","HOLDS(robot,box)","EMPTY(robot)","ON(box,x)"}; S[0][9]=x; S[1][6]=x; S[4][7]=x; if(IsInState(S[0]) && IsInState(S[1])) { if(IsInState(S[2])) Delete(number); else { printf("Cannot set down %c",x); return false; } Insert(S[3]); Insert(S[4]); return true; } return false; } void ShowState(char s[10][20],int num) { int i; printf(" "); for(i=0;i printf("%s ",s[i]); printf("\n"); } void main() { printf("the process as follows:\n\nThe start state:\n"); ShowState(state,state_num); printf("(1) Go from c To a:\n"); if(!GoTo('c','a')) return; ShowState(state,state_num); printf("(2) PickUp a:\n"); if(!PickUp('a')) return; ShowState(state,state_num); printf("(3) Go from a To b:\n"); if(!GoTo('a','b')) return; ShowState(state,state_num); printf("(4) SetDown b:\n"); if(!SetDown('b')) return; ShowState(state,state_num); printf("(5) Go from b To c:\n"); if(!GoTo('b','c')) return; ShowState(state,state_num); } 六、测试结果及说明 实验很成功 七、实验体会 让我了解到人工智能的先进化，开阔我的眼界通过，本次实验，让我更加了解启发式搜索算法的原理，见识了其广泛的应用；同时加强了本人阅读程序能力和编程能力，以及如何将理论问题解决实际应用的能力。在编程实现过程中出现过不少问题，通过一次次调试得以解决，并一定程度上提高了我的编程能力，而且让我对人工智能这一课程有了更直接的认知 重庆交通大学计算机与信息学院验证性实验报告 班级：计软专业 13 级 1 班 学号： 631306050123 姓名：黄嘉城 实验项目名称：启发式搜索 实验项目性质：验证性实验 实验所属课程：人工智能 实验室(中心)：软件中心实验室（语音楼8楼）指导教师：朱振国 实验完成时间： 2016 年 6 月 10 日 一实验目的 理解和掌握A*算法 二实验内容及要求 在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标，用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）。 三实验设备及软件 visual studio 四、设计方案 ㈠题目 启发式搜索 ㈡设计的主要思路 （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。 ㈢主要功能 解决8数码问题 五、主要代码 #include #include #include #define Overflow 1 #define N 3 int goal[N][N]={1,2,3,8,0,4,7,6,5}; int zero[2],NodeQTY=0; int *z=zero;//记录0的位置 zero[0]:r行； zero[1]:c列； typedef int Piece; struct Chessboard { Piece pos[N][N];//记录每个数码a的位置r行c列 int d,f,move;//d:深度；f:启发函数值；move:父节点移动到该节点的方式 }; struct LNode{ Chessboard board; LNode *parent,*next; bool flag; }; typedef LNode* List; int* Findzero(LNode* &Node) { int i,j,zr[2]; int *z=zr; for(i=0;i { for(j=0;j { if(Node->board.pos[i][j]==0) { zr[0]=i+1; zr[1]=j+1; break; } } } return z; } int Wrong(LNode *Node) { int w=0,i,j; for(i=0;i { for(j=0;j { if(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0) w++; } } return w; } int pick(LNode *Node) { int w=0,i,j,ii,jj; for(i=0;i { for(j=0;j if(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0) { for(ii=0;ii for(jj=0;jj if(Node->board.pos[i][j]==goal[ii][jj]) { w=w+abs(ii-i)+abs(jj-j); break; } } } } return w; } LNode* extend(LNode *Node,int depth,int zero[2],int moveflag,int Choose) { LNode* NewNode=new LNode; for(int i=0;i { for(int j=0;j { NewNode->board.pos[i][j]=Node->board.pos[i][j]; } } switch(moveflag) { case 1: //向左移，不能出界：zero[1]>=2 New-Node->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-1][zero[ 1]-2]; NewNode->board.pos[zero[0]-1][zero[1]-2]=0; break; case 2: //向右移，不能出界：zero[1]<=2 New-Node->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-1][zero[ 1]]; NewNode->board.pos[zero[0]-1][zero[1]]=0; break; case 3: //向上移，不能出界：zero[0]>=2 New-Node->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]-2][zero[ 1]-1]; NewNode->board.pos[zero[0]-2][zero[1]-1]=0; break; case 4: //向下移，不能出界：zero[0]<=2 New-Node->board.pos[zero[0]-1][zero[1]-1]=NewNode->board.pos[zero[0]][zero[1]-1]; NewNode->board.pos[zero[0]][zero[1]-1]=0; break; } NewNode->board.d=depth+1; switch(Choose) { case 1:NewNode->board.f=NewNode->board.d+Wrong(NewNode); break; case 2:NewNode->board.f=NewNode->board.d+pick(NewNode); break; } NewNode->board.move=moveflag; NewNode->parent=Node; NodeQTY++; return NewNode; } void InitList(LNode* &Open,LNode* &Close) { Open=(List)malloc(sizeof(LNode)); Close=(List)malloc(sizeof(LNode)); if(!Open&&!Close) exit(Overflow); Open->next=NULL; Close->next=NULL; } int ListInsert(List &L,LNode* NewNode) { List p=L; while(p->next){ p=p->next; } NewNode->next=p->next; p->next=NewNode; return true; } LNode* Getminf(List &L) { List p=L,q=L->next,r=L,min; min=q;//p,q寻找f最小值的指针，r指向表L中min前一个元素 if(!q) return NULL; while(q) { if(min->board.f>q->board.f) { r=p; min=q; } p=q; q=q->next; } r->next=min->next; min->next=NULL; return min; } int main() { int i,j,choose; List Open,Close; LNode *Best,*current; LNode *Start=new LNode; printf("\t\t\t八数码问题求解\n"); printf("\n请输入初始状态："); for(i=0;i { scanf("%d",&(Start->board.pos[i][j])); } } printf("(注:The flag of movement--1:左移;2:右移;3:上移;4:下移)\n"); printf("初始棋盘状态：\n"); for(i=0;i { for(j=0;j { printf("|%d",Start->board.pos[i][j]); } printf("|\n"); } InitList(Open,Close); printf("请选择(1:A算法;2:A*算法):"); scanf("%d",&choose); Start->board.d=0; switch(choose) { case 1:Start->board.f=Start->board.d+Wrong(Start); break; case 2:Start->board.f=Start->board.d+pick(Start); break; } // Start->board.f=0+Wrong(Start); Start->board.move=0; Start->parent=NULL; Start->next=NULL; Start->flag=1; ListInsert(Open,Start);//将S加入到Open表中 while(Open->next) { Best=Getminf(Open); ListInsert(Close,Best); if(!(Best->board.f-Best->board.d)) { printf("$$$******有解！******$$$\n"); break; } z=Findzero(Best); zero[0]=*(z+0);zero[1]=*(z+1); if(zero[1]>=N-1&&Best->board.move!=2) ListInsert(Open,extend(Best,Best->board.d,zero,1,choose)); if(zero[1]<=N-1&&Best->board.move!=1) ListInsert(Open,extend(Best,Best->board.d,zero,2,choose)); if(zero[0]>=N-1&&Best->board.move!=4) ListInsert(Open,extend(Best,Best->board.d,zero,3,choose)); if(zero[0]<=N-1&&Best->board.move!=3) ListInsert(Open,extend(Best,Best->board.d,zero,4,choose)); } printf("本算法搜索图中总共扩展的节点数为：%d\n",NodeQTY); printf("\t最佳路径如下所示：\n"); if(Open->next) { while(Best->parent) { Best->flag=1; Best=Best->parent; } List p=Close->next,q=Close->next; if(p==Start) q=p->next; else exit(1); int Step=0; while(p&&q)//在Close表中依标记找到路径 { if(q->flag==1&&q->parent==p) { printf("Step %d:0 move as the %d-flag of movement.\n",++Step,q->board.move); for(i=0;i { for(j=0;j { printf("|%d",q->board.pos[i][j]); } printf("|\n"); } p=q;//记住父节点 } q=q->next; } printf("到达目标状态！\n"); } else printf("该问题无法求解！\n"); } 六心得体会 通过本次实验，让我更加了解启发式搜索算法的原理，见识了其广泛的应用；同时加强了本人阅读程序能力和编程能力，以及如何将理论问题解决实际应用的能力。在编程实现过程中出现过不少问题，通过一次次调试得以解决，并一定程度上提高了我的编程能力，而且让我对人工智能这一课程有了更直接的认知 2.5 谓词逻辑推理理论 谓词演算推证的基本思路是将量词消去， 然后用类似命题演算推证法证明。 2.5.1 谓词演算推证 谓词演算推证也是由三个要素组成：推理根据、推理规则和证明方法。 推理根据： 一方面命题演算推证中命题定律和推理定律的代换实例可以作为谓词演算推证的推理依据； 一方面谓词演算的基本逻辑等价式和逻辑蕴涵式： 量词否定逻辑等价式 量词辖域的收缩与扩张逻辑等价式 量词分配逻辑等价式 具有两个量词的逻辑等价式 量词与联结词的逻辑蕴涵式 具有两个量词的逻辑蕴涵式 2.5.1 谓词演算推证 证明方法： 直接证法 间接证明方法 反证法 附加前提证法 2.5.1 谓词演算推证 推理规则： P规则 T规则 CP规则 消去和添加量词的规则 2.5.1 谓词演算推证 1）US 规则（全称指定规则） 这里P 是谓词，而c 是个体域中某个任意的个体。 例如，设个体域为全体偶数的集合，P(x)表示“x 是整数”，则?xP(x)表示“所有的偶数都是整数”，那么根据全称指定规则有P(6)，即“6是整数”。 全称指定规则在使用时要求x 是P(x)中自由出现的个体变元。该规则使用时还可以有以下形式：() () c Ρx x Ρ∴?() () y Ρx Ρ∴?x 这里y 是任意的不在P(x)中约束出现的个体变元。注意： 2.5.1 谓词演算推证 2）UG 规则（全称推广规则） 设E 是指定的个体域，若对于E 中的任意个体a ，都有P(a)成立，才能应用该全称推广规则。例如，设个体域是全体人类，P(x)表示“x 是要死的”。显然，对于任意一个人a ，P(a)都成立，即任何人都是要死的。则应用全称推广规则有?xP(x)成立。 全称推广规则在使用时要求y 不在P(x)中约束出现。注意：) () (y yP x P ?∴ 启发式搜索 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八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个 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.doczj.com/doc/0e12673725.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 谓词演算的 推理理论 在谓词逻辑中，除了命题逻辑中的推理规则继续有效外，还有以下四条规则。设前提Г= {A 1,A 2,…,A k }. 1. 全称指定规则（全称量词消去规则）US ： 例1 取个体域为实数域，F(x, y): x>y, P(x)=(?y) F(x,y), 则(?x)P(x) ?P(z)=(?y) F(z,y). 而不能(?x) P(x) ?P(y)=(?y) F(y,y). 其中x,y 是个体变项符号，c 为任意的个体常量. 或 (?x ) P (x ) ∴ P (y ) (?x) P (x ) ∴ P (c ) 2 . 全称推广规则（全称量词引入规则） UG： P(x) ∴ (?x)P(x) 其中x是个体变项符号，且不在前提的任何公式中 自由出现. 3. 存在指定规则（存在量词消去规则） ES： (?x)P(x) ∴ P(c) 1)c是使P(x)为真的特定的个体常量，不是任意的. 2)c不在前提中或者先前推导公式中出现或自由出现， 换句话说，此c是在该推导之前从未使用过的. 4. 存在推广规则（存在量词引入规则) EG： P(c) ∴ ( x)P(x) 其中x是个体变项符号, c是个体常项符号. 谓词逻辑的推理理论由下列要素构成. 1. 等价公式 2. 蕴含式 3. 推理规则： (1) 前提引入规则 (2) 结论引入规则 (3) CP推理规则 (4)归谬论 (5) US规则 (6) UG规则 (7) ES规则 (8) EG规则 1)在推导的过程中，可以引用命题演算中的规则P、规则T、 规则CP . 2)为了在推导过程中消去量词，可以引用规则US和规则ES来 消去量词. 3)当所要求的结论可能被定量时，此时可引用规则UG和规则 EG将其量词加入. 4)证明时可采用如命题演算中的直接证明方法和间接证明方法. 5)在推导过程中，对消去量词的公式或公式中没含量词的子公 式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式. 6)在推导过程中，对含有量词的公式可以引用谓词中的基本等 价公式和基本蕴涵公式. 启发式搜索——初识A*算法 A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，先说说何谓启发式算法。 一、何谓启发式搜索算法 在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一个解题的过程，应用这个过程可以从求解的开始得到问题的结果。由于求解问题的过程中分支有很多，主要是求解过程中求解条件的不确定性、不完备性造成的，使得求解的路径很多，这样就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。 深度优先是按照一定的顺序，先查找完一个分支，再查找另一个分支，直至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是：他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不可预测的情况下就不可取了。他们的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中搜索时，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直至找到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。 2.5 谓词演算的推理理论 1．推理定律 谓词演算中也存在一些基本的等价与蕴含关系，参见表2-2。我们以此作为推理的基础，即推理定律。 表2-2 序号 等价或蕴含关系 含义 E27 E28 ┐?xA(x)??x┐A(x) ┐?xA(x)??x┐A(x) 量词否定等值式 E29 E30?x(A(x)∧B(x))??xA(x)∧?xB(x) ?x(A(x)∨B(x))??xA(x)∨?xB(x) 量词分配等值式（量词分配律） E31 E32 E33 E34 E35 E36 E37 E38 E39 E40 E41 E42 E43?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(A(x)→B(x))??xA(x)→?xB(x) ?x(A(x)→B)??xA(x)→B ?xA(x)→B??x(A(x)→B) A→?xB(x)??x(A→B(x)) A→?xB(x)??x(A→B(x)) 量词作用域的扩张与收缩 I21 I22?xA(x)∨?xB(x)??x(A(x)∨B(x)) ?x(A(x)∧B(x))??xA(x)∧?xB(x) I23 ?xA(x)→?xB(x)??x(A(x)→B(x)) 表2-2中的I、E序号是接着表1-5和1-8排列的，表明它们都是谓词逻辑的推理定律。E31~E34与E35~E38只是A和B的顺序不同。 2．量词的消除与产生规则 谓词推理可以看作是对命题推理的扩充。除了原来的P规则（前提引入）、T规则（命题等价和蕴含）及反证法、CP规则外，为什么还需引入新的推理规则呢？ 命题逻辑中只有一种命题，但谓词逻辑中有2种，即量词量化的命题和谓词填式命题。如果仅由表2-2的推理定律就可推证，并不需要引入新的规则，但这种情况十分罕见，也失去了谓词逻辑本身的意义。为此，要引入如下4个规则完成量词量化命题与谓词填式之间的转换，其中的A(x)表示任意的谓词。 (1) 全称指定（消去）规则US（Ubiquity Specification，或记为?-） 练习5.1 1?指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并作适当更改，同时回答它们是否是命题： (1)x(P(x)V Q(x))A R (2)x(P(x)A Q(x))A xS(x) f T(x) (3)x(P(x) f y(B(x,y)A Q(y))V T(y)) (4)P(x) ( y x(P(x)A B(x,y)) P(x)) 解： (1)全称量词，辖域P(x)V Q(x)，其中x为约束变元， x(P(x)V Q(x))A R是命题。不需要更改变元。 (2)全称量词，辖域P(x)V Q(x),其中x为约束变元。 存在量词，辖域S(x),其中x为约束变元。 T(x)xxx为自由变元。 x(P(x)A Q(x))A xS(x) f T不是命题。 公式中x既是自由变元又是约束变元，可更改变元为如下公式： x(P(x)A Q(x))A yS(y) f T(z) (3)全称量词，辖域P(x) f y(B(x,y)A Q(y))V T(y),其中x为约 束变元, 存在量词，辖域B(x,y)A Q(y)，其中y为约束变元。 T(y)xxy为自由变元。 x(P(x) f y(B(x,y)A Q(y))V T(y))不是命题。 公式中y既是自由变元又是约束变元，可更改变元为如下公式： x(P(x) -y(B(x,y)A Q(y))V T(z)不是命题。 (4)全称量词，辖域x(P(x)A B(x,y)),其中y为约束变元。 存在量词，辖域P(x)A B(x,y),其中x为约束变元。 不在量词辖域中的P(x)(第一个和第三个P(x))中的x为自由变元。 P(x) y x(P(x)A B(x,y)) - P不是命题。 公式中x既是自由变元又是约束变元，可更改变元为如下公式： P(z) -(y x(P(x)A B(x,y)) - P(z)) 2. 对个体域｛0,1｝判定下列公式的真值，E(x)表示“是偶数” (1)x(E(x) x=1) (2)x(E(x)A「x=1) (3)x(E(x)A x=1) (4)x(E(x) —x=1) 再将它们的量词消去，表示成合取或析取命题公式，鉴别你所确定的真值是否正确。 解： (1)x(E(x) x真) x(E(x) —n可表示成命题公式(E (0) —n 0=1A (E (1) —n 1)1 其中E (0) —n 0真，E 设前提为?x?yF(x, y) ，下面的推证是否正确？ (1) ?x?yF(x, y) P (2) ?yF(y, y) T (1) US 解：推证不正确。 取解释I：个体域为R，在I下前提被解释为?x?y(x>y) ，为真； 而?yF(y, y)被解释为?y(y>y) ，为假。 所以推理不正确。 错误的原因是第(2)步违反了US规则成立的条件y不应在P(x)中约束出现。 设前提为?x?yF(x, y) ，下面的推证是否正确？ (1) ?x?yF(x, y) P (2) ?yF(t, y) T (1) US (3) F(t, c) T (2) ES (4)?xF(x,c) T (3) UG (5)?y?x F(x,y) T (4) EG 解：推证不正确。 取与例2.16相同的解释，则?x?yF(x,y)为真； 而?y?x F(x,y)意为“存在着最小实数”，是假命题， 所以推理不正确。 之所以出现这样的错误，是第(3)步违反了ES规则成立的条件 P(x)中除x外还有其他自由出现的个体变元时，不能用此规则。 试证明 ?x(P(x)→Q(x))∧?x(Q(x)→R(x))??x(P(x)→R(x))证：(1)?x(P(x)→Q(x)) P (2)P(y)→Q(y)T (1) US (3)?x(Q(x)→R(x)) P (4)Q(y)→R(y)T (3) US (5)P(y)→R(y) T (2)(4) I (6)?x(P(x)→R(x)) T (5) UG 证毕。 试证明 ?x(C(x)→W(x)∧R(x))∧?x(C(x)∧Q(x))??x(Q(x)∧R(x))证：(1) ?x(C(x)∧Q(x))P (2) C(a)∧Q(a)T (1) ES (3) ?x(C(x)→W(x)∧R(x))P (4)C(a)→W(a)∧R(a)T (3) US (5)C(a) T (2) I (6)W(a)∧R(a) T (4)(5) I (7)Q(a)T (2) I (8)R(a)T (6) I (9)Q(a)∧R(a)T (7)(8) I (10)?x(Q(x)∧R(x)) T (9) EG 证毕。 启发式图搜索算法 摘要：启发式搜索策略概述和有序搜索。启发式搜索弥补盲目搜索的不足，提高搜索效率。一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。进行搜索技术一般需要某些有关具体问题领域的特性的信息。 关键词：启发式搜索；估价函数；有序搜索；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、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（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|。 人工智能技术报告 启发式搜索 产生背景： 何谓启发式搜索算法在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 定义： 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径， 可以有不同的效果。我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n) 是当h(n) >> g(n)时，可以省略g(n)，而提高效率。这些就深了。 算法举例 启发算法有：蚁群算法，遗传算法、模拟退火算法等蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。 分析：蚁群算法 蚁群算法(ant colony optimization，ACO)，又称蚂蚁算法，指的是一种源于自然现象的算法，也是一种meta heuristic，即与具体问题关系不大的优化算法，也就是它是一种用来在图中寻找优化路径的机率型技术。 蚂蚁觅食原理： 自然界中，蚂蚁这种视盲生物，在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径，甚至在该路径上放置障碍物之后， 它们仍然能很快重新找到新的最佳路线。 启发式搜索A和A*搜索算法 首先什么是启发式搜索？启发式搜索就是利用当前问题有关的信息作为启发式信息，这些信息是能够提升查找效率、减少搜索时间和减少查询次数的。为了利用这些信息，我们定义了一个估价函数h(x)，h(x)是对当前状态x的一个估计，它表示x状态到目标点的距离。那么由它表示的意义我们可以知道，当h(x)等于0时，说明到达了目标点。 一、A和A*搜搜算法介绍 A搜索算法就是使用了估价函数的搜索算法，估价函数的一般形式是f(x)=g(x)+h(x)。其任务就是估计待搜索有希望程度，赢一次给它们排定次序。其中g(x)代表从初始结点到x结点的实际代价，h(x)是从当前结点到目标结点的代价，这个代价是估计出来的。 A*搜索算法是估价函数满足一定条件的算法，其限制条件是f(x)=g(x)+h(x)，代价函数g(x)大于0，h(x)的值不大于x到目标结点的实际代价h*(x)。 二、A和A*搜索算法运用 搜索算法如下： ①将初始节点S0放入Open表中。 ②如Open表为空，则搜索失败，退出。 ③把Open表的第一个节点取出，放入到Closed表中，并把该节点记为节点n。 ④如果节点n是目标节点，则搜索成功，求得一个解，退出。 ⑤扩展节点n，生成一组子节点，对既不在Open表中也不在Closed表中的子节点，计算出相应的估价函数值。 ⑥把节点n的子节点放到Open表中。 ⑦对Open表中的各节点按估价函数值从小到大排列；。 ⑧转到②。 启发式通常用于资讯充份的搜寻算法，例如最好优先贪婪算法与A*。最好优先贪婪算法会为启发式函数选择最低代价的节点；A*则会为g(n) + h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。如果h(n)是可接受的（admissible）意即h(n)未曾付出超过达到目标的代价，则A*一定 Heuristic Search 启发式搜索 译 by 陈雪(QQ:53352894) 必要条件 ?递归算法 主要概念 启发式搜索的主要目标是使用一个估价函数去判断所有状态的“好坏”，以提高搜索找到解的效率。 通常，估价函数表示成一个函数或是一个状态，这个函数叫做“估价函数”例如：?迷宫寻找出路的时候，到出口的欧几里德距离 D=[(xI-xj)^2+(yI-yj)^2]1/2。式中，D是点i和点j之间的距离； xI xj 是第i个点的坐标；yI yj是第j个点的坐标。（译者注） ?当尝试在一场跳棋比赛中获胜时，能吃掉对手的最多棋子子 设计估价函数 直观地看，估价函数越优秀，搜索就更好（快）。问题是：怎么评价估价函数的好坏呢？ 估价函数的好坏，取决于它评估一个状态好坏的能力。例如，迷宫的例子，怎么计算到出口的距离？欧几里德距离也许非常的坏，甚至是非常小的迷宫，它也可能绕很多的路： 一般来说，估价函数越好，搜索就越快。一般来说，搜索时间和估价函数的准确性如下图： 注意！一个似乎很“傻”的估价函数可以大大地提高程序的效率！（如果它非常完美地被使用） 另一个重要概念是“可接受”，一个可接受的估价函数表示对于每个点都不存在“低估”的情况。例如，迷宫的欧几里德距离启发函数是“低估”的，刚才的图例很清楚地说明了这一点。 方法1：启发式剪枝 最简单也是最常用的启发式搜索是利用估价函数来剪枝。假设我们的问题是要求找最小总花费。对于一个可接受的估价函数，当前花费是A，启发函数返回了B，当前子问的最优解是A+B。如果找到的一个解一个花费是C，C谓词演算推证
启发式搜索 八数码问题
《人工智能基础》实验报告-实验名称：启发式搜索算法
实验一 启发式搜索算法
启发式搜索算法解决八数码问题(C语言)
启发式搜索算法在N数码问题中的应用
离散数学24谓词演算的推理理论
启发式搜索A星算法
谓词演算的推理理论(牛连强)
7逻辑代数(下)：谓词演算习题答案
谓词演算推证举例
人工智能启发式图搜索算法
启发式优化算法综述
(完整版)启发式搜索算法
实验二、A＊搜索算法
(启发式搜索)
盲目搜索与启发式搜索的主要方法和策略
启发式搜索
相关主题
文本预览