****大学
人工智能基础课程实验报告
(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)为当前节点的无序度。)
(3)节点的处理
取得一个结点后,判断是否有解,然后对其进行扩展,用估价函数从中取得一个最优节点,依次循环将路径得到,直到取的最后的目标状态。
(4)算法设计
a.输入初始结点,判断解的存在性,并与目标节点对比。
b.若不是目标节点则进行扩展,生成其全部后继节点。
c.对于每个后继节点均求其f(n),并比较。
d.将最小f(n)存入正确路径,并与目标节点进行对比。
e.若不是目标节点则循环执行b,若是目标节点则输出
5实验结果
输入输出:
源代码如下:
#include
int final[9]={1,2,3,8,0,4,7,6,5};//目标状态节点
int a[1000][9],c[9],e[9],f[9];//路径节点和扩展节点
int deep=1,fn;//深度和估计值
int b[9];
char moveaction;//移动方向
int fnjisuan(int b[9])//估价函数
{
int compare=0,s=0,fn1,d[9];
d[0]=b[0];d[1]=b[1];d[2]=b[2];d[3]=b[5];d[4]=b[8];d[5]=b[7];d[6]=b[6];d[7]=b[3];d[ 8]=b[4];
for(int i=0;i<9;i++)
{
if(b[i]!=final[i]&&i!=4)compare++;
}for(i=0;i<7;i++)if((d[i+1]-d[i])!=1)s++;
fn1=2*compare+3*s+deep;//估价函数计算结果
return fn1;
}
void show(int c[9])//输出节点
{
for(int i=0;i<9;i++)a[deep][i]=c[i];
for(i=0;i<9;i++){
if((i)%3==0)printf("\n");
printf("%d\t",c[i]);
}
deep++;
printf("\n");
}
int jingguo(int e[9])//测试当前节点是否已经经过避免回溯
{
for(int i=0;i { int k=0; for(int j=0;j<9;j++) if(e[j]==a[i][j])k++; if(k==9)return 0; }return 1; } int move_up(int c[9],int Zerosign)//上移操作 { for(int i=0;i<9;i++)c[i]=b[i]; c[Zerosign]=c[Zerosign-3]; c[Zerosign-3]=0; int fn1=fnjisuan(c); return fn1; } int move_down(int c[9],int Zerosign)//下移操作 { for(int i=0;i<9;i++)c[i]=b[i]; c[Zerosign]=c[Zerosign+3]; c[Zerosign+3]=0; int fn1=fnjisuan(c); return fn1; } int move_left(int c[9],int Zerosign)//左移操作 { for(int i=0;i<9;i++)c[i]=b[i]; c[Zerosign]=c[Zerosign-1]; c[Zerosign-1]=0; int fn1=fnjisuan(c); return fn1; } int move_right(int c[9],int Zerosign)//右移操作 { for(int i=0;i<9;i++)c[i]=b[i]; c[Zerosign]=c[Zerosign+1]; c[Zerosign+1]=0; int fn1=fnjisuan(c); return fn1; } int zuixiao(int fn1,int fn2,int fn3,int fn4)//求最小值{ int f1,f2,f3; f1=(fn1<=fn2)?fn1:fn2; f2=(fn3<=fn4)?fn3:fn4; f3=(f1<=f2)?f1:f2; return f3; } int cixiao(int fn1,int fn2,int fn3,int fn4)//求次小值{ int f1,f2,f3,f4; f1=(fn1<=fn2)?fn1:fn2; f3=(fn1>fn2)?fn1:fn2; f2=(fn3<=fn4)?fn3:fn4; f4=(fn1>fn2)?fn1:fn2; if(f1<=f2) { if(f3<=f2)return f3; else return f2; } else if(f4<=f1)return f4; else return f1; } void budeng(int f1,int f2,int fn1,int fn2,int fn3,int fn4,int Zerosign)//处理估价函数最小值唯一的时候 { if(f1==fn1) { if(moveaction!='d'&&jingguo(c)) {move_up(c,Zerosign);moveaction='u';} else { if(f2==fn2){move_right(c,Zerosign);moveaction='r';} if(f2==fn3){move_left(c,Zerosign);moveaction='l';} if(f2==fn4){move_down(c,Zerosign);moveaction='d';} } } if(f1==fn2) { if(moveaction!='l'&&jingguo(c)){move_right(c,Zerosign);moveaction='r';} else{ if(f2==fn3){move_left(c,Zerosign);moveaction='l';} if(f2==fn4){move_down(c,Zerosign);moveaction='d';} if(f2==fn1){move_up(c,Zerosign);moveaction='u';} } } if(f1==fn3) { if(moveaction!='r'&&jingguo(c)){move_left(c,Zerosign);moveaction='l';} else{ if(f2==fn1){move_up(c,Zerosign);moveaction='u';} if(f2==fn2){move_right(c,Zerosign);moveaction='r';} if(f2==fn4){move_down(c,Zerosign);moveaction='d';} } } if(f1==fn4) { if(moveaction!='u'&&jingguo(c)){move_down(c,Zerosign);moveaction='d';} else{ if(f2==fn2){move_right(c,Zerosign);moveaction='r';} if(f2==fn3){move_left(c,Zerosign);moveaction='l';} if(f2==fn1){move_up(c,Zerosign);moveaction='u';} } } } int ceshi(int k[9])//测试估价函数 { int fn1=100,fn2=100,fn3=100,fn4=100,f1,Zerosign; for(int i=0;i<9;i++) if(0==k[i]){Zerosign=i;break;} if(Zerosign!=0&&Zerosign!=1&&Zerosign!=2&&moveaction!='d') fn1=move_up(c,Zerosign); if(Zerosign!=2&&Zerosign!=5&&Zerosign!=8&&moveaction!='l') fn2=move_right(c,Zerosign); if(Zerosign!=0&&Zerosign!=3&&Zerosign!=6&&moveaction!='r') fn3=move_left(c,Zerosign); if(Zerosign!=6&&Zerosign!=7&&Zerosign!=8&&moveaction!='u') fn4=move_down(c,Zerosign); f1=zuixiao(fn1,fn2,fn3,fn4); return f1; } void move(int c[9])//确定移动方向 { int fn1=100,fn2=100,fn3=100,fn4=100,f1,f2,Zerosign; for(int i=0;i<9;i++) if(0==c[i]){Zerosign=i;break;} if(Zerosign!=0&&Zerosign!=1&&Zerosign!=2&&moveaction!='d') fn1=move_up(c,Zerosign); if(Zerosign!=2&&Zerosign!=5&&Zerosign!=8&&moveaction!='l') fn2=move_right(c,Zerosign); if(Zerosign!=0&&Zerosign!=3&&Zerosign!=6&&moveaction!='r') fn3=move_left(c,Zerosign); if(Zerosign!=6&&Zerosign!=7&&Zerosign!=8&&moveaction!='u') fn4=move_down(c,Zerosign); f1=zuixiao(fn1,fn2,fn3,fn4); f2=cixiao(fn1,fn2,fn3,fn4); if(f1==f2) { if(fn1==fn2&&fn1==f1) { move_up(c,Zerosign); for(i=0;i<9;i++)e[i]=c[i]; move_right(c,Zerosign); for(i=0;i<9;i++)f[i]=c[i]; if((ceshi(e) else {move_right(c,Zerosign);moveaction='r';} } if(fn1==fn3&&fn1==f1) { move_up(c,Zerosign); for(i=0;i<9;i++)e[i]=c[i]; move_left(c,Zerosign); for(i=0;i<9;i++)f[i]=c[i]; if((ceshi(e) } if(fn1==fn4&&fn1==f1) { move_up(c,Zerosign); for(i=0;i<9;i++)e[i]=c[i]; move_down(c,Zerosign); for(i=0;i<9;i++)f[i]=c[i]; if((ceshi(e) else {move_down(c,Zerosign);moveaction='d';} } if(fn2==fn3&&fn2==f1) { move_right(c,Zerosign); for(i=0;i<9;i++)e[i]=c[i]; move_left(c,Zerosign); for(i=0;i<9;i++)f[i]=c[i]; if((ceshi(e) else {move_left(c,Zerosign);moveaction='l';} } if(fn2==fn4&&fn2==f1) { move_right(c,Zerosign); for(i=0;i<9;i++)e[i]=c[i]; move_down(c,Zerosign); for(i=0;i<9;i++)f[i]=c[i]; if((ceshi(e) else {move_down(c,Zerosign);moveaction='d';} } if(fn3==fn4&&fn3==f1) { move_left(c,Zerosign); for(i=0;i<9;i++)e[i]=c[i]; move_down(c,Zerosign); for(i=0;i<9;i++)f[i]=c[i]; if((ceshi(e) else {move_down(c,Zerosign);moveaction='d';} } } else budeng(f1,f2,fn1,fn2,fn3,fn4,Zerosign); } int duibi(int c[9]) {//与目标节点比较 for(int i=0;i<9;i++) if(c[i]!=final[i]) break; if(i>=9)return 1; else return 0; } int cunzaixing(int c[9]) {//得出初始化节点是否存在路径到目标节点 int nixu=0,nixu1=0,i,j; for( j=0;j<9;j++) for(int i=j+1;i<9;i++) if(final[j]>final[i]&&final[j]!=0&&final[i]!=0)nixu++; for(j=0;j<9;j++) for( i=j+1;i<9;i++) if(c[j]>c[i]&&c[j]!=0&&c[i]!=0)nixu1++; if((nixu%2)-(nixu1%2)==0) return 1; else return 0; } void main(){//主函数 int sd=1; printf("请输入初始结点如(2 8 3 1 6 4 7 0 5)以空格隔开的九个0到9之间的不重复数: \n"); for(int i=0;i<9;i++) { scanf("%d",&b[i]); c[i]=b[i]; }printf("您输入的初始矩阵为:\n"); show(c); deep--; if(cunzaixing(c)==0) printf("此矩阵不存在路径至目标矩阵!\n"); else{ while(!duibi(c)&&deep<100){ move(c); printf("第%d步移动后的矩阵为:\n",sd++);show(c); for(int i=0;i<9;i++) b[i]=c[i];} } } 实验二王浩算法的实现 1. 实验内容: 实现命题逻辑框架内的王浩算法。 ⑴将命题逻辑中的王浩算法推广至下述命题语言的情形之下: ⅰ命题变量符号:1p,2 p,L p,3 ⅱ逻辑连接符:?,∧,∨,→,? ⅲ间隔符:(,) ⑵在上述⑴中所定义的命题语言中实现王浩算法。 2.实验目的 熟练掌握命题逻辑中的王浩算法。 3.实验要求 ⑴实验题目必须由个人独立完成,允许自行参考相关文献资料,但严禁同学间相互拷贝和抄袭程序以及文档资料。实验结束后一周内上交实验报告和实验文档资料。 ⑵提交的文档资料包括设计文档和程序源代码。设计文档和程序源代码以书面文档方式提供(用4 A纸打印);并提交电子文档备查。 四.数据结构 给定公式,例如:(p1->(q1->r1))->((p1->q1)->(p1->r1)) 函数inite主要作用是负责将符号初始化成树的结构。 函数clone复制一棵完全相同的符号树。 函数restruct查找所有&,|, <->等符号,并将其拆分成新形式:!,->符号。 函数searching王浩算法的主要函数。 函数show和output:显示符号串和推理过程。 五.实验结果 公式正确 六.实验总结 通过本次实验,使我更深入的理解了启发式搜索的原理以及实现,对于其优越性有一定认识,加深了对语法分析以及逻辑公式理解,同时熟练掌握了对树的操作。 在编程实现过程中出现过不少问题,通过一次次调试得以解决,并一定程度上提高了我的编程能力,而且让我对人工智能这一课程有了更直接的认知。 王浩算法源代码清单: #include #include #include #define MAX_L 5 int i=0; int stepcount=1; enum type{and,or,detrusion,equal,level,variable}; struct node{char *s;type kind;int polar;node *next;node *child;int start;}; struct step{step *child;step *brother;node *lhead;node *rhead;int count;char name[30];}; int inite(char *s,node *head){ int len=strlen(s); int j=0,polar=1; node *now=NULL; node *last=NULL; if(s==NULL)return 0; last=head; while(i if(s[i]=='|'){ if(!(s[i+1]<='Z'&&s[i+1]>='A'||s[i+1]<='z'&&s[i+1]>='a')&&s[i+1]!='1'&&s[i+1]!='0' &&s[i+1]!='('&&s[i+1]!='!'||i==0)return 0; now=(node*)malloc(sizeof(node)); now->kind=or; now->s=NULL; now->next=NULL; now->child=NULL; now->polar=polar; now->start=0; if(last->kind==level&&last->child==NULL){ last->child=now; }else{last->next=now;} last=now; i++; }else if(s[i]=='&'){ if(!(s[i+1]<='Z'&&s[i+1]>='A'||s[i+1]<='z'&&s[i+1]>='a')&&s[i+1]!='1'&&s[i+1]!='0' &&s[i+1]!='('&&s[i+1]!='!'||i==0) return 0; now=(node*)malloc(sizeof(node)); now->kind=and; now->s=NULL; now->next=NULL; now->child=NULL; now->polar=polar; now->start=0; if(last->kind==level&&last->child==NULL){ last->child=now; }else{ last->next=now; }last=now; i++; }else if(s[i]=='!'){ if(!(s[i+1]<='Z'&&s[i+1]>='A'||s[i+1]<='z'&&s[i+1]>='a')&&s[i+1]!='1'&&s[i+1]!='0' &&s[i+1]!='('&&s[i+1]!='!') return 0; polar=1-polar; i++; }else if(s[i]=='-'){ if(s[i+1]!='>'||(s[i+2]!='!'&&s[i+2]!='('&&!(s[i+2]<='Z'&&s[i+2]>='A'||s[i+2]<='z' &&s[i+2]>='a'))||i==0) return 0; now=(node*)malloc(sizeof(node)); now->kind=detrusion; now->s=NULL; now->next=NULL; now->child=NULL; now->polar=polar; now->start=0; if(last->kind==level&&last->child==NULL){ last->child=now; }else{ last->next=now; }last=now; i=i+2; }else if(s[i]=='<'){ if((s[i+1]!='-'||s[i+2]!='>')||(s[i+3]!='!'&&s[i+3]!='('&&!(s[i+3]<='Z'&&s[i+3]>=' A'||s[i+3]<='z'&&s[i+3]>='a')||i==0)&&s[i+3]!='1'&&s[i+3]!='0') return 0; now=(node*)malloc(sizeof(node)); now->kind=equal; now->s=NULL; now->next=NULL; now->child=NULL; now->polar=polar; now->start=0; if(last->kind==level&&last->child==NULL){ last->child=now; }else{ last->next=now; }last=now; i=i+3; }else if(s[i]<='Z'&&s[i]>='A'||s[i]<='z'&&s[i]>='a'){ now=(node*)malloc(sizeof(node)); now->kind=variable; now->next=NULL; now->child=NULL; now->polar=polar; now->start=0; now->s=(char*)malloc(MAX_L*sizeof(char)); if(last->kind==level&&last->child==NULL){ last->child=now; }else{ last->next=now; }last=now; j=0; while((s[i]<='Z'&&s[i]>='A'||s[i]<='z'&&s[i]>='a')||(s[i]<='9'&&s[i]>='0')) (now->s)[j]=s[i]; i++; j++; }if(s[i]!='|'&&s[i]!='&'&&s[i]!='-'&&s[i]!='<'&&s[i]!='\0'&&s[i]!=')') return 0; (now->s)[j]='\0'; polar=1; }else if(s[i]=='1'||s[i]=='0'){ if(s[i+1]!='<'&&s[i+1]!='-'&&s[i+1]!='&'&&s[i+1]!='|'&&s[i+1]!=')'&&s[i+1]!='\0') return 0; now=(node*)malloc(sizeof(node)); now->kind=equal; now->s=(char*)malloc(2*sizeof(char)); (now->s)[0]=s[i]; (now->s)[1]='\0'; now->next=NULL; now->child=NULL; now->polar=polar; now->start=0; if(last->kind==level&&last->child==NULL){ last->child=now; }else{ last->next=now; }last=now; i++; }else if(s[i]=='('){ if(!(s[i+1]<='Z'&&s[i+1]>='A'||s[i+1]<='z'&&s[i+1]>='a')&&s[i+1]!='1'&&s[i+1]!='0' &&s[i+1]!='!'&&s[i+1]!='(') return 0; now=(node*)malloc(sizeof(node)); now->kind=level; now->s=NULL; now->next=NULL; now->child=NULL; now->polar=polar; now->start=0; if(last->kind==level&&last->child==NULL){ last->child=now; }else{ last->next=now; }last=now; i++; polar=1; if(!inite(s,last))return 0; }else if(s[i]==')'){ if(s[i+1]!='P'&&s[i+1]!='1'&&s[i+1]!='0'&&s[i+1]!='-'&&s[i+1]!='<'&&s[i+1]!='&'&&s [i+1]!='|'&&s[i+1]!='\0'&&s[i+1]!=')') return 0; i++; return 1; }else return 0; }return 1; } node* clone(node *parent){ node *son=NULL; if(parent==NULL)return NULL; son=(node*)malloc(sizeof(node)); son->kind=parent->kind; son->polar=parent->polar; son->s=parent->s; son->start=parent->start; if(parent->next!=NULL) son->next=clone(parent->next); else son->next=NULL; if(parent->child!=NULL) son->child=clone(parent->child); else son->child=NULL; return son; } void remove(node *head){ node *now=NULL; now=head; if(now==NULL)return; if(now->kind==level&&now->child->kind==variable&&now->child->next==NULL){ now->polar=(now->child->polar==now->polar); now->child->polar=1; } while(now->kind==level&&now->child->kind==level&&now->child->next==NULL){ now->polar=(now->polar==now->child->polar); now->child=now->child->child; } if(now->next!=NULL)remove(now->next); if(now->child!=NULL)remove(now->child); } void restruct(node* head){ node *now=NULL; node *last=NULL; node *newone=NULL,*newtwo=NULL,*newthree=NULL,*newfour=NULL,*newnow=NULL; int order=1; while(order<=4){ last=head; now=last->child; while(now!=NULL){ if((now->kind==variable||now->kind==level)&&order==1){ if(now->next!=NULL&&now->next->kind==and){ newone=(node*)malloc(sizeof(node)); newone->child=NULL; newone->kind=level; newone->next=NULL; newone->polar=0; newone->s=NULL; newone->start=0; if(last->kind==level) last->child=newone; else last->next=newone; newone->next=now->next->next->next; newone->child=now; now->next->next->polar=1-now->next->next->polar; now->next->kind=detrusion; now->next->next->next=NULL; now=newone; }else{ last=now; now=now->next; } }else if((now->kind==variable||now->kind==level)&&order==2){ if(now->next!=NULL&&now->next->kind==or){ newone=(node*)malloc(sizeof(node)); newone->child=NULL; newone->kind=level; newone->next=NULL; newone->polar=1; newone->s=NULL; newone->start=0; if(last->kind==level) last->child=newone; else last->next=newone; newone->next=now->next->next->next; newone->child=now; now->polar=1-now->polar; now->next->kind=detrusion; now->next->next->next=NULL; now=newone; }else{ last=now; now=now->next; } }else if((now->kind==variable||now->kind==level)&&order==3){ if(now->next!=NULL&&now->next->kind==equal){ newone=(node*)malloc(sizeof(node)); newone->child=NULL; newone->kind=level; newone->next=NULL; newone->polar=0; newone->s=NULL; newone->start=0; newtwo=(node*)malloc(sizeof(node)); newtwo->child=NULL; newtwo->kind=level; newtwo->next=NULL; newtwo->polar=1; newtwo->s=NULL; newtwo->start=0; newthree=(node*)malloc(sizeof(node)); newthree->child=NULL; newthree->kind=detrusion; newthree->next=NULL; newthree->polar=1; newthree->s=NULL; newthree->start=0; newfour=(node*)malloc(sizeof(node)); newfour->child=NULL; newfour->kind=level; newfour->next=NULL; newfour->polar=0; newfour->s=NULL; newfour->start=0; if(last->kind==level) last->child=newone; else last->next=newone; newone->next=now->next->next->next; newone->child=newtwo; now->next->kind=detrusion; newtwo->child=now; now->next->next->next=NULL; newtwo->next=newthree; newthree->next=newfour; newfour->next=NULL; newnow=clone(now); newnow->next->kind=detrusion; newfour->child=newnow->next->next; newnow->next->next->next=newnow->next; newnow->next->next=newnow; newnow->next=NULL; now=newone; }else{ last=now; now=now->next; } }else if(now->kind==level&&order==4){ restruct(now); last=now; now=now->next; }else{ last=now; now=now->next; } }order++; } } void show(node *head){ node *now=NULL; now=head; while(now!=NULL){ if(now->kind==level){ if(now->polar==0)printf("!"); if(now->start!=1||(now->polar==0&&now->child->next!=NULL))printf("("); show(now->child); if(now->start!=1||(now->polar==0&&now->child->next!=NULL))printf(")"); now=now->next; if(now!=NULL&&now->start==1)putchar(','); }else if(now->kind==and){ printf("&"); now=now->next; }else if(now->kind==or){ printf("|"); now=now->next; }else if(now->kind==detrusion){ printf("->"); now=now->next; }else if(now->kind==equal){ printf("<->"); now=now->next; }else if(now->kind==variable){ if(now->polar==0)printf("!"); printf("%s",now->s); now=now->next; } }return; } int searching(step *one){ node *now=NULL; node *last=NULL; node *newlev=NULL; node *nnow=NULL; node *nlast=NULL; step *nextone=NULL; step *nexttwo=NULL; int key=0; int mark=0; int re1=1; int re2=1; nextone=(step*)malloc(sizeof(step)); nextone->brother=NULL; nextone->child=NULL; nextone->lhead=NULL; nextone->rhead=clone(one->rhead); nextone->lhead=clone(one->lhead); strcpy(nextone->name,""); one->child=nextone; now=nextone->rhead; last=now; while(now!=NULL){ if(now->polar==0){ if(now==nextone->rhead)nextone->rhead=now->next; else last->next=now->next; now->next=NULL; remove(now); now->next=nextone->lhead; nextone->lhead=now; now->polar=1-now->polar; now->start=1; now=last->next; strcpy(one->name,"根据规则1"); mark=1; key=1; break; }else if(now->child->next!=NULL&&now->child->next->kind==detrusion){ nlast=now->child; nnow=now->child->next; while(nnow->next->next!=NULL&&nnow->next->next->kind==detrusion){ nlast=nnow->next; nnow=nnow->next->next; } now->polar=1-now->polar; newlev=(node*)malloc(sizeof(node)); newlev->child=nnow->next; newlev->kind=level; newlev->polar=1; newlev->next=NULL; newlev->start=1; nlast->next=NULL; remove(newlev); newlev->next=now->next; now->next=NULL; remove(now); now->next=newlev; strcpy(one->name,"根据规则4"); mark=1; key=1; break; }else{ last=now; now=now->next; } }now=nextone->lhead; last=now; while(now!=NULL&&key!=1){ if(now->polar==0){ if(now==nextone->lhead)nextone->lhead=now->next; else last->next=now->next; now->next=NULL; remove(now); now->next=nextone->rhead; nextone->rhead=now; now->polar=1-now->polar; now->start=1; now=last->next; strcpy(one->name,"根据规则2"); mark=1; key=1; break; }else if(now->child->next!=NULL&&now->child->next->kind==detrusion){ nexttwo=(step*)malloc(sizeof(step)); nexttwo->brother=NULL; nexttwo->child=NULL; nexttwo->lhead=NULL; nexttwo->rhead=clone(nextone->rhead); nexttwo->lhead=clone(nextone->lhead); strcpy(nexttwo->name,""); nlast=now->child; nnow=now->child->next; 人工智能实验报告大 全 人工智能课内实验报告 (8次) 学院:自动化学院 班级:智能1501 姓名:刘少鹏(34) 学号: 06153034 目录 课内实验1:猴子摘香蕉问题的VC编程实现 (1) 课内实验2:编程实现简单动物识别系统的知识表示 (5) 课内实验3:盲目搜索求解8数码问题 (18) 课内实验4:回溯算法求解四皇后问题 (33) 课内实验5:编程实现一字棋游戏 (37) 课内实验6:字句集消解实验 (46) 课内实验7:简单动物识别系统的产生式推理 (66) 课内实验8:编程实现D-S证据推理算法 (78) 人工智能课内实验报告实验1:猴子摘香蕉问题的VC编程实现 学院:自动化学院 班级:智能1501 姓名:刘少鹏(33) 学号: 06153034 日期: 2017-3-8 10:15-12:00 实验1:猴子摘香蕉问题的VC编程实现 一、实验目的 (1)熟悉谓词逻辑表示法; (2)掌握人工智能谓词逻辑中的经典例子——猴子摘香蕉问题的编程实现。 二、编程环境 VC语言 三、问题描述 房子里有一只猴子(即机器人),位于a处。在c处上方的天花板上有一串香蕉,猴子想吃,但摘不到。房间的b处还有一个箱子,如果猴子站到箱子上,就可以摸着天花板。如图1所示,对于上述问题,可以通过谓词逻辑表示法来描述知识。要求通过VC语言编程实现猴子摘香蕉问题的求解过程。 图1 猴子摘香蕉问题 四、源代码 #include 游戏人工智能实验报告记录四 ————————————————————————————————作者:————————————————————————————————日期: 实验四有限状态机实验 实验报告 一、实验目的 通过蚂蚁世界实验掌握游戏中追有限状态机算法 二、实验仪器 Windows7系统 Microsoft Visual Studio2015 三、实验原理及过程 1)制作菜单 设置参数:点击会弹出对话框,设置一些参数,红、黑蚂蚁的家会在地图上标记出来 运行:设置好参数后点击运行,毒药、食物、水会在地图上随机显示 下一步:2只红蚂蚁和2只黑蚂蚁会随机出现在地图上,窗口右方还会出现红、黑蚂蚁当前数量的统计 不断按下一步,有限状态机就会不断运行,使蚁群产生变化 2)添加加速键 资源视图中下方 选择ID和键值 3)新建头文件def.h 在AntView.cpp中加入#include"def.h" 与本实验有关的数据大都是在这里定义的 int flag=0; #define kForage 1 #define kGoHome 2 #define kThirsty 3 #define kDead 4 #define kMaxEntities 200 class ai_Entity{ public: int type; int state; int row; int col; ai_Entity(); ~ai_Entity() {} void New (int theType,int theState,int theRow,int theCol); void Forage(); void GoHome(); void Thirsty(); void Dead(); 《人工智能》课外实践报告 项目名称:剪枝法五子棋 所在班级: 2013级软件工程一班 小组成员:李晓宁、白明辉、刘小晶、袁成飞、程小兰、李喜林 指导教师:薛笑荣 起止时间: 2016-5-10——2016-6-18 项目基本信息 一、系统分析 1.1背景 1.1.1 设计背景 智力小游戏作为人们日常休闲娱乐的工具已经深入人们的生活,五子棋更成为了智力游戏的经典,它是基于AI的αβ剪枝法和极小极大值算法实现的人工智能游戏,让人们能和计算机进行对弈。能使人们在与电脑进行对弈的过程中学习五子棋,陶冶情操。并且推进人们对AI的关注和兴趣。 1.1.2可行性分析 通过研究,本游戏的可行性有以下三方面作保障 (1)技术可行性 本游戏采用Windows xp等等系统作为操作平台,使用人工智能进行算法设计,利用剪枝法进行编写,大大减少了内存容量,而且不用使用数据库,便可操作,方便可行,因此在技术上是可行的。 (2)经济可行性 开发软件:SublimText (3)操作可行性 该游戏运行所需配置低、用户操作界面友好,具有较强的操作可行性。 1.2数据需求 五子棋需要设计如下的数据字段和数据表: 1.2.1 估值函数: 估值函数通常是为了评价棋型的状态,根据实现定义的一个棋局估值表,对双方的棋局形态进行计算,根据得到的估值来判断应该采用的走法。棋局估值表是根据当前的棋局形势,定义一个分值来反映其优势程度,来对整个棋局形势进行评价。本程序采用的估值如下: 状态眠二假活三眠三活二冲四假活三活三活四连五 分值 2 4 5 8 12 15 40 90 200 一般来说,我们采用的是15×15的棋盘,棋盘的每一条线称为一路,包括行、列和斜线,4个方向,其中行列有30路,两条对角线共有58路,整个棋盘的路数为88路。考虑到五子棋必须要五子相连才可以获胜,这样对于斜线,可以减少8路,即有效的棋盘路数为72路。对于每一路来说,第i路的估分为E(i)=Ec(i)-Ep(i),其中Ec(i)为计算机的i路估分,Ep(i)为玩家的i路估分。棋局整个形势的估值情况通过对各路估分的累加进行判断,即估值函数: 72 F(n)= Σ E(i) i=1 1.2.2 极小极大值算法: 极大极小搜索算法就是在博弈树在寻找最优解的一个过程,这主要是一个对各个子结点进行比较取舍的过程,定义一个估值函数F(n)来分别计算各个终结点的分值,通过双方的分值来对棋局形势进行分析判断。以甲乙两人下棋为例,甲为max,乙为min。当甲走棋时,自然在博弈树中寻找最大点的走法,轮到乙时,则寻找最小点的走法,如此反复,这就是一个极大极小搜索过程,以此来寻找对机器的最佳走法。 实验四有限状态机实验 实验报告 一、实验目的 通过蚂蚁世界实验掌握游戏中追有限状态机算法 二、实验仪器 Windows7系统 Microsoft Visual Studio2015 三、实验原理及过程 1)制作菜单 设置参数:点击会弹出对话框,设置一些参数,红、黑蚂蚁的家会在地图上标记出来 运行:设置好参数后点击运行,毒药、食物、水会在地图上随机显示 下一步:2只红蚂蚁和2只黑蚂蚁会随机出现在地图上,窗口右方还会出现红、黑蚂蚁当前数量的统计 不断按下一步,有限状态机就会不断运行,使蚁群产生变化 2)添加加速键 资源视图中 下方 选择ID和键值 3)新建头文件def.h 在AntView.cpp中加入#include"def.h" 与本实验有关的数据大都是在这里定义的 int flag=0; #define kForage 1 #define kGoHome 2 #define kThirsty 3 #define kDead 4 #define kMaxEntities 200 class ai_Entity{ public: int type; int state; int row; int col; ai_Entity(); ~ai_Entity() {} void New (int theType,int theState,int theRow,int theCol); void Forage(); void GoHome(); void Thirsty(); void Dead(); }; ai_Entity entityList[kMaxEntities]; #define kRedAnt 1 #define kBlackAnt 2 人工智能导论实验报告 学院:计算机科学与技术学院 专业:计算机科学与技术 2016.12.20 目录 人工智能导论实验报告 (1) 一、简介(对该实验背景,方法以及目的的理解) (3) 1. 实验背景 (3) 2. 实验方法 (3) 3. 实验目的 (3) 二、方法(对每个问题的分析及解决问题的方法) (4) Q1: Depth First Search (4) Q2: Breadth First Search (4) Q3: Uniform Cost Search (5) Q4: A* Search (6) Q5: Corners Problem: Representation (6) Q6: Corners Problem: Heuristic (6) Q7: Eating All The Dots: Heuristic (7) Q8: Suboptimal Search (7) 三、实验结果(解决每个问题的结果) (7) Q1: Depth First Search (7) Q2: Breadth First Search (9) Q3: Uniform Cost Search (10) Q4: A* Search (12) Q5: Corners Problem: Representation (13) Q6: Corners Problem: Heuristic (14) Q7: Eating All The Dots: Heuristic (14) Q8: Suboptimal Search (15) 自动评分 (15) 四、总结及讨论(对该实验的总结以及任何该实验的启发) (15) 人工智能课内实验报告 (8次) 学院:自动化学院 班级:智能1501 姓名:刘少鹏(34) 学号: 06153034 目录 课内实验1:猴子摘香蕉问题的VC编程实现 (1) 课内实验2:编程实现简单动物识别系统的知识表示 (5) 课内实验3:盲目搜索求解8数码问题 (18) 课内实验4:回溯算法求解四皇后问题 (33) 课内实验5:编程实现一字棋游戏 (37) 课内实验6:字句集消解实验 (46) 课内实验7:简单动物识别系统的产生式推理 (66) 课内实验8:编程实现D-S证据推理算法 (78) 人工智能课内实验报告实验1:猴子摘香蕉问题的VC编程实现 学院:自动化学院 班级:智能1501 姓名:刘少鹏(33) 学号: 06153034 日期: 2017-3-8 10:15-12:00 实验1:猴子摘香蕉问题的VC编程实现 一、实验目的 (1)熟悉谓词逻辑表示法; (2)掌握人工智能谓词逻辑中的经典例子——猴子摘香蕉问题的编程实现。 二、编程环境 VC语言 三、问题描述 房子里有一只猴子(即机器人),位于a处。在c处上方的天花板上有一串香蕉,猴子想吃,但摘不到。房间的b处还有一个箱子,如果猴子站到箱子上,就可以摸着天花板。如图1所示,对于上述问题,可以通过谓词逻辑表示法来描述知识。要求通过VC语言编程实现猴子摘香蕉问题的求解过程。 图1 猴子摘香蕉问题 四、源代码 #include 计算机科学与技术1341901301 敏 实验一:知识表示方法 一、实验目的 状态空间表示法是人工智能领域最基本的知识表示方法之一,也是进一步学习状态空间搜索策略的基础,本实验通过牧师与野人渡河的问题,强化学生对知识表示的了解和应用,为人工智能后续环节的课程奠定基础。 二、问题描述 有n个牧师和n个野人准备渡河,但只有一条能容纳c个人的小船,为了防止野人侵犯牧师,要求无论在何处,牧师的人数不得少于野人的人数(除非牧师人数为0),且假定野人与牧师都会划船,试设计一个算法,确定他们能否渡过河去,若能,则给出小船来回次数最少的最佳方案。 三、基本要求 输入:牧师人数(即野人人数):n;小船一次最多载人量:c。 输出:若问题无解,则显示Failed,否则,显示Successed输出一组最佳方案。用三元组(X1, X2, X3)表示渡河过程中的状态。并用箭头连接相邻状态以表示迁移过程:初始状态->中间状态->目标状态。 例:当输入n=2,c=2时,输出:221->110->211->010->021->000 其中:X1表示起始岸上的牧师人数;X2表示起始岸上的野人人数;X3表示小船现在位置(1表示起始岸,0表示目的岸)。 要求:写出算法的设计思想和源程序,并以图形用户界面实现人机交互,进行输入和输出结果,如: Please input n: 2 Please input c: 2 Successed or Failed?: Successed Optimal Procedure: 221->110->211->010->021->000 四、算法描述 (1)算法基本思想的文字描述; 实验报告 1.对CLIPS和其运行及推理机制进行介绍 CLIPS是一个基于前向推理语言,用标准C语言编写。它具有高移植性、高扩展性、 强大的知识表达能力和编程方式以及低成本等特点。 CLIPS由两部分组成:知识库、推理机。它的基本语法是: (defmodule< module-n ame >[< comme nt >]) CLIPS的基本结构: (1).知识库由事实库(初始事实+初始对象实例)和规则库组成。 事实库: 表示已知的数据或信息,用deftemplat,deffact定义初始事实表FACTLIS,由关系名、后跟 零个或多个槽以及它们的相关值组成,其格式如下: 模板: (deftemplate 《人工智能导论》作业(1-4章) 1.人工智能有哪几个主要的学派?各学派的基本理论框架和主要研究方向有何不同?2.用谓词逻辑方法表述下面问题积木世界的问题。 (定义谓词、描述状态、定义操作、给出操作序列) 3.请给出下列描述的语义网络表示: 1)11月5日,NBA常规赛火箭主场对阵小牛,火箭107-76大胜小牛。 2)张老师从9月至12月给自动化专业学生教授《自动控制原理》。李老师从10至12月 给计算机专业学生教授《操作系统原理》。 3)树和草都是植物;树和草都有根和叶;水草是草,生活在水中;果树是树,会结果; 苹果树是果树,结苹果。 4.请用相应谓词公式描述下列语句: 1)有的人喜欢足球、有的人喜欢篮球;有的人既喜欢足球又喜欢篮球。 2)喜欢编程的同学都喜欢计算机。 3)不是每个自控系的学生都喜欢编程。 4)有一个裁缝,他给所有不自己做衣服的人做衣服。 5)如果星期六不下雨,汤姆就会去爬山。 5.什么是谓词公式的解释?对于公式?x ?y (P(x)→Q(f(x),y)) D={1,2,3} 分别给出使公式为真和假的一种解释。 6.什么是合一?求出下面公式的最一般合一: P(f(y), y, x) P(x, f(a),z)。 7.把下面谓词公式化为子句集 ?x ?y (P(x,y)∨Q(x,y))→R(x,y)) ?x (P(x) →?y(P(y)∧R(x,y)) ?x (P(x)∧?y(P(y) →R(x,y))) 8.证明下面各题中,G是否是F的逻辑结论? F1: ?x (P(x) →?y(Q(y)→L(x,y))) F2: ?x (P(x)∧?y(R(y) →L(x,y))) G: ?x (R(x) →~Q(x)) F1: ?z (~B(z)→?y(D(z,y)∧C(y))) F2: ?x (E(x)∧A(x)∧?y (D(x,y) →E(y))) F3: ?y(E(y) →~B(y)) G: ?z (E(z) ∧C(z)) 9.已知:John, Mike, Sam是高山俱乐部成员。 高山俱乐部成员都是滑雪运动员或登山运动员(也可以都是)。 登山运动员不喜欢雨。 滑雪运动员都喜欢雪。 凡是Mike喜欢的,John就不喜欢。 凡是Mike 不喜欢的,John就喜欢。 Mike喜欢雨和雪。 问:高山俱乐部是否有一个成员,他是登山运动员,但不是滑雪运动员?如果有,他是谁?10.为什么说归结式是其亲本子句的逻辑结论? 11.何为完备的归结策略?有哪些归结策略是完备的? 12.何谓搜索?有哪些常用的搜索方法?盲目搜索与启发式搜索的根本区别是什么?13.用状态空间法表示问题时,什么是问题的解?什么是最优解?在图搜索算法中,OPEN 表和CLOSED表的作用是什么?f(x)有何不同含义? 14.宽度优先搜索和深度优先搜索有何不同?在何种情况下,宽度优先搜索优于深度优先搜索,何种情况反之? 15.什么是启发式搜索,g(x)与h(x)各有什么作用?A*算法的限制条件是什么? 人工智能导论 实验报告 姓名:蔡鹏 学号:1130310726 实验一 一、实验内容 有如下序列,试把所有黑色格移到所有白色格的右边,黄色格代表空格,黑色格和白色格可以和距离不超过三的空格交换。 二、实验代码 #include Enstack(root,&S); while(S.num!=0) { n=Destack(&S); if(n->f < min->f) { min=n; } for(i=0;i 人工智能课程项目报告 姓名: 班级:二班 一、实验背景 在新的时代背景下,人工智能这一重要的计算机学科分支,焕发出了他强大的生命力。不仅仅为了完成课程设计,作为计算机专业的学生, 了解他,学习他我认为都是很有必要的。 二、实验目的 识别手写字体0~9 三、实验原理 用K-最近邻算法对数据进行分类。逻辑回归算法(仅分类0和1)四、实验内容 使用knn算法: 1.创建一个1024列矩阵载入训练集每一行存一个训练集 2. 把测试集中的一个文件转化为一个1024列的矩阵。 3.使用knnClassify()进行测试 4.依据k的值,得出结果 使用逻辑回归: 1.创建一个1024列矩阵载入训练集每一行存一个训练集 2. 把测试集中的一个文件转化为一个1024列的矩阵。 3. 使用上式求参数。步长0.07,迭代10次 4.使用参数以及逻辑回归函数对测试数据处理,根据结果判断测试数 据类型。 五、实验结果与分析 5.1 实验环境与工具 Window7旗舰版+ python2.7.10 + numpy(库)+ notepad++(编辑) Python这一语言的发展是非常迅速的,既然他支持在window下运行就不必去搞虚拟机。 5.2 实验数据集与参数设置 Knn算法: 训练数据1934个,测试数据有946个。 数据包括数字0-9的手写体。每个数字大约有200个样本。 每个样本保持在一个txt文件中。手写体图像本身的大小是32x32的二值图,转换到txt文件保存后,内容也是32x32个数字,0或者1,如下图所 示 建立一个kNN.py脚本文件,文件里面包含三个函数,一个用来生成将每个样本的txt文件转换为对应的一个向量:img2vector(filename):,一个用 来加载整个数据库loadDataSet():,最后就是实现测试。 人工智能实验报告 学号: 姓名: 实验名称:遗传算法 实验日期:2016.1.5 【实验名称】遗传算法 【实验目的】 掌握遗传算法的基本原理,熟悉遗传算法的运行机制,学会用遗传算法来求解问题。 【实验原理】 遗传算法( Genetic Algorithm )是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群开始的,而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化, 如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来 越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学 的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。 遗传算法程度流程图为: 【实验名称】遗传算法 【实验目的】 掌握遗传算法的基本原理,熟悉遗传算法的运行机制,学会用遗传算法来求解问题。 【实验原理】 遗传算法( Genetic Algorithm )是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群开始的,而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化, 如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来 越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学 的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。 遗传算法程度流程图为: 《一人工智能方向实习一》 实习报告 专业:计算机科学与技术 班级:12419013 学号: 姓名: 江苏科技大学计算机学院 2016年3月 实验一数据聚类分析 一、实验目的 编程实现数据聚类的算法。 二、实验内容 k-means聚类算法。 三、实验原理方法和手段 k-means算法接受参数k ;然后将事先输入的 n个数据对象划分为 k个聚类以便使得 所获得的聚类满足:同一聚类中的对象相似度较高 四、实验条件 Matlab2014b 五、实验步骤 (1)初始化k个聚类中心。 (2)计算数据集各数据到中心的距离,选取到中心距离最短的为该数据所属类别。 (3)计算(2)分类后,k个类别的中心(即求聚类平均距离) (4)继续执行(2)(3)直到k个聚类中心不再变化(或者数据集所属类别不再变化) 六、实验代码 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % mai n.m % k-mea ns algorithm % @author matcloud %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% clear; close all ; load fisheriris ; X = [meas(:,3) meas(:,4)]; figure; plot(X(:,1),X(:,2), 'ko' ,'MarkerSize' ,4); title( 'fisheriris dataset' , 'FontSize' ,18, 'Color' , 'red'); [idx,ctrs] = kmea ns(X,3); figure; subplot(1,2,1); plot(X(idx==1,1),X(idx==1,2), 'ro' , 'MarkerSize' ,4); hold on; ****大学 人工智能基础课程实验报告 (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)估价函数的确定 标准文档 《人工智能》课外实践报告 项目名称:剪枝法五子棋 所在班级: 2013级软件工程一班 小组成员:李晓宁、白明辉、刘小晶、袁成飞、程小兰、李喜林 指导教师:薛笑荣 起止时间: 2016-5-10——2016-6-18 项目基本信息项目名称五子棋 项目简介 智力小游戏作为人们日常休闲娱乐的工具已经深入人们的生活,五子棋更成为了智力游戏的经典,它是基于AI的αβ剪枝法和极小极大值算法实现的人工智能游戏,让人们能和计算机进行对弈。这个项目我们实现了当人点击“开始”按钮时,开始下棋,当人的棋子落时,计算机会根据算法进行最佳路径计算,然后落子下棋。任何一方赢了都会弹出哪方赢了。然后单击重新开始。 任务分工李晓宁 130904021 白明辉 130904001:负责界面实现和估值函数设计文档整理 刘小晶 130904032 袁成飞 130904051:负责极小极大值算法的设计与实现 李喜林 130904019 程小兰 130904004:负责αβ剪枝法的设计与实现 一、系统分析 1.1背景 1.1.1 设计背景 智力小游戏作为人们日常休闲娱乐的工具已经深入人们的生活,五子棋更成为了智力游戏的经典,它是基于AI的αβ剪枝法和极小极大值算法实现的人工智能游戏,让人们能和计算机进行对弈。能使人们在与电脑进行对弈的过程中学习五子棋,陶冶情操。并且推进人们对AI的关注和兴趣。 1.1.2可行性分析 通过研究,本游戏的可行性有以下三方面作保障 (1)技术可行性 本游戏采用Windows xp等等系统作为操作平台,使用人工智能进行算法设计,利用剪枝法进行编写,大大减少了内存容量,而且不用使用数据库,便可操作,方便可行,因此在技术上是可行的。 (2)经济可行性 开发软件:SublimText (3)操作可行性 该游戏运行所需配置低、用户操作界面友好,具有较强的操作可行性。 1.2数据需求 五子棋需要设计如下的数据字段和数据表: 1.2.1 估值函数: 实验一:知识表示方法 一、实验目的 状态空间表示法是人工智能领域最基本的知识表示方法之一,也是进一步学习状态空间搜索策略的基础,本实验通过牧师与野人渡河的问题,强化学生对知识表示的了解和应用,为人工智能后续环节的课程奠定基础。 二、问题描述 有n个牧师和n个野人准备渡河,但只有一条能容纳c个人的小船,为了防止野人侵犯牧师,要求无论在何处,牧师的人数不得少于野人的人数(除非牧师人数为0),且假定野人与牧师都会划船,试设计一个算法,确定他们能否渡过河去,若能,则给出小船来回次数最少的最佳方案。 三、基本要求 输入:牧师人数(即野人人数):n;小船一次最多载人量:c。 输出:若问题无解,则显示Failed,否则,显示Successed输出一组最佳方案。用三元组(X1, X2, X3)表示渡河过程中的状态。并用箭头连接相邻状态以表示迁移过程:初始状态->中间状态->目标状态。 例:当输入n=2,c=2时,输出:221->110->211->010->021->000 其中:X1表示起始岸上的牧师人数;X2表示起始岸上的野人人数;X3表示小船现在位置(1表示起始岸,0表示目的岸)。 要求:写出算法的设计思想和源程序,并以图形用户界面实现人机交互,进行输入和输出结果,如: Please input n: 2 Please input c: 2 Successed or Failed?: Successed Optimal Procedure: 221->110->211->010->021->000 四、实验组织运行要求 本实验采用集中授课形式,每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验。 六、实验代码 Main.cpp #include 人工智能第二次实验报告 一.实验题目: 遗传算法的设计与实现 二.实验目的: 通过人工智能课程的学习,熟悉遗传算法的简单应用。 三.实验内容 用遗传算法求解 f (x) = x2的最大值,x∈[0,31],x取整数。 可以看出该函数比较简单,只要是为了体现遗传算法的思想,在问题选择上,选了一个比较容易实现的,把主要精力放在遗传算法的实现,以及核心思想体会上。 四.实验过程: 1.实现过程 (1)编码 使用二进制编码,随机产生一个初始种群。L 表示编码长度,通常由对问题的求解精度决定,编码长度L 越长,可期望的最优解的精度也就越高,过大的L 会增大运算量。针对该问题进行了简化,因为题设中x∈ [0,31],所以将二进制长度定为5就够用了; (2)生成初始群体 种群规模表示每一代种群中所含个体数目。随机产生N个初始串结构数据,每个串结构数据成为一个个体,N个个体组成一个初始群体,N表示种群规模的大小。当N取值较小时,可提高遗传算法的运算速度,但却降低种群的多样性,容易引起遗传算法早熟,出现假收敛;而N当取值较大时,又会使得遗传算法效率降低。一般建议的取值范围是20—100。 (3)适应度检测 根据实际标准计算个体的适应度,评判个体的优劣,即该个体所代表的可行解的优劣。本例中适应度即为所求的目标函数; (4)选择 从当前群体中选择优良(适应度高的)个体,使它们有机会被选中进入下一次迭代过程,舍弃适应度低的个体。本例中采用轮盘赌的选择方法,即个体被选择的几率与其适应度值大小成正 比; (5)交叉 遗传操作,根据设置的交叉概率对交配池中个体进行基因交叉操作,形成新一代的种群,新一代中间个体的信息来自父辈个体,体现了信息交换的原则。交叉概率控制着交叉操作的频率,由于交叉操作是遗传算法中产生新个体的主要方法,所以交叉概率通常应取较大值;但若过大的话,又可能破坏群体的优良模式。一般取0.4到0.99。 (6)变异 随机选择中间群体中的某个个体,以变异概率大小改变个体某位基因的值。变异为产生新个体提供了机会。变异概率也是影响新个体产生的一个因素,变异概率小,产生新个体少;变异概率太大,又会使遗传算法变成随机搜索。一般取变异概率为0.0001—0.1。 (7)结束条件 当得到的解大于等于900时,结束。从而观看遗传的效率问题。 五.代码及结果: /*遗传算法设计最大值*/ #include 哈工大人工智能导论实验报告 ————————————————————————————————作者:————————————————————————————————日期: 人工智能导论实验报告 学院:计算机科学与技术学院 专业:计算机科学与技术 2016.12.20 目录 人工智能导论实验报告 (3) 一、简介(对该实验背景,方法以及目的的理解) (5) 1.实验背景 (5) 2.实验方法 (5) 3.实验目的 (5) 二、方法(对每个问题的分析及解决问题的方法) (6) Q1: Depth First Search (6) Q2: Breadth First Search (6) Q3: Uniform Cost Search (7) Q4: A* Search (8) Q5: Corners Problem: Representation (8) Q6: Corners Problem: Heuristic (8) Q7: Eating All The Dots: Heuristic (9) Q8: Suboptimal Search (9) 三、实验结果(解决每个问题的结果) (9) Q1: Depth First Search (9) Q2: Breadth First Search (11) Q3: Uniform Cost Search (12) Q4: A* Search (14) Q5: Corners Problem: Representation (15) Q6: Corners Problem: Heuristic (16) Q7: Eating All The Dots: Heuristic (16) Q8: Suboptimal Search (17) 自动评分 (17) 四、总结及讨论(对该实验的总结以及任何该实验的启发) (17) 人工智能实验报告 实验名称:模糊方法实现电热箱的闭环控制实验 模糊逻辑控制(Fuzzy Logic Control)简称模糊控制(Fuzzy Control),是以模糊集合论、模糊语言变量和模糊逻辑推理为基础的一种计算机数字控制技术。1965年,美国的L.A.Zadeh 创立了模糊集合论;1973年他给出了模糊逻辑控制的定义和相关的定理。1974年,英国的E.H.Mamdani首先用模糊控制语句组成模糊控制器,并把它应用于锅炉和蒸汽机的控制,在实验室获得成功。这一开拓性的工作标志着模糊控制论的诞生。 模糊控制实质上是一种非线性控制,从属于智能控制的范畴。模糊控制的一大特点是既具有系统化的理论,又有着大量实际应用背景。模糊控制的发展最初在西方遇到了较大的阻力;然而在东方尤其是在日本,却得到了迅速而广泛的推广应用。近20多年来,模糊控制不论从理论上还是技术上都有了长足的进步,成为自动控制领域中一个非常活跃而又硕果累累的分支。其典型应用的例子涉及生产和生活的许多方面,例如在家用电器设备中有模糊洗衣机、空调、微波炉、吸尘器、照相机和摄录机等;在工业控制领域中有水净化处理、发酵过程、化学反应釜、水泥窑炉等的模糊控制;在专用系统和其它方面有地铁靠站停车、汽车驾驶、电梯、自动扶梯、蒸汽引擎以及机器人的模糊控制等。 模糊控制是以模糊集合论、模糊语言变量和模糊逻辑推理为基础的微机数字控制。它能模拟人的思维,构成一种非线性控制,以满足复杂的、不确定的过程控制的需要,是一种典型的智能控制。模糊控制系统类似于常规的微机控制系统,如下图所示: 图1 模糊控制系统的构成图 一、实验目的 1. 学习由已知对象建立一个双入单出模糊控制器; 2. 掌握利用模糊控制器实现温度控制的方法。 二、实验原理及内容 模糊控制器最常用的都是二维的,其输入变量有两个(X1,X2),输出变量只有一个(Y)。在实际控制系统中,X1一般取为误差信号,X2一般取误差的变化,由于同时考虑到误差和误差变化的影响,所以才能保证系统稳定,不致于产生振荡。模糊控制系统的方框图如下图所示: 暨南大学人工智能实验报告 题目:动物识别系统 院系:信科院计算机系 一、目的与要求 1.掌握人工智能的知识表示技术,能用产生式表示法表示知识,并实现一个用于识别的专家系统。 2.推理策略采用正向推理和反向推理两种。 事实可看成是断言一个语言变量的值或是多个语言变量间的关系的陈述句,语言变量的值或语言变量间的关系可以是一个词。不一定是数字。一般使用三元组(对象,属性,值)或(关系,对象1,对象2)来表示事实,其中对象就是语言变量,若考虑不确定性就成了四元组表示(增加可信度)。这种 表示的机器内部实现就是一个表。 如事实“老李年龄是35岁”,便写成(Lee,age,35) 事实“老李、老张是朋友”,可写成(friend,Lee,Zhang)2.规则的表示: 、 是精确的,而产生式的匹配可以是不确定的,原因是产生式的前提条件和结论都可以是不确定的,因此其匹配也可以是不确定的。 3.产生式系统的结构: 3. 3.3推理机 推理机是一个解释程序,控制协同规则库与数据库,负责整个产生式系统的运行,决定问题求解过程的推理路线,实现对问题的求解。 推理机主要包括下面一些工作内容: (1)按一定策略从规则库中选择规则与数据库的已知事实进行匹配。匹配的过程中会产生三种情况。第一种匹配成功,则此条规则将被列入被激活候选集;第二种匹配失败,即输入条件与已知条件矛盾;第三种匹配无结果,即该条规则前件的已知条件中完全与输入事实无关,则将规则列入待测试规则集,将在下一轮匹配中再次使用。因为有可能推理中间结果符合其前件的已知 正向推理是从已知事实出发,通过规则库求的结论,也称为自底向上,或称为数据驱动方式。 正向推理过程的具体步骤是:人工智能实验报告大全
游戏人工智能实验报告记录四
人工智能实验报告
游戏人工智能实验报告四
(完整word版)哈工大人工智能导论实验报告
人工智能实验报告大全
人工智能实验报告
人工智能实验报告
人工智能导论1-4章作业
人工智能导论实验
人工智能实验报告
人工智能遗传算法实验报告
人工智能实验报告
人工智能实验报告
人工智能实验报告材料
人工智能_实验报告
//船 class Boat { public: static int c; int pastor;//牧师 int savage;//野人 Boat(int pastor, int savage); }; //河岸状态 class State
人工智能实验报告文件.doc
哈工大人工智能导论实验报告
人工智能实验报告
人工智能实验报告