使用A*算法实现8数码问题的求解

#include "Stdio.h" #include "Conio.h" #include "stdlib.h" #include "math.h" void Copy_node(struct node *p1,struct node *p2); void Calculate_f(int deepth,struct node *p); void Add_to_open(struct node *p); void Add_to_closed(struct node *p); void Remove_p(struct node *name,struct node *p); int Test_A_B(struct node *p1,struct node *p2); struct node * Solution_Astar(struct node *p); void Expand_n(struct node *p); struct node * Search_A(struct node *name,struct node *temp); void Print_result(struct node *p); /* 定义8数码的节点状态 */ typedef struct node { int s[3][3]; //当前8数码的状态 int i_0; //当前空格所在行号 int j_0; //当前空格所在列号 int f; //当前代价值 int d; //当前节点深度 int h; //启发信息，采用数码"不在位"距离和 struct node *father; //指向解路径上该节点的父节点 struct node *next; //指向所在open或closed表中的下一个元素 }; struct node s_0={{3,8,5,7,0,2,1,6,4},1,1,0,0,0,NULL,NULL}; //定义初始状态 struct node s_g={{1,2,3,8,0,4,7,6,5},1,1,0,0,0,NULL,NULL}; //定义目标状态 struct node *open=NULL; //建立open表指针 struct node *closed=NULL; //建立closed表指针 int sum_node=0; //用于记录扩展节点总数 void input(){ int i,j; for(i=0;i<3;i++) for(j=0;j<3;j++) { printf("请输入第%d行第%d列的值\n",i,j); scanf("%d",&s_0.s[i][j]); } printf("请输入初始状态的空格的位置(行)\n"); scanf("%d",&s_0.i_0); printf("请输入初始状态的空格的位置(列)\n"); scanf("%d",&s_0.j_0); printf("\n\n"); } int main(void) { input(); struct node s,*target; Copy_node(&s_0,&s); Calculate_f(0,&s); //拷贝8数码初始状态，初始化代价值 target=Solution_Astar(&s); //求解主程序 if(target) Print_result(target); //输出解路径 else printf("问题求解失败！"); getch(); return 0; } /******************************************/ /* A*算法 */ /******************************************/ struct node * Solution_Astar(struct node *p) { struct node *n,*temp; Add_to_open(p); //将s_0放入open表 while(open!=NULL) //只要open表中还有元素，就继续对代价最小的节点进行扩展 { n=open; //n指向open表中当前要扩展的元素 temp=open->next; Add_to_closed(n); open=temp; if(Test_A_B(n,&s_g)) //当前n指向节点为目标时，跳出程序结束；否则，继续下面的步骤 return n; Expand_n(n); //扩展节点n } return NULL; } /*******************************************************/ /* 生成当前节点n通过走步可以得到的所有状态 */ /*******************************************************/ void Expand_n(struct node *p) { struct node *temp,*same; if(p->j_0>=1) //空格所在列号不小于1,可左移 { temp=p->father; if(temp!=NULL&&temp->i_0==p->i_0&&temp->j_0+1==p->j_0) //新节点与其祖父节点相同 ; else //新节点与其祖父节点不同，或其父节点为起始节点 { temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间 Copy_node(p,temp); //拷贝p指向的节点状态 temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0][temp->j_0-1]; //空格左移 temp->s[temp->i_0][temp->j_0-1]=0; temp->j_0--; temp->d++; Calculate_f(temp->d,temp); //修改新节点的代价值 temp->father=p; //新节点指向其父节点 if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点 { if(temp->f<same->f) //temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表 { Remove_p(closed,same); //从closed表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node++; } else; } else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节点 { if(temp->f<same->f) //temp指向的节点,其代价比open表中相同状态节点代价小，加入open表 { Remove_p(open,same); //从open表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node++; } else ; } else //新节点为完全不同的新节点，加入open表 { Add_to_open(temp); sum_node++; } } }//end左移 if(p->j_0<=1) //空格所在列号不大于1,可右移 { temp=p->father; if(temp!=NULL&&temp->i_0==p->i_0&&temp->j_0+1==p->j_0) //新节点与其祖父节点相同 ; else //新节点与其祖父节点不同，或其父节点为起始节点 { temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间 Copy_node(p,temp); //拷贝p指向的节点状态 temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0][temp->j_0+1]; //空格右移 temp->s[temp->i_0][temp->j_0+1]=0; temp->j_0++; temp->d++; Calculate_f(temp->d,temp); //修改新节点的代价值 temp->father=p; //新节点指向其父节点 if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点 { if(temp->f<same->f) //temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表 { Remove_p(closed,same); //从closed表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node++; } else; } else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节点 { if(temp->f<same->f) //temp指向的节点,其代价比open表中相同状态节点代价小，加入open表 { Remove_p(open,same); //从open表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node++; } else ; } else //新节点为完全不同的新节点，加入open表 { Add_to_open(temp); sum_node++; } } }//end右移 if(p->i_0>=1) //空格所在列号不小于1,上移 { temp=p->father; if(temp!=NULL&&temp->i_0==p->i_0-1&&temp->j_0==p->j_0) //新节点与其祖父节点相同 ; else //新节点与其祖父节点不同，或其父节点为起始节点 { temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间 Copy_node(p,temp); //拷贝p指向的节点状态 temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0-1][temp->j_0]; //空格上移 temp->s[temp->i_0-1][temp->j_0]=0; temp->i_0--; temp->d++; Calculate_f(temp->d,temp); //修改新节点的代价值 temp->father=p; //新节点指向其父节点 if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点 { if(temp->f<same->f) //temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表 { Remove_p(closed,same); //从closed表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node++; } else; } else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节点 { if(temp->f<same->f) //temp指向的节点,其代价比open表中相同状态节点代价小，加入open表 { Remove_p(open,same); //从open表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node++; } else ; } else //新节点为完全不同的新节点，加入open表 { Add_to_open(temp); sum_node++; } } }//end上移 if(p->i_0<=1) //空格所在列号不大于1,下移 { temp=p->father; if(temp!=NULL&&temp->i_0==p->i_0+1&&temp->j_0==p->j_0) //新节点与其祖父节点相同 ; else //新节点与其祖父节点不同，或其父节点为起始节点 { temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间 Copy_node(p,temp); //拷贝p指向的节点状态 temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0+1][temp->j_0]; //空格下移 temp->s[temp->i_0+1][temp->j_0]=0; temp->i_0++; temp->d++; Calculate_f(temp->d,temp); //修改新节点的代价值 temp->father=p; //新节点指向其父节点 if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点 { if(temp->f<same->f) //temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表 { Remove_p(closed,same); //从closed表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node++;