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 * Search_A(struct node *name,struct node *temp); void Print_result(struct node *p);
struct node // 定义8数码的节点状态 {
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={{2,8,3,1,6,4,7,0,5},2,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 main() {
int bingo=0; //定义查找成功标志，bingo=1，成功
struct node s; //定义头结点s struct node *target,*n,*ls,*temp,*same; //定义结构体指针
Copy_node(&s_0,&s); //复制初始状s_0态给头结点s Calculate_f(0,&s); //计算头结点的代价值
Add_to_open(&s); //将头结点s放入open表
while(open!=NULL) //只要open表不为空，进行以下循环 {
n=open; //n指向open表中当前要扩展的元素 ls=open->next; Add_to_closed(n);
open=ls; //将n指向的节点放入closed表中
if(Test_A_B(n,&s_g)) //当前n指向节点为目标时，跳出程序结束；否则，继续下面的步骤 { bingo=1; break; } else
if(n->j_0>=1) //空格所在列号不小于1,可左移 {
temp=n->father;
if(temp!=NULL&&temp->i_0==n->i_0&&temp->j_0-1==n->j_0) //新节点与其祖父节点相同 ; else //新节点与其祖父节点不同，或其父节点为起始节点 {
temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间 Copy_node(n,temp); //拷贝n指向的节点状态
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=n; //新节点指向其父节点 if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点 { if(temp->f Add_to_open(temp); sum_node++; } else; } 点 else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节 { if(temp->f 代价小，加入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 if(n->i_0>=1) //空格所在列号不小于1,上移 { temp=n->father; if(temp!=NULL&&temp->i_0==n->i_0-1&&temp->j_0==n->j_0) //新节点与其祖父节点相同 ; else //新节点与其祖父节点不同，或其父节点为起始节点 { temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间 Copy_node(n,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=n; //新节点指向其父节点 if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点 { if(temp->f else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节 { if(temp->f if(n->i_0<=1) //空格所在列号不大于1,下移 { temp=n->father; if(temp!=NULL&&temp->i_0==n->i_0+1&&temp->j_0==n->j_0) //新节点与其祖父节点相同 ; else //新节点与其祖父节点不同，或其父节点为起始节点 { temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间 Copy_node(n,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=n; //新节点指向其父节点 if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点 { if(temp->f Remove_p(closed,same); //从closed表中删除与temp指向节点状态相 Add_to_open(temp); sum_node++; } else; } else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节 { if(temp->f if(bingo=1) Print_result(n); //输出解路径 else printf(\"问题求解失败！\"); }//主函数结束 //************************************************************************* //********************** ********************** //********************** 计算某个节点状态的代价值 ********************** //********************** ********************** //************************************************************************* void Calculate_f(int deepth,struct node *p) { int i,j,temp; temp=0; for(i=0;i<=2;i++) //计算所有\"不在位\"数码的距离和 { for(j=0;j<=2;j++) { if((p->s[i][j])!=(s_g.s[i][j])) temp++; } } p->h=temp; p->f=deepth+p->h; } //************************************************************************* //********************** ********************** //********************** 添加p指向的节点到open表中 ********************** //********************** ********************** //************************************************************************* void Add_to_open(struct node *p) { struct node *p1,*p2; p1=open; //初始时p1指向open表首部 p2=NULL; if(open==NULL) //open表为空时，待插入节点即为open表第一个元素，open指向该元素 { p->next=NULL; open=p; } else //open表不为空时，添加待插入节点，并保证open表代价递增 的排序 { while(p1!=NULL&&p->f>p1->f) { p2=p1; //p2始终指向p1指向的前一个元素 p1=p1->next; } if(p2==NULL) //待插入节点为当前open表最小 { p->next=open; open=p; } else if(p1==NULL) //待插入节点为当前open表最大 { p->next=NULL; p2->next=p; } else //待插入节点介于p2、p1之间 { p2->next=p; p->next=p1; } } } //*************************************************************************** //********************** ********************** //********************** 添加p指向的节点到closed表中 ********************** //********************** ********************** //*************************************************************************** void Add_to_closed(struct node *p) { if(closed==NULL) //closed表为空时，p指向节点为closed表第一个元素，closed指向该元素 { p->next=NULL; closed=p; } else //closed表不为空时，直接放到closed表首部 { p->next=closed; closed=p; } } //************************************************************************************************** //********************** ********************** //********************** 在open表或closed表中搜索和temp指向的节点相同的节点 ********************** //********************** ********************** //************************************************************************************************** struct node * Search_A(struct node *name,struct node *temp) { struct node *p1; p1=name; //p1指向open表或closed表 while(p1!=NULL) { if(Test_A_B(p1,temp)) //找到相同的节点，返回该节点地址 return p1; else p1=p1->next; } return NULL; } //*********************************************************************************************** //********************** ********************** //********************** 判断两个节点状态是否相同，相同则返回1，否则返回0 ********************** //********************** ********************** //*********************************************************************************************** int Test_A_B(struct node *p1,struct node *p2) { int i,j,flag; flag=1; for(i=0;i<=2;i++) for(j=0;j<=2;j++) { if((p2->s[i][j])!=(p1->s[i][j])) { flag=0; return flag; } else ; } return flag; } //****************************************************************************** //********************** ********************** //********************** 从open表或closed表删除指定节点 ********************** //********************** ********************** //****************************************************************************** void Remove_p(struct node *name,struct node *p) { struct node *p1,*p2; p1=NULL; p2=NULL; if(name==NULL) //如果name指向的链表为空，则不需要进行删除 return; else if(Test_A_B(name,p)&&name->f==p->f) //指定节点为name指向的链表的第一个元素 { open=name->next; name->next=NULL; return; } else { p2=name; p1=p2->next; while(p1) { if(Test_A_B(p1,p)&&p1->f==p->f) //找到指定节点 { p2->next=p1->next; return; } else { p2=p1; //p2始终指向p1指向的前一个元素 p1=p1->next; } } return; } } //************************************************************************************** //********************** ********************** //********************** 将p1指向的节点状态拷贝到p2指向的节点中 ********************** //********************** ********************** //************************************************************************************** void Copy_node(struct node *p1,struct node *p2) { int i,j; for(i=0;i<=2;i++) { for(j=0;j<=2;j++) { p2->s[i][j]=p1->s[i][j]; } } p2->i_0=p1->i_0; p2->j_0=p1->j_0; p2->f=p1->f; p2->d=p1->d; p2->h=p1->h; p2->next=p1->next; p2->father=p1->father; } //*********************************************************** //********************** ********************** //********************** 输出结果 ********************** //********************** ********************** //*********************************************************** void Print_result(struct node *p) { struct node *path[100]; struct node *temp,*temp_father; int i,j,k; for(i=0;i<=99;i++) //初始化路径指针数组 path[i]=0; temp=p; printf(\"总共扩展 %d 个节点\\n\ printf(\"总共扩展 %d 层\\n\ printf(\"解路径如下：\\n\"); for(i=p->d;i>=0;i--) //存储解路径上各节点的地址 { path[i]=temp; temp=temp->father; } for(k=0;k<=p->d;k++) //输出解路径 { temp=path[k]; //建立节点指点指针 printf(\"第%d步 \ if(k-1>=0) //输出移动策略 { temp_father=path[k-1]; if(temp->i_0 { for(j=0;j<=2;j++) { printf(\"%d \ } printf(\"\\n\"); } printf(\"\\n\"); } } 因篇幅问题不能全部显示，请点此查看更多更全内容