人工智能-与或图搜索解决梵塔-代码C语言版(共4页).doc

《人工智能-与或图搜索解决梵塔-代码C语言版(共4页).doc》由会员分享，可在线阅读，更多相关《人工智能-与或图搜索解决梵塔-代码C语言版(共4页).doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上与或图搜索解决梵塔#include stdafx.h#define STACKs 100#define STACKsr 10#include malloc.htypedef struct Openint n;/要移动的盘数int start;/开始杆号int middle;/过度杆号int end;/目标杆号int son;/子问题解决个数，0都未解决，3都解决Open* father;/父节点OPen,*OPEN;/定义栈typedef structOPEN *base;/在栈构造之前和销毁之后，base的值为NULL;OPEN *top;/栈顶指针int stac

2、ksize;/当前已分配的存储空间，以Open结构体地址为单位。SqStack;int InitStack(SqStack &s)/s.base=(OPEN*)malloc(STACKs*sizeof(OPEN);/栈中存放OPEN指针if(!s.base)return 0;s.top=s.base;s.stacksize=STACKs;return 1;/InitStack*/int GetTop(SqStack s,OPEN &e)/返回当前问题的指针，指向OPen结构体if(s.top=s.base)return 0;e=*(s.top-1);return 1;int Push(SqSt

3、ack &s,OPEN e)/将扩展结点添加到open表中（即栈）if(s.top-s.base=s.stacksize)/如果当前栈已满，扩展栈容量s.base=(OPEN*)realloc(s.base,(STACKs+STACKsr)*sizeof(OPEN);if(!s.base)return 0;s.top=s.base+s.stacksize;s.stacksize+=STACKsr;*s.top+=e;return 1;/Pushint Pop(SqStack &s,OPEN &e)/从open表头部删除该节点if(s.top=s.base)return 0;e=*-s.top;

4、return 1;/Popint main()int n,k,m,z;/int i=0;/声明问题解决步骤printf(请输入盘的个数:);scanf(%d,&n);printf(请输入开始杆号:);scanf(%d,&k);printf(请输入目标杆号:);scanf(%d,&m);printf(请输入中间杆号:);scanf(%d,&z);OPEN q,p,r;SqStack S;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

5、);doGetTop(S,p);if(p-n=1)/终点问题的解（只移动一个盘子）i+;if(p-father)(p-father-son)+;printf(第%-5d步: 杆%d to 杆%dn,i,p-start,p-end);Pop(S,p);if(GetTop(S,p)if(p-son=3)/所有子问题都解决了，父节点标记加1，删除该节点if(p-father)(p-father-son)+;Pop(S,r);if(GetTop(S,p)if(p-sonn1)/将问题等价分解成更易解决的子问题/扩展未解决节点，扩展成如下3个子节点r=NULL;r=(OPEN)malloc(sizeof

6、(OPen);r-son=0;r-father=p;r-n=p-n-1;r-start=p-middle;r-end=p-end;r-middle=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);while(S.top!=S.base);/当open表空时，结束return 0;测试结果：专心-专注-专业