人工智能與或圖搜索解決梵塔代碼C語言版

1、與或圖搜索解決梵塔#include "stdafx.h"#define STACKs 100#define STACKsr 10#include "malloc.h"typedef struct Openint n;/要移動的盤數(shù)int start;/開始桿號int middle;/過度桿號int end;/目標桿號int son;/子問題解決個數(shù)，0都未解決，3都解決Open* father;/父節(jié)點OPen,*OPEN;/定義棧typedef structOPEN *base;/在棧構(gòu)造之前和銷毀之后，base的值為NULL;OPEN *top;/棧

2、頂指針int stacksize;/當前已分配的存儲空間，以O(shè)pen結(jié)構(gòu)體地址為單位。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結(jié)構(gòu)體if(s.top=s.base)return 0;e=*(s.top-1);ret

3、urn 1;int Push(SqStack &s,OPEN e)/將擴展結(jié)點添加到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表頭部刪除該節(jié)點

4、if(s.top=s.base)return 0;e=*-s.top;return 1;/Popint main()int n,k,m,z;/int i=0;/聲明問題解決步驟printf("請輸入盤的個數(shù):");scanf("%d",&n);printf("請輸入開始桿號:");scanf("%d",&k);printf("請輸入目標桿號:");scanf("%d",&m);printf("請輸入中間桿號:");scanf(&qu

5、ot;%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);doGetTop(S,p);if(p->n=1)/終點問題的解（只移動一個盤子）i+;if(p->father)(p->father->son)+;printf("第%-5d步: 桿%d to 桿%dn",i,

6、p->start,p->end);Pop(S,p);if(GetTop(S,p)if(p->son=3)/所有子問題都解決了，父節(jié)點標記加1，刪除該節(jié)點if(p->father)(p->father->son)+;Pop(S,r);if(GetTop(S,p)if(p->son<3&&p->n>1)/將問題等價分解成更易解決的子問題/擴展未解決節(jié)點，擴展成如下3個子節(jié)點r=NULL;r=(OPEN)malloc(sizeof(OPen);r->son=0;r->father=p;r->n=p->

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