九宫问题.docx
《九宫问题.docx》由会员分享,可在线阅读,更多相关《九宫问题.docx(21页珍藏版)》请在冰点文库上搜索。
九宫问题
(十一)九宫问题)
题目叙述:
九宫问题又称“八数码问题”,是说在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,从某种初始状态开始,对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态变换至目标状态。
求其最少步数。
/*****************************/
/*EIGHTDIGITPROBLEM*/
/*唐国峰2012年4月23日*/
//预编译命令
#include"iostream"
#include"stdlib.h"
usingnamespacestd;
//棋盘大小
#definesize3
//定义二维数组来存储数据表示某一个特定状态
typedefintstatus[size][size];
//定义状态图中的节点数据结构,即节点的状态信息等
typedefstructNode
{
statusdata;//节点所存储的状态
structNode*parent;//指向节点的父亲节点
structSpringLink*child;//指向节点的后继节点
structNode*next;//指向链表的后一个节点
intf_value;//由初始状态经由当前节点至目标状态的总耗散值
intg_value;//由初始状态经到当前节点实际耗散值
inth_value;//由当前节点到目标状态的预计耗散值
}NNode,*PNode;
//定义表述指向当前节点的扩展节点的链表
typedefstructSpringLink
structNode*pointData;//指向节点的指针
structSpringLink*next;//指向当前节点的其他扩展节点
}SPLink,*PSPLink;
//声明OPEN表和CLOSED表
PNodeopen;
PNodeclosed;
//计算棋盘状态的逆序数
intInverseNumber(statusa)
inti,j,sum=0;
intdata_chang[size*size]={0};
//将二维数组转换成一维数组,以方便求逆序数
for(i=0;i{for(j=0;j{data_chang[i*size+j]=a[i][j];}} //计算序列中除零外的逆序数for(i=0;i<=size*size;i++){if(data_chang[i]!=0){//要比较多少次,从最后一个元素开始比较for(j=i;j>=0;j--){//当后一个数比前一个数小时if(data_chang[i]{sum++;}}}}returnsum;} //判断是否存在解决方案boolhasSolution(statusstartStatus,statustargetStatus){intstartInverseNumber=InverseNumber(startStatus);inttatgetInverseNumber=InverseNumber(targetStatus); //判断初始状态和目标状态除零外的序列逆序数奇偶性,相同则可求值,不同则不可求if((startInverseNumber%2)!=(tatgetInverseNumber%2)){returnfalse;}else{returntrue;}} //初始化一个空链表voidinitLink(PNode&Head){Head=(PNode)malloc(sizeof(NNode));Head->next=NULL;} //判断链表是否为空boolisEmpty(PNodeHead){if(Head->next==NULL){returntrue;}else{returnfalse;}} //从链表中拿出一个数据voidpopNode(PNode&Head,PNode&FNode){if(isEmpty(Head)){FNode=NULL;return;}FNode=Head->next;Head->next=Head->next->next;FNode->next=NULL;} //向节点的最终后继节点链表中添加新的子节点voidaddSpringNode(PNode&Head,PNodenewData){PSPLinknewNode=(PSPLink)malloc(sizeof(SPLink));newNode->pointData=newData; newNode->next=Head->child;Head->child=newNode;} //释放状态图中存放节点后继节点地址的空间voidfreeSpringLink(PSPLink&Head){PSPLinktmm; while(Head!=NULL){tmm=Head;Head=Head->next;free(tmm);}} //释放open表与closed表中的资源voidfreeLink(PNode&Head){PNodetmn; tmn=Head;Head=Head->next;free(tmn); while(Head!=NULL){//首先释放存放节点后继节点地址的空间freeSpringLink(Head->child);tmn=Head;Head=Head->next;free(tmn);}} //向普通链表中添加一个节点voidaddNode(PNode&Head,PNode&newNode){newNode->next=Head->next;Head->next=newNode;} //向非递减排列的链表中添加一个节点voidaddAscNode(PNode&Head,PNode&newNode){PNodeP;PNodeQ; P=Head->next;Q=Head;while(P!=NULL&&P->f_valuef_value){Q=P;P=P->next;}//上面判断好位置之后,下面就是简单的插入节点了newNode->next=Q->next;Q->next=newNode;} //计算节点到目标状态的预计耗散值intcomputeh_value(PNodetheNode,statustargetStatus){intnum=0;for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(theNode->data[i][j]!=targetStatus[i][j]){num++;}}}returnnum;} //计算节点的f,g,h值voidcomputeAllValue(PNode&theNode,PNodeparentNode,statustargetStatus){if(parentNode==NULL){theNode->g_value=0;}else{theNode->g_value=parentNode->g_value+1;} theNode->h_value=computeh_value(theNode,targetStatus);theNode->f_value=theNode->g_value+theNode->h_value;} //初始化函数,进行算法初始条件的设置voidinitial(statusstartStatus,statustargetStatus){//初始化open以及closed表initLink(open);initLink(closed); //初始化起始节点,令初始节点的父节点为空节点PNodeNULLNode=NULL;PNodeStartNode=(PNode)malloc(sizeof(NNode));for(inti=0;i<3;i++){for(intj=0;j<3;j++){StartNode->data[i][j]=startStatus[i][j];}}StartNode->parent=NULL;StartNode->child=NULL;StartNode->next=NULL;computeAllValue(StartNode,NULLNode,targetStatus); //起始节点进入OPEN表addAscNode(open,StartNode);} //将B节点的状态赋值给A节点voidstatusAEB(PNode&ANode,PNodeBNode){for(inti=0;i<3;i++){for(intj=0;j<3;j++){ANode->data[i][j]=BNode->data[i][j];}}} //两个节点是否有相同的状态boolhasSameStatus(PNodeANode,PNodeBNode){for(inti=0;i{for(intj=0;j{if(ANode->data[i][j]!=BNode->data[i][j])returnfalse;}}returntrue;} //节点与其祖先节点是否有相同的状态boolhasAnceSameStatus(PNodeOrigiNode,PNodeAnceNode){while(AnceNode!=NULL){if(hasSameStatus(OrigiNode,AnceNode))returntrue;AnceNode=AnceNode->parent;}returnfalse;} //取得方格中空的格子的位置voidgetPosition(PNodetheNode,int&row,int&col){for(inti=0;i{for(intj=0;j{if(theNode->data[i][j]==0){row=i;col=j;return;}}}} //交换两个数字的值voidchangeAB(int&a,int&b){intc;c=b;b=a;a=c;} //检查相应的状态是否在某一个链表中boolinLink(PNodespciNode,PNodetheLink,PNode&theNodeLink,PNode&preNode){preNode=theLink;theLink=theLink->next; while(theLink!=NULL){if(hasSameStatus(spciNode,theLink)){theNodeLink=theLink;returntrue;}preNode=theLink;theLink=theLink->next;}returnfalse;} //产生节点的后继节点链表voidSpringLink(PNodetheNode,PNode&spring,statustargetStatus){introw;intcol; getPosition(theNode,row,col); //空的格子右边的格子向左移动if(col!=2){PNoderlNewNode=(PNode)malloc(sizeof(NNode));statusAEB(rlNewNode,theNode);changeAB(rlNewNode->data[row][col],rlNewNode->data[row][col+1]);if(hasAnceSameStatus(rlNewNode,theNode->parent)){free(rlNewNode);//与父辈相同,丢弃本节点}else{rlNewNode->parent=theNode;rlNewNode->child=NULL;rlNewNode->next=NULL;computeAllValue(rlNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,rlNewNode);}}//空的格子左边的格子向右移动if(col!=0){PNodelrNewNode=(PNode)malloc(sizeof(NNode));statusAEB(lrNewNode,theNode);changeAB(lrNewNode->data[row][col],lrNewNode->data[row][col-1]);if(hasAnceSameStatus(lrNewNode,theNode->parent)){free(lrNewNode);//与父辈相同,丢弃本节点}else{lrNewNode->parent=theNode;lrNewNode->child=NULL;lrNewNode->next=NULL;computeAllValue(lrNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,lrNewNode);}}//空的格子上边的格子向下移动if(row!=0){PNodeudNewNode=(PNode)malloc(sizeof(NNode));statusAEB(udNewNode,theNode);changeAB(udNewNode->data[row][col],udNewNode->data[row-1][col]);if(hasAnceSameStatus(udNewNode,theNode->parent)){free(udNewNode);//与父辈相同,丢弃本节点}else{udNewNode->parent=theNode;udNewNode->child=NULL;udNewNode->next=NULL;computeAllValue(udNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,udNewNode);}}//空的格子下边的格子向上移动if(row!=2){PNodeduNewNode=(PNode)malloc(sizeof(NNode));statusAEB(duNewNode,theNode);changeAB(duNewNode->data[row][col],duNewNode->data[row+1][col]);if(hasAnceSameStatus(duNewNode,theNode->parent)){free(duNewNode);//与父辈相同,丢弃本节点}else{duNewNode->parent=theNode;duNewNode->child=NULL;duNewNode->next=NULL;computeAllValue(duNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,duNewNode);}}} //输出给定节点的状态voidoutputStatus(PNodestat){for(inti=0;i<3;i++){for(intj=0;j<3;j++){cout<data[i][j]<<"";}cout<}} //输出最佳的路径voidoutputBestRoad(PNodegoal){intdeepnum=goal->g_value; if(goal->parent!=NULL){outputBestRoad(goal->parent);}cout<<"第"<"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
for(j=0;j{data_chang[i*size+j]=a[i][j];}} //计算序列中除零外的逆序数for(i=0;i<=size*size;i++){if(data_chang[i]!=0){//要比较多少次,从最后一个元素开始比较for(j=i;j>=0;j--){//当后一个数比前一个数小时if(data_chang[i]{sum++;}}}}returnsum;} //判断是否存在解决方案boolhasSolution(statusstartStatus,statustargetStatus){intstartInverseNumber=InverseNumber(startStatus);inttatgetInverseNumber=InverseNumber(targetStatus); //判断初始状态和目标状态除零外的序列逆序数奇偶性,相同则可求值,不同则不可求if((startInverseNumber%2)!=(tatgetInverseNumber%2)){returnfalse;}else{returntrue;}} //初始化一个空链表voidinitLink(PNode&Head){Head=(PNode)malloc(sizeof(NNode));Head->next=NULL;} //判断链表是否为空boolisEmpty(PNodeHead){if(Head->next==NULL){returntrue;}else{returnfalse;}} //从链表中拿出一个数据voidpopNode(PNode&Head,PNode&FNode){if(isEmpty(Head)){FNode=NULL;return;}FNode=Head->next;Head->next=Head->next->next;FNode->next=NULL;} //向节点的最终后继节点链表中添加新的子节点voidaddSpringNode(PNode&Head,PNodenewData){PSPLinknewNode=(PSPLink)malloc(sizeof(SPLink));newNode->pointData=newData; newNode->next=Head->child;Head->child=newNode;} //释放状态图中存放节点后继节点地址的空间voidfreeSpringLink(PSPLink&Head){PSPLinktmm; while(Head!=NULL){tmm=Head;Head=Head->next;free(tmm);}} //释放open表与closed表中的资源voidfreeLink(PNode&Head){PNodetmn; tmn=Head;Head=Head->next;free(tmn); while(Head!=NULL){//首先释放存放节点后继节点地址的空间freeSpringLink(Head->child);tmn=Head;Head=Head->next;free(tmn);}} //向普通链表中添加一个节点voidaddNode(PNode&Head,PNode&newNode){newNode->next=Head->next;Head->next=newNode;} //向非递减排列的链表中添加一个节点voidaddAscNode(PNode&Head,PNode&newNode){PNodeP;PNodeQ; P=Head->next;Q=Head;while(P!=NULL&&P->f_valuef_value){Q=P;P=P->next;}//上面判断好位置之后,下面就是简单的插入节点了newNode->next=Q->next;Q->next=newNode;} //计算节点到目标状态的预计耗散值intcomputeh_value(PNodetheNode,statustargetStatus){intnum=0;for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(theNode->data[i][j]!=targetStatus[i][j]){num++;}}}returnnum;} //计算节点的f,g,h值voidcomputeAllValue(PNode&theNode,PNodeparentNode,statustargetStatus){if(parentNode==NULL){theNode->g_value=0;}else{theNode->g_value=parentNode->g_value+1;} theNode->h_value=computeh_value(theNode,targetStatus);theNode->f_value=theNode->g_value+theNode->h_value;} //初始化函数,进行算法初始条件的设置voidinitial(statusstartStatus,statustargetStatus){//初始化open以及closed表initLink(open);initLink(closed); //初始化起始节点,令初始节点的父节点为空节点PNodeNULLNode=NULL;PNodeStartNode=(PNode)malloc(sizeof(NNode));for(inti=0;i<3;i++){for(intj=0;j<3;j++){StartNode->data[i][j]=startStatus[i][j];}}StartNode->parent=NULL;StartNode->child=NULL;StartNode->next=NULL;computeAllValue(StartNode,NULLNode,targetStatus); //起始节点进入OPEN表addAscNode(open,StartNode);} //将B节点的状态赋值给A节点voidstatusAEB(PNode&ANode,PNodeBNode){for(inti=0;i<3;i++){for(intj=0;j<3;j++){ANode->data[i][j]=BNode->data[i][j];}}} //两个节点是否有相同的状态boolhasSameStatus(PNodeANode,PNodeBNode){for(inti=0;i{for(intj=0;j{if(ANode->data[i][j]!=BNode->data[i][j])returnfalse;}}returntrue;} //节点与其祖先节点是否有相同的状态boolhasAnceSameStatus(PNodeOrigiNode,PNodeAnceNode){while(AnceNode!=NULL){if(hasSameStatus(OrigiNode,AnceNode))returntrue;AnceNode=AnceNode->parent;}returnfalse;} //取得方格中空的格子的位置voidgetPosition(PNodetheNode,int&row,int&col){for(inti=0;i{for(intj=0;j{if(theNode->data[i][j]==0){row=i;col=j;return;}}}} //交换两个数字的值voidchangeAB(int&a,int&b){intc;c=b;b=a;a=c;} //检查相应的状态是否在某一个链表中boolinLink(PNodespciNode,PNodetheLink,PNode&theNodeLink,PNode&preNode){preNode=theLink;theLink=theLink->next; while(theLink!=NULL){if(hasSameStatus(spciNode,theLink)){theNodeLink=theLink;returntrue;}preNode=theLink;theLink=theLink->next;}returnfalse;} //产生节点的后继节点链表voidSpringLink(PNodetheNode,PNode&spring,statustargetStatus){introw;intcol; getPosition(theNode,row,col); //空的格子右边的格子向左移动if(col!=2){PNoderlNewNode=(PNode)malloc(sizeof(NNode));statusAEB(rlNewNode,theNode);changeAB(rlNewNode->data[row][col],rlNewNode->data[row][col+1]);if(hasAnceSameStatus(rlNewNode,theNode->parent)){free(rlNewNode);//与父辈相同,丢弃本节点}else{rlNewNode->parent=theNode;rlNewNode->child=NULL;rlNewNode->next=NULL;computeAllValue(rlNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,rlNewNode);}}//空的格子左边的格子向右移动if(col!=0){PNodelrNewNode=(PNode)malloc(sizeof(NNode));statusAEB(lrNewNode,theNode);changeAB(lrNewNode->data[row][col],lrNewNode->data[row][col-1]);if(hasAnceSameStatus(lrNewNode,theNode->parent)){free(lrNewNode);//与父辈相同,丢弃本节点}else{lrNewNode->parent=theNode;lrNewNode->child=NULL;lrNewNode->next=NULL;computeAllValue(lrNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,lrNewNode);}}//空的格子上边的格子向下移动if(row!=0){PNodeudNewNode=(PNode)malloc(sizeof(NNode));statusAEB(udNewNode,theNode);changeAB(udNewNode->data[row][col],udNewNode->data[row-1][col]);if(hasAnceSameStatus(udNewNode,theNode->parent)){free(udNewNode);//与父辈相同,丢弃本节点}else{udNewNode->parent=theNode;udNewNode->child=NULL;udNewNode->next=NULL;computeAllValue(udNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,udNewNode);}}//空的格子下边的格子向上移动if(row!=2){PNodeduNewNode=(PNode)malloc(sizeof(NNode));statusAEB(duNewNode,theNode);changeAB(duNewNode->data[row][col],duNewNode->data[row+1][col]);if(hasAnceSameStatus(duNewNode,theNode->parent)){free(duNewNode);//与父辈相同,丢弃本节点}else{duNewNode->parent=theNode;duNewNode->child=NULL;duNewNode->next=NULL;computeAllValue(duNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,duNewNode);}}} //输出给定节点的状态voidoutputStatus(PNodestat){for(inti=0;i<3;i++){for(intj=0;j<3;j++){cout<data[i][j]<<"";}cout<}} //输出最佳的路径voidoutputBestRoad(PNodegoal){intdeepnum=goal->g_value; if(goal->parent!=NULL){outputBestRoad(goal->parent);}cout<<"第"<"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
data_chang[i*size+j]=a[i][j];
}
//计算序列中除零外的逆序数
for(i=0;i<=size*size;i++)
if(data_chang[i]!
=0)
//要比较多少次,从最后一个元素开始比较
for(j=i;j>=0;j--)
//当后一个数比前一个数小时
if(data_chang[i]{sum++;}}}}returnsum;} //判断是否存在解决方案boolhasSolution(statusstartStatus,statustargetStatus){intstartInverseNumber=InverseNumber(startStatus);inttatgetInverseNumber=InverseNumber(targetStatus); //判断初始状态和目标状态除零外的序列逆序数奇偶性,相同则可求值,不同则不可求if((startInverseNumber%2)!=(tatgetInverseNumber%2)){returnfalse;}else{returntrue;}} //初始化一个空链表voidinitLink(PNode&Head){Head=(PNode)malloc(sizeof(NNode));Head->next=NULL;} //判断链表是否为空boolisEmpty(PNodeHead){if(Head->next==NULL){returntrue;}else{returnfalse;}} //从链表中拿出一个数据voidpopNode(PNode&Head,PNode&FNode){if(isEmpty(Head)){FNode=NULL;return;}FNode=Head->next;Head->next=Head->next->next;FNode->next=NULL;} //向节点的最终后继节点链表中添加新的子节点voidaddSpringNode(PNode&Head,PNodenewData){PSPLinknewNode=(PSPLink)malloc(sizeof(SPLink));newNode->pointData=newData; newNode->next=Head->child;Head->child=newNode;} //释放状态图中存放节点后继节点地址的空间voidfreeSpringLink(PSPLink&Head){PSPLinktmm; while(Head!=NULL){tmm=Head;Head=Head->next;free(tmm);}} //释放open表与closed表中的资源voidfreeLink(PNode&Head){PNodetmn; tmn=Head;Head=Head->next;free(tmn); while(Head!=NULL){//首先释放存放节点后继节点地址的空间freeSpringLink(Head->child);tmn=Head;Head=Head->next;free(tmn);}} //向普通链表中添加一个节点voidaddNode(PNode&Head,PNode&newNode){newNode->next=Head->next;Head->next=newNode;} //向非递减排列的链表中添加一个节点voidaddAscNode(PNode&Head,PNode&newNode){PNodeP;PNodeQ; P=Head->next;Q=Head;while(P!=NULL&&P->f_valuef_value){Q=P;P=P->next;}//上面判断好位置之后,下面就是简单的插入节点了newNode->next=Q->next;Q->next=newNode;} //计算节点到目标状态的预计耗散值intcomputeh_value(PNodetheNode,statustargetStatus){intnum=0;for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(theNode->data[i][j]!=targetStatus[i][j]){num++;}}}returnnum;} //计算节点的f,g,h值voidcomputeAllValue(PNode&theNode,PNodeparentNode,statustargetStatus){if(parentNode==NULL){theNode->g_value=0;}else{theNode->g_value=parentNode->g_value+1;} theNode->h_value=computeh_value(theNode,targetStatus);theNode->f_value=theNode->g_value+theNode->h_value;} //初始化函数,进行算法初始条件的设置voidinitial(statusstartStatus,statustargetStatus){//初始化open以及closed表initLink(open);initLink(closed); //初始化起始节点,令初始节点的父节点为空节点PNodeNULLNode=NULL;PNodeStartNode=(PNode)malloc(sizeof(NNode));for(inti=0;i<3;i++){for(intj=0;j<3;j++){StartNode->data[i][j]=startStatus[i][j];}}StartNode->parent=NULL;StartNode->child=NULL;StartNode->next=NULL;computeAllValue(StartNode,NULLNode,targetStatus); //起始节点进入OPEN表addAscNode(open,StartNode);} //将B节点的状态赋值给A节点voidstatusAEB(PNode&ANode,PNodeBNode){for(inti=0;i<3;i++){for(intj=0;j<3;j++){ANode->data[i][j]=BNode->data[i][j];}}} //两个节点是否有相同的状态boolhasSameStatus(PNodeANode,PNodeBNode){for(inti=0;i{for(intj=0;j{if(ANode->data[i][j]!=BNode->data[i][j])returnfalse;}}returntrue;} //节点与其祖先节点是否有相同的状态boolhasAnceSameStatus(PNodeOrigiNode,PNodeAnceNode){while(AnceNode!=NULL){if(hasSameStatus(OrigiNode,AnceNode))returntrue;AnceNode=AnceNode->parent;}returnfalse;} //取得方格中空的格子的位置voidgetPosition(PNodetheNode,int&row,int&col){for(inti=0;i{for(intj=0;j{if(theNode->data[i][j]==0){row=i;col=j;return;}}}} //交换两个数字的值voidchangeAB(int&a,int&b){intc;c=b;b=a;a=c;} //检查相应的状态是否在某一个链表中boolinLink(PNodespciNode,PNodetheLink,PNode&theNodeLink,PNode&preNode){preNode=theLink;theLink=theLink->next; while(theLink!=NULL){if(hasSameStatus(spciNode,theLink)){theNodeLink=theLink;returntrue;}preNode=theLink;theLink=theLink->next;}returnfalse;} //产生节点的后继节点链表voidSpringLink(PNodetheNode,PNode&spring,statustargetStatus){introw;intcol; getPosition(theNode,row,col); //空的格子右边的格子向左移动if(col!=2){PNoderlNewNode=(PNode)malloc(sizeof(NNode));statusAEB(rlNewNode,theNode);changeAB(rlNewNode->data[row][col],rlNewNode->data[row][col+1]);if(hasAnceSameStatus(rlNewNode,theNode->parent)){free(rlNewNode);//与父辈相同,丢弃本节点}else{rlNewNode->parent=theNode;rlNewNode->child=NULL;rlNewNode->next=NULL;computeAllValue(rlNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,rlNewNode);}}//空的格子左边的格子向右移动if(col!=0){PNodelrNewNode=(PNode)malloc(sizeof(NNode));statusAEB(lrNewNode,theNode);changeAB(lrNewNode->data[row][col],lrNewNode->data[row][col-1]);if(hasAnceSameStatus(lrNewNode,theNode->parent)){free(lrNewNode);//与父辈相同,丢弃本节点}else{lrNewNode->parent=theNode;lrNewNode->child=NULL;lrNewNode->next=NULL;computeAllValue(lrNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,lrNewNode);}}//空的格子上边的格子向下移动if(row!=0){PNodeudNewNode=(PNode)malloc(sizeof(NNode));statusAEB(udNewNode,theNode);changeAB(udNewNode->data[row][col],udNewNode->data[row-1][col]);if(hasAnceSameStatus(udNewNode,theNode->parent)){free(udNewNode);//与父辈相同,丢弃本节点}else{udNewNode->parent=theNode;udNewNode->child=NULL;udNewNode->next=NULL;computeAllValue(udNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,udNewNode);}}//空的格子下边的格子向上移动if(row!=2){PNodeduNewNode=(PNode)malloc(sizeof(NNode));statusAEB(duNewNode,theNode);changeAB(duNewNode->data[row][col],duNewNode->data[row+1][col]);if(hasAnceSameStatus(duNewNode,theNode->parent)){free(duNewNode);//与父辈相同,丢弃本节点}else{duNewNode->parent=theNode;duNewNode->child=NULL;duNewNode->next=NULL;computeAllValue(duNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,duNewNode);}}} //输出给定节点的状态voidoutputStatus(PNodestat){for(inti=0;i<3;i++){for(intj=0;j<3;j++){cout<data[i][j]<<"";}cout<}} //输出最佳的路径voidoutputBestRoad(PNodegoal){intdeepnum=goal->g_value; if(goal->parent!=NULL){outputBestRoad(goal->parent);}cout<<"第"<"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
sum++;
returnsum;
//判断是否存在解决方案
boolhasSolution(statusstartStatus,statustargetStatus)
intstartInverseNumber=InverseNumber(startStatus);
inttatgetInverseNumber=InverseNumber(targetStatus);
//判断初始状态和目标状态除零外的序列逆序数奇偶性,相同则可求值,不同则不可求
if((startInverseNumber%2)!
=(tatgetInverseNumber%2))
returnfalse;
else
returntrue;
//初始化一个空链表
voidinitLink(PNode&Head)
Head=(PNode)malloc(sizeof(NNode));
Head->next=NULL;
//判断链表是否为空
boolisEmpty(PNodeHead)
if(Head->next==NULL)
//从链表中拿出一个数据
voidpopNode(PNode&Head,PNode&FNode)
if(isEmpty(Head))
FNode=NULL;
return;
FNode=Head->next;
Head->next=Head->next->next;
FNode->next=NULL;
//向节点的最终后继节点链表中添加新的子节点
voidaddSpringNode(PNode&Head,PNodenewData)
PSPLinknewNode=(PSPLink)malloc(sizeof(SPLink));
newNode->pointData=newData;
newNode->next=Head->child;
Head->child=newNode;
//释放状态图中存放节点后继节点地址的空间
voidfreeSpringLink(PSPLink&Head)
PSPLinktmm;
while(Head!
=NULL)
tmm=Head;
Head=Head->next;
free(tmm);
//释放open表与closed表中的资源
voidfreeLink(PNode&Head)
PNodetmn;
tmn=Head;
free(tmn);
//首先释放存放节点后继节点地址的空间
freeSpringLink(Head->child);
//向普通链表中添加一个节点
voidaddNode(PNode&Head,PNode&newNode)
newNode->next=Head->next;
Head->next=newNode;
//向非递减排列的链表中添加一个节点
voidaddAscNode(PNode&Head,PNode&newNode)
PNodeP;
PNodeQ;
P=Head->next;
Q=Head;
while(P!
=NULL&&P->f_valuef_value)
Q=P;
P=P->next;
//上面判断好位置之后,下面就是简单的插入节点了
newNode->next=Q->next;
Q->next=newNode;
//计算节点到目标状态的预计耗散值
intcomputeh_value(PNodetheNode,statustargetStatus)
intnum=0;
for(inti=0;i<3;i++)
for(intj=0;j<3;j++)
if(theNode->data[i][j]!
=targetStatus[i][j])
num++;
returnnum;
//计算节点的f,g,h值
voidcomputeAllValue(PNode&theNode,PNodeparentNode,statustargetStatus)
if(parentNode==NULL)
theNode->g_value=0;
theNode->g_value=parentNode->g_value+1;
theNode->h_value=computeh_value(theNode,targetStatus);
theNode->f_value=theNode->g_value+theNode->h_value;
//初始化函数,进行算法初始条件的设置
voidinitial(statusstartStatus,statustargetStatus)
//初始化open以及closed表
initLink(open);
initLink(closed);
//初始化起始节点,令初始节点的父节点为空节点
PNodeNULLNode=NULL;
PNodeStartNode=(PNode)malloc(sizeof(NNode));
StartNode->data[i][j]=startStatus[i][j];
StartNode->parent=NULL;
StartNode->child=NULL;
StartNode->next=NULL;
computeAllValue(StartNode,NULLNode,targetStatus);
//起始节点进入OPEN表
addAscNode(open,StartNode);
//将B节点的状态赋值给A节点
voidstatusAEB(PNode&ANode,PNodeBNode)
ANode->data[i][j]=BNode->data[i][j];
//两个节点是否有相同的状态
boolhasSameStatus(PNodeANode,PNodeBNode)
for(inti=0;i{for(intj=0;j{if(ANode->data[i][j]!=BNode->data[i][j])returnfalse;}}returntrue;} //节点与其祖先节点是否有相同的状态boolhasAnceSameStatus(PNodeOrigiNode,PNodeAnceNode){while(AnceNode!=NULL){if(hasSameStatus(OrigiNode,AnceNode))returntrue;AnceNode=AnceNode->parent;}returnfalse;} //取得方格中空的格子的位置voidgetPosition(PNodetheNode,int&row,int&col){for(inti=0;i{for(intj=0;j{if(theNode->data[i][j]==0){row=i;col=j;return;}}}} //交换两个数字的值voidchangeAB(int&a,int&b){intc;c=b;b=a;a=c;} //检查相应的状态是否在某一个链表中boolinLink(PNodespciNode,PNodetheLink,PNode&theNodeLink,PNode&preNode){preNode=theLink;theLink=theLink->next; while(theLink!=NULL){if(hasSameStatus(spciNode,theLink)){theNodeLink=theLink;returntrue;}preNode=theLink;theLink=theLink->next;}returnfalse;} //产生节点的后继节点链表voidSpringLink(PNodetheNode,PNode&spring,statustargetStatus){introw;intcol; getPosition(theNode,row,col); //空的格子右边的格子向左移动if(col!=2){PNoderlNewNode=(PNode)malloc(sizeof(NNode));statusAEB(rlNewNode,theNode);changeAB(rlNewNode->data[row][col],rlNewNode->data[row][col+1]);if(hasAnceSameStatus(rlNewNode,theNode->parent)){free(rlNewNode);//与父辈相同,丢弃本节点}else{rlNewNode->parent=theNode;rlNewNode->child=NULL;rlNewNode->next=NULL;computeAllValue(rlNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,rlNewNode);}}//空的格子左边的格子向右移动if(col!=0){PNodelrNewNode=(PNode)malloc(sizeof(NNode));statusAEB(lrNewNode,theNode);changeAB(lrNewNode->data[row][col],lrNewNode->data[row][col-1]);if(hasAnceSameStatus(lrNewNode,theNode->parent)){free(lrNewNode);//与父辈相同,丢弃本节点}else{lrNewNode->parent=theNode;lrNewNode->child=NULL;lrNewNode->next=NULL;computeAllValue(lrNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,lrNewNode);}}//空的格子上边的格子向下移动if(row!=0){PNodeudNewNode=(PNode)malloc(sizeof(NNode));statusAEB(udNewNode,theNode);changeAB(udNewNode->data[row][col],udNewNode->data[row-1][col]);if(hasAnceSameStatus(udNewNode,theNode->parent)){free(udNewNode);//与父辈相同,丢弃本节点}else{udNewNode->parent=theNode;udNewNode->child=NULL;udNewNode->next=NULL;computeAllValue(udNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,udNewNode);}}//空的格子下边的格子向上移动if(row!=2){PNodeduNewNode=(PNode)malloc(sizeof(NNode));statusAEB(duNewNode,theNode);changeAB(duNewNode->data[row][col],duNewNode->data[row+1][col]);if(hasAnceSameStatus(duNewNode,theNode->parent)){free(duNewNode);//与父辈相同,丢弃本节点}else{duNewNode->parent=theNode;duNewNode->child=NULL;duNewNode->next=NULL;computeAllValue(duNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,duNewNode);}}} //输出给定节点的状态voidoutputStatus(PNodestat){for(inti=0;i<3;i++){for(intj=0;j<3;j++){cout<data[i][j]<<"";}cout<}} //输出最佳的路径voidoutputBestRoad(PNodegoal){intdeepnum=goal->g_value; if(goal->parent!=NULL){outputBestRoad(goal->parent);}cout<<"第"<"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
for(intj=0;j{if(ANode->data[i][j]!=BNode->data[i][j])returnfalse;}}returntrue;} //节点与其祖先节点是否有相同的状态boolhasAnceSameStatus(PNodeOrigiNode,PNodeAnceNode){while(AnceNode!=NULL){if(hasSameStatus(OrigiNode,AnceNode))returntrue;AnceNode=AnceNode->parent;}returnfalse;} //取得方格中空的格子的位置voidgetPosition(PNodetheNode,int&row,int&col){for(inti=0;i{for(intj=0;j{if(theNode->data[i][j]==0){row=i;col=j;return;}}}} //交换两个数字的值voidchangeAB(int&a,int&b){intc;c=b;b=a;a=c;} //检查相应的状态是否在某一个链表中boolinLink(PNodespciNode,PNodetheLink,PNode&theNodeLink,PNode&preNode){preNode=theLink;theLink=theLink->next; while(theLink!=NULL){if(hasSameStatus(spciNode,theLink)){theNodeLink=theLink;returntrue;}preNode=theLink;theLink=theLink->next;}returnfalse;} //产生节点的后继节点链表voidSpringLink(PNodetheNode,PNode&spring,statustargetStatus){introw;intcol; getPosition(theNode,row,col); //空的格子右边的格子向左移动if(col!=2){PNoderlNewNode=(PNode)malloc(sizeof(NNode));statusAEB(rlNewNode,theNode);changeAB(rlNewNode->data[row][col],rlNewNode->data[row][col+1]);if(hasAnceSameStatus(rlNewNode,theNode->parent)){free(rlNewNode);//与父辈相同,丢弃本节点}else{rlNewNode->parent=theNode;rlNewNode->child=NULL;rlNewNode->next=NULL;computeAllValue(rlNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,rlNewNode);}}//空的格子左边的格子向右移动if(col!=0){PNodelrNewNode=(PNode)malloc(sizeof(NNode));statusAEB(lrNewNode,theNode);changeAB(lrNewNode->data[row][col],lrNewNode->data[row][col-1]);if(hasAnceSameStatus(lrNewNode,theNode->parent)){free(lrNewNode);//与父辈相同,丢弃本节点}else{lrNewNode->parent=theNode;lrNewNode->child=NULL;lrNewNode->next=NULL;computeAllValue(lrNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,lrNewNode);}}//空的格子上边的格子向下移动if(row!=0){PNodeudNewNode=(PNode)malloc(sizeof(NNode));statusAEB(udNewNode,theNode);changeAB(udNewNode->data[row][col],udNewNode->data[row-1][col]);if(hasAnceSameStatus(udNewNode,theNode->parent)){free(udNewNode);//与父辈相同,丢弃本节点}else{udNewNode->parent=theNode;udNewNode->child=NULL;udNewNode->next=NULL;computeAllValue(udNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,udNewNode);}}//空的格子下边的格子向上移动if(row!=2){PNodeduNewNode=(PNode)malloc(sizeof(NNode));statusAEB(duNewNode,theNode);changeAB(duNewNode->data[row][col],duNewNode->data[row+1][col]);if(hasAnceSameStatus(duNewNode,theNode->parent)){free(duNewNode);//与父辈相同,丢弃本节点}else{duNewNode->parent=theNode;duNewNode->child=NULL;duNewNode->next=NULL;computeAllValue(duNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,duNewNode);}}} //输出给定节点的状态voidoutputStatus(PNodestat){for(inti=0;i<3;i++){for(intj=0;j<3;j++){cout<data[i][j]<<"";}cout<}} //输出最佳的路径voidoutputBestRoad(PNodegoal){intdeepnum=goal->g_value; if(goal->parent!=NULL){outputBestRoad(goal->parent);}cout<<"第"<"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
if(ANode->data[i][j]!
=BNode->data[i][j])
//节点与其祖先节点是否有相同的状态
boolhasAnceSameStatus(PNodeOrigiNode,PNodeAnceNode)
while(AnceNode!
if(hasSameStatus(OrigiNode,AnceNode))
AnceNode=AnceNode->parent;
//取得方格中空的格子的位置
voidgetPosition(PNodetheNode,int&row,int&col)
for(inti=0;i{for(intj=0;j{if(theNode->data[i][j]==0){row=i;col=j;return;}}}} //交换两个数字的值voidchangeAB(int&a,int&b){intc;c=b;b=a;a=c;} //检查相应的状态是否在某一个链表中boolinLink(PNodespciNode,PNodetheLink,PNode&theNodeLink,PNode&preNode){preNode=theLink;theLink=theLink->next; while(theLink!=NULL){if(hasSameStatus(spciNode,theLink)){theNodeLink=theLink;returntrue;}preNode=theLink;theLink=theLink->next;}returnfalse;} //产生节点的后继节点链表voidSpringLink(PNodetheNode,PNode&spring,statustargetStatus){introw;intcol; getPosition(theNode,row,col); //空的格子右边的格子向左移动if(col!=2){PNoderlNewNode=(PNode)malloc(sizeof(NNode));statusAEB(rlNewNode,theNode);changeAB(rlNewNode->data[row][col],rlNewNode->data[row][col+1]);if(hasAnceSameStatus(rlNewNode,theNode->parent)){free(rlNewNode);//与父辈相同,丢弃本节点}else{rlNewNode->parent=theNode;rlNewNode->child=NULL;rlNewNode->next=NULL;computeAllValue(rlNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,rlNewNode);}}//空的格子左边的格子向右移动if(col!=0){PNodelrNewNode=(PNode)malloc(sizeof(NNode));statusAEB(lrNewNode,theNode);changeAB(lrNewNode->data[row][col],lrNewNode->data[row][col-1]);if(hasAnceSameStatus(lrNewNode,theNode->parent)){free(lrNewNode);//与父辈相同,丢弃本节点}else{lrNewNode->parent=theNode;lrNewNode->child=NULL;lrNewNode->next=NULL;computeAllValue(lrNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,lrNewNode);}}//空的格子上边的格子向下移动if(row!=0){PNodeudNewNode=(PNode)malloc(sizeof(NNode));statusAEB(udNewNode,theNode);changeAB(udNewNode->data[row][col],udNewNode->data[row-1][col]);if(hasAnceSameStatus(udNewNode,theNode->parent)){free(udNewNode);//与父辈相同,丢弃本节点}else{udNewNode->parent=theNode;udNewNode->child=NULL;udNewNode->next=NULL;computeAllValue(udNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,udNewNode);}}//空的格子下边的格子向上移动if(row!=2){PNodeduNewNode=(PNode)malloc(sizeof(NNode));statusAEB(duNewNode,theNode);changeAB(duNewNode->data[row][col],duNewNode->data[row+1][col]);if(hasAnceSameStatus(duNewNode,theNode->parent)){free(duNewNode);//与父辈相同,丢弃本节点}else{duNewNode->parent=theNode;duNewNode->child=NULL;duNewNode->next=NULL;computeAllValue(duNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,duNewNode);}}} //输出给定节点的状态voidoutputStatus(PNodestat){for(inti=0;i<3;i++){for(intj=0;j<3;j++){cout<data[i][j]<<"";}cout<}} //输出最佳的路径voidoutputBestRoad(PNodegoal){intdeepnum=goal->g_value; if(goal->parent!=NULL){outputBestRoad(goal->parent);}cout<<"第"<"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
for(intj=0;j{if(theNode->data[i][j]==0){row=i;col=j;return;}}}} //交换两个数字的值voidchangeAB(int&a,int&b){intc;c=b;b=a;a=c;} //检查相应的状态是否在某一个链表中boolinLink(PNodespciNode,PNodetheLink,PNode&theNodeLink,PNode&preNode){preNode=theLink;theLink=theLink->next; while(theLink!=NULL){if(hasSameStatus(spciNode,theLink)){theNodeLink=theLink;returntrue;}preNode=theLink;theLink=theLink->next;}returnfalse;} //产生节点的后继节点链表voidSpringLink(PNodetheNode,PNode&spring,statustargetStatus){introw;intcol; getPosition(theNode,row,col); //空的格子右边的格子向左移动if(col!=2){PNoderlNewNode=(PNode)malloc(sizeof(NNode));statusAEB(rlNewNode,theNode);changeAB(rlNewNode->data[row][col],rlNewNode->data[row][col+1]);if(hasAnceSameStatus(rlNewNode,theNode->parent)){free(rlNewNode);//与父辈相同,丢弃本节点}else{rlNewNode->parent=theNode;rlNewNode->child=NULL;rlNewNode->next=NULL;computeAllValue(rlNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,rlNewNode);}}//空的格子左边的格子向右移动if(col!=0){PNodelrNewNode=(PNode)malloc(sizeof(NNode));statusAEB(lrNewNode,theNode);changeAB(lrNewNode->data[row][col],lrNewNode->data[row][col-1]);if(hasAnceSameStatus(lrNewNode,theNode->parent)){free(lrNewNode);//与父辈相同,丢弃本节点}else{lrNewNode->parent=theNode;lrNewNode->child=NULL;lrNewNode->next=NULL;computeAllValue(lrNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,lrNewNode);}}//空的格子上边的格子向下移动if(row!=0){PNodeudNewNode=(PNode)malloc(sizeof(NNode));statusAEB(udNewNode,theNode);changeAB(udNewNode->data[row][col],udNewNode->data[row-1][col]);if(hasAnceSameStatus(udNewNode,theNode->parent)){free(udNewNode);//与父辈相同,丢弃本节点}else{udNewNode->parent=theNode;udNewNode->child=NULL;udNewNode->next=NULL;computeAllValue(udNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,udNewNode);}}//空的格子下边的格子向上移动if(row!=2){PNodeduNewNode=(PNode)malloc(sizeof(NNode));statusAEB(duNewNode,theNode);changeAB(duNewNode->data[row][col],duNewNode->data[row+1][col]);if(hasAnceSameStatus(duNewNode,theNode->parent)){free(duNewNode);//与父辈相同,丢弃本节点}else{duNewNode->parent=theNode;duNewNode->child=NULL;duNewNode->next=NULL;computeAllValue(duNewNode,theNode,targetStatus);//将本节点加入后继节点链表addNode(spring,duNewNode);}}} //输出给定节点的状态voidoutputStatus(PNodestat){for(inti=0;i<3;i++){for(intj=0;j<3;j++){cout<data[i][j]<<"";}cout<}} //输出最佳的路径voidoutputBestRoad(PNodegoal){intdeepnum=goal->g_value; if(goal->parent!=NULL){outputBestRoad(goal->parent);}cout<<"第"<"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
if(theNode->data[i][j]==0)
row=i;
col=j;
//交换两个数字的值
voidchangeAB(int&a,int&b)
intc;
c=b;
b=a;
a=c;
//检查相应的状态是否在某一个链表中
boolinLink(PNodespciNode,PNodetheLink,PNode&theNodeLink,PNode&preNode)
preNode=theLink;
theLink=theLink->next;
while(theLink!
if(hasSameStatus(spciNode,theLink))
theNodeLink=theLink;
//产生节点的后继节点链表
voidSpringLink(PNodetheNode,PNode&spring,statustargetStatus)
introw;
intcol;
getPosition(theNode,row,col);
//空的格子右边的格子向左移动
if(col!
=2)
PNoderlNewNode=(PNode)malloc(sizeof(NNode));
statusAEB(rlNewNode,theNode);
changeAB(rlNewNode->data[row][col],rlNewNode->data[row][col+1]);
if(hasAnceSameStatus(rlNewNode,theNode->parent))
free(rlNewNode);//与父辈相同,丢弃本节点
rlNewNode->parent=theNode;
rlNewNode->child=NULL;
rlNewNode->next=NULL;
computeAllValue(rlNewNode,theNode,targetStatus);
//将本节点加入后继节点链表
addNode(spring,rlNewNode);
//空的格子左边的格子向右移动
PNodelrNewNode=(PNode)malloc(sizeof(NNode));
statusAEB(lrNewNode,theNode);
changeAB(lrNewNode->data[row][col],lrNewNode->data[row][col-1]);
if(hasAnceSameStatus(lrNewNode,theNode->parent))
free(lrNewNode);//与父辈相同,丢弃本节点
lrNewNode->parent=theNode;
lrNewNode->child=NULL;
lrNewNode->next=NULL;
computeAllValue(lrNewNode,theNode,targetStatus);
addNode(spring,lrNewNode);
//空的格子上边的格子向下移动
if(row!
PNodeudNewNode=(PNode)malloc(sizeof(NNode));
statusAEB(udNewNode,theNode);
changeAB(udNewNode->data[row][col],udNewNode->data[row-1][col]);
if(hasAnceSameStatus(udNewNode,theNode->parent))
free(udNewNode);//与父辈相同,丢弃本节点
udNewNode->parent=theNode;
udNewNode->child=NULL;
udNewNode->next=NULL;
computeAllValue(udNewNode,theNode,targetStatus);
addNode(spring,udNewNode);
//空的格子下边的格子向上移动
PNodeduNewNode=(PNode)malloc(sizeof(NNode));
statusAEB(duNewNode,theNode);
changeAB(duNewNode->data[row][col],duNewNode->data[row+1][col]);
if(hasAnceSameStatus(duNewNode,theNode->parent))
free(duNewNode);//与父辈相同,丢弃本节点
duNewNode->parent=theNode;
duNewNode->child=NULL;
duNewNode->next=NULL;
computeAllValue(duNewNode,theNode,targetStatus);
addNode(spring,duNewNode);
//输出给定节点的状态
voidoutputStatus(PNodestat)
cout<data[i][j]<<"";
cout<}} //输出最佳的路径voidoutputBestRoad(PNodegoal){intdeepnum=goal->g_value; if(goal->parent!=NULL){outputBestRoad(goal->parent);}cout<<"第"<"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
//输出最佳的路径
voidoutputBestRoad(PNodegoal)
intdeepnum=goal->g_value;
if(goal->parent!
outputBestRoad(goal->parent);
cout<<"第"<"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
"<outputStatus(goal);} voidAStar(statusstartStatus,statustargetStatus){PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针PNodespring;//tmpNode的后继节点链PNodetmpLNode;//tmpNode的某一个后继节点PNodetmpChartNode;PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针boolgetGoal=false;//标识是否达到目标状态longnumcount=1;//记录从open表中拿出节点的序号 initial(startStatus,targetStatus);//对函数进行初始化initLink(spring);//对后继链表的初始化tmpChartNode=NULL; cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
outputStatus(goal);
voidAStar(statusstartStatus,statustargetStatus)
PNodetmpNode;//指向从open表中拿出并放到closed表中的节点的指针
PNodespring;//tmpNode的后继节点链
PNodetmpLNode;//tmpNode的某一个后继节点
PNodetmpChartNode;
PNodethePreNode;//指向将要从closed表中移到open表中的节点的前一个节点的指针
boolgetGoal=false;//标识是否达到目标状态
longnumcount=1;//记录从open表中拿出节点的序号
initial(startStatus,targetStatus);//对函数进行初始化
initLink(spring);//对后继链表的初始化
tmpChartNode=NULL;
cout<<"从OPEN表中拿出的节点的状态及相应的值"<while(!isEmpty(open)){//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中popNode(open,tmpNode);addNode(closed,tmpNode); cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
while(!
isEmpty(open))
//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中
popNode(open,tmpNode);
addNode(closed,tmpNode);
cout<<"第"<"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
"<outputStatus(tmpNode);cout<<"其f值为:"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
outputStatus(tmpNode);
cout<<"其f值为:
"<f_value<cout<<"其g值为:"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
cout<<"其g值为:
"<g_value<cout<<"其h值为:"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
cout<<"其h值为:
"<h_value< //如果拿出的元素是目标状态则跳出循环if(computeh_value(tmpNode,targetStatus)==0){getGoal=true;break;} //产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点SpringLink(tmpNode,spring,targetStatus); //遍历检测节点的后继节点链表while(!isEmpty(spring)){popNode(spring,tmpLNode);//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用if(inLink(tmpLNode,open,tmpChartNode,thePreNode)){addSpringNode(tmpNode,tmpChartNode);if(tmpLNode->g_valueg_value){tmpChartNode->parent=tmpLNode->parent;tmpChartNode->g_value=tmpLNode->g_value;tmpChartNode->f_value=tmpLNode->f_value;}fre
//如果拿出的元素是目标状态则跳出循环
if(computeh_value(tmpNode,targetStatus)==0)
getGoal=true;
break;
//产生当前检测节点的后继(与祖先不同)节点列表,产生的后继节点的parent属性指向当前检测的节点
SpringLink(tmpNode,spring,targetStatus);
//遍历检测节点的后继节点链表
isEmpty(spring))
popNode(spring,tmpLNode);
//状态在OPEN表中已经存在,thePreNode参数在这里并不起作用
if(inLink(tmpLNode,open,tmpChartNode,thePreNode))
addSpringNode(tmpNode,tmpChartNode);
if(tmpLNode->g_valueg_value)
tmpChartNode->parent=tmpLNode->parent;
tmpChartNode->g_value=tmpLNode->g_value;
tmpChartNode->f_value=tmpLNode->f_value;
fre
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2