资源描述：
《人工智能 与或图搜索解决梵塔 代码c语言版》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、与或图搜索解决梵塔#include"stdafx.h"#defineSTACKs100#defineSTACKsr10#include"malloc.h"typedefstructOpen{intn;//要移动的盘数intstart;//开始杆号intmiddle;//过度杆号intend;//目标杆号intson;//子问题解决个数，0都未解决，3都解决Open*father;//父节点}OPen,*OPEN;//定义栈typedefstruct{OPEN*base;//在栈构造之前和销毁之后，base的值为NULL;OPEN*top;/
2、/栈顶指针intstacksize;//当前已分配的存储空间，以Open结构体地址为单位。}SqStack;intInitStack(SqStack&s){//s.base=(OPEN*)malloc(STACKs*sizeof(OPEN));//栈中存放OPEN指针if(!s.base)return0;s.top=s.base;s.stacksize=STACKs;return1;}//InitStack*/intGetTop(SqStacks,OPEN&e){//返回当前问题的指针，指向OPen结构体if(s.top==s.base)r
3、eturn0;e=*(s.top-1);return1;}intPush(SqStack&s,OPENe){//将扩展结点添加到open表中（即栈）if(s.top-s.base>=s.stacksize){//如果当前栈已满，扩展栈容量s.base=(OPEN*)realloc(s.base,(STACKs+STACKsr)*sizeof(OPEN));if(!s.base)return0;s.top=s.base+s.stacksize;s.stacksize+=STACKsr;}*s.top++=e;return1;}//Pushin
4、tPop(SqStack&s,OPEN&e){//从open表头部删除该节点if(s.top==s.base)return0;e=*--s.top;return1;}//Popintmain(){intn,k,m,z;//inti=0;//声明问题解决步骤printf("请输入盘的个数:");scanf("%d",&n);printf("请输入开始杆号:");scanf("%d",&k);printf("请输入目标杆号:");scanf("%d",&m);printf("请输入中间杆号:");scanf("%d",&z);OPENq,p,r
5、;SqStackS;InitStack(S);q=(OPEN)malloc(sizeof(OPen));q->son=0;q->n=n;q->end=m;q->start=k;q->father=NULL;q->middle=z;Push(S,q);do{GetTop(S,p);if(p->n==1){//终点问题的解（只移动一个盘子）i++;if(p->father){(p->father->son)++;}printf("第%-5d步:杆%dto杆%d",i,p->start,p->end);Pop(S,p);}if(GetTop(
6、S,p)){if(p->son==3){//所有子问题都解决了，父节点标记加1，删除该节点if(p->father){(p->father->son)++;}Pop(S,r);}}if(GetTop(S,p)){if(p->son<3&&p->n>1){//将问题等价分解成更易解决的子问题//扩展未解决节点，扩展成如下3个子节点r=NULL;r=(OPEN)malloc(sizeof(OPen));r->son=0;r->father=p;r->n=p->n-1;r->start=p->middle;r->end=p->end;r->mid
7、dle=p->start;Push(S,r);r=(OPEN)malloc(sizeof(OPen));r->son=0;r->father=p;r->n=1;r->start=p->start;r->end=p->end;r->middle=p->middle;Push(S,r);r=(OPEN)malloc(sizeof(OPen));r->son=0;r->father=p;r->start=p->start;r->end=p->middle;r->middle=p->end;r->n=p->n-1;Push(S,r);}}}whil
8、e(S.top!=S.base);//当open表空时，结束return0;}测试结果：
