c++八数码A*算法求解

// //============================================================================== // 8数码问题求解 // 武汉理工0702（研）人工智能结业设计 // 指导老师：彭德威 编程：龙振海 // 完成日期：2008.1.25 //============================================================================== #include <iostream> #include "math.h" #include "windows.h" using namespace std; class List; class Node//8数码结点 { private: int nValue[3][3]; int nzX; int nzY; int hf; Node *parent; Node *child; public: Node(Node *parent=NULL,Node *child=NULL):parent(parent),child(child) { } void giveHf(int i) { hf=i; } int getHf() { return hf; } void giveValue(int i,int j,int value) { nValue[i][j]=value; } int nGetValue(int i,int j) { return nValue[i][j]; } void giveZx(int x) { nzX=x; } int getZx() { return nzX; } void giveZy(int y) { nzY=y; } int getZy() { return nzY; } void show() { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { int tmp=0; tmp=nValue[i][j]; if(tmp==0) { cout<<" "; } else { cout<<nValue[i][j]<<" "; } } cout<<endl<<endl<<endl<<endl<<endl; } } }; class listNode//open表结点 { private: int nGrade; listNode *right; listNode *down; listNode *up; listNode *parent; listNode *child; List * lup; Node node; public: listNode(listNode *parent=NULL,listNode *child=NULL,listNode *right=NULL,listNode *down=NULL,listNode *up=NULL,List *lup=NULL):right(right),down(down),up(up),lup(lup),parent(parent),child(child) { } void giveParent(listNode *parent) { this->parent=parent; } void giveChild(listNode * child) { this->child=child; } listNode * getChild() { return child; } listNode * getParent() { return parent; } void giveLup(List *l) { lup=l; } List * getLup() { return lup; } void giveNode(Node &node) { this->node=new Node(); this->node.giveZx(node.getZx()); this->node.giveZy(node.getZy()); this->node.giveHf(node.getHf()); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { this->node.giveValue(i,j,node.nGetValue(i,j)); } } } void giveRight(listNode *listNode) { right =listNode; } void giveDown(listNode *listNode) { down=listNode; } Node getNode() { return node; } listNode * getRight() { return right; } listNode * getDown() { return down; } listNode * getUp() { return up; } void giveUp(listNode *listNode) { up=listNode; } void giveGrade(int i) { nGrade=i; } int getGrade() { return nGrade; } }; class List//open表 { private: List *right; listNode *down; int nGrade; public: List(List *r=NULL,listNode *d=NULL):down(d),right(r) { } List* getRight() { return right; } void giveRight(List *l) { right=l; } listNode * getDown() { return down; } void giveDown(listNode *n) { down=n; } void giveGrade(int i) { nGrade=i; } int getGrade() { return nGrade; } }; class Close//close表 { private: Close * next; listNode * lnode; public: Close(Close * next=NULL,listNode *lnode=NULL):next(next),lnode(lnode) { } void giveNext(Close * next) { this->next=next; } void giveLnode(listNode *lnode) { this->lnode=lnode; } Close * getNext() { return next; } listNode * getLnode() { return lnode; } }; List * listInc(List * head)//扩充表 { List *l=new List(); l->giveGrade(head->getGrade()+1); l->giveRight(head); head=l; return head; } int hFunction(Node nNode ,Node nEnd,int nGrade)//启发函数 { int res=nGrade%12; //(2/(nGrade+1))*nGrade; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { for(int l=0;l<3;l++) { for(int m=0;m<3;m++) { if(nNode.nGetValue(i,j)==nEnd.nGetValue(l,m)) { res+=(abs(i-l)+abs(j-m)); continue; } } } } } return res; } void listNodeCopy(listNode *n,listNode *m)//表结点复制 { n->giveGrade(m->getGrade()); n->giveRight(m->getRight()); n->giveLup(m->getLup()); n->giveDown(m->getDown()); n->giveUp(m->getUp()); n->giveNode(m->getNode()); } void nodeCopy(Node &n,Node m)//结点复制 { n.giveHf(m.getHf()); n.giveZx(m.getZx()); n.giveZy(m.getZy()); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { n.giveValue(i,j,m.nGetValue(i,j)); } } } void addNode(List *head ,listNode *ln,listNode *tmp,Close *c)//往open表中添加结点 { List *ltmp=head; if(tmp!=NULL) { Close *ctmp=c; while(ctmp!=NULL) { if(hFunction(ctmp->getLnode()->getNode(),ln->getNode(),0)==0) { return; } ctmp=ctmp->getNext(); } } List *tmpr=head; while(tmpr->getGrade()!=ln->getGrade()) { tmpr=tmpr->getRight(); } listNode *tmpd=tmpr->getDown(); if(tmpd==NULL) { tmpr->giveDown(new listNode()); listNodeCopy(tmpr->getDown(),ln); tmpr->getDown()->giveLup(tmpr); tmpr->getDown()->giveRight(NULL); tmpr->getDown()->giveParent(tmp); } else { while(tmpd!=NULL) { if(tmpd->getNode().getHf()>ln->getNode().getHf()) { if(tmpd->getLup()!=NULL) { tmpd->giveUp(new listNode()); listNodeCopy(tmpd->getUp(),ln); tmpd->getUp()->giveLup(tmpd->getLup ()); tmpd->getLup()->giveDown(tmpd->getUp ()); tmpd->getUp()->giveDown(tmpd); tmpd->giveLup(NULL); tmpd->getUp()->giveParent(tmp); } else { tmpd->getUp()->giveDown(new listNode()); tmpd->getUp()->getDown()->giveDown(tmpd); tmpd->getUp()->getDown()->giveUp(tmpd->getUp ()); tmpd->giveUp(tmpd->getUp()->getDown()); listNodeCopy(tmpd->getUp(),ln); tmpd->getUp()->giveParent(tmp); } break; } else if(tmpd->getNode().getHf()==ln->getNode().getHf()) { if(tmpd->getLup()!=NULL) { tmpd->giveUp(new listNode()); tmpd->getUp()->giveRight(tmpd->getRight()); tmpd->giveRight(tmpd->getUp()); tmpd->giveUp(NULL); listNodeCopy(tmpd->getRight(),ln); tmpd->getRight()->giveParent(tmp); } else { listNode *t =tmpd; while(t->getRight()!=NULL) { t=t->getRight(); } t->giveRight(new listNode()); listNodeCopy(t->getRight(),ln); t->getRight()->giveParent(tmp); } break; } else if(tmpd->getNode().getHf()<ln->getNode().getHf()) { if(tmpd->getDown()==NULL) { tmpd->giveDown(new listNode()); listNodeCopy(tmpd->getDown(),ln); tmpd->getDown()->giveUp(tmpd); tmpd->getDown()->giveParent(tmp); break; } else { tmpd=tmpd->getDown(); } } } } } listNode *delNode(List *head)//从open表中删除最优结点 { List *tmp=head; while(1) { if(tmp->getDown()==NULL) { tmp=tmp->getRight(); } else { break; } } listNode *res=tmp->getDown(); int ntmp=res->getNode().getHf()+1; while((tmp)!=NULL) { if(tmp->getDown()!=NULL) { if(ntmp>tmp->getDown()->getNode().getHf()) { ntmp=tmp->getDown()->getNode().getHf(); res=tmp->getDown(); } tmp=tmp->getRight(); } else { tmp=tmp->getRight(); } } if(res->getRight()!=NULL&&res->getDown()==NULL)// { res->getLup()->giveDown(res->getRight()); res->getRight()->giveLup(res->getLup()); res->giveLup(NULL); res->giveRight(NULL); } else if(res->getDown()!=NULL&&res->getRight()==NULL) { res->getLup()->giveDown(res->getDown()); res->getDown()->giveUp(NULL); res->getDown()->giveLup(res->getLup()); res->giveLup