人工智能-与或图搜索解决梵塔-代码C语言版0001

1、与或图搜索解决梵塔#include "stda仅.h"#define STACKs 100#define STACKsr 10#include "malloc.h"typedef struct Openint n;要移动的盘数int start;/ 开始杆号int middle;/过度杆号int end;/ 目标杆号int son;/子问题解决个数，0都未解决，3都解决Open* father;/ 父节点OPen,*OPEN;定义栈typedef structOPEN *base;/ 在栈构造之前和销毁之后，base的值为NULL;OPEN *top;/

2、 栈顶指针int stacksize;/当前已分配的存储空间，以 Open结构体地址为单位。SqStack;/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(SqStack &

3、amp;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;/Push int Pop(SqStack &s,OPEN &e)/ 从 open 表头部删除该节点if(s.top=s.base)re

4、turn 0;e=*-s.top;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

5、);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);doGetTop(S,p);if(p->n=1)终点问题的解(只移动一个盘子)i+;if(p->father)(p->father->son)+;printf("第-5 步：杆 to 杆 dn",i,p->start,p->end);

6、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->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->

7、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;测试结果：口 :亨可资b£q 1 2A 工专福实班 '.rgyL h'j D ebu gYg/uhuQjewet niye杆mr-on