人工智能a星算法解决八数码难题程序代码

#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 * Search_A(struct node *name,struct node *temp); void Print_result(struct node *p); struct node / 定义 8 数码的节点状态 int s33; /当前 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 Calculate_f(0, /计算头结点的代价值 Add_to_open( /将头结点 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, break; else if(n-j_0=1) /空格所在列号不小于 1,可左移 temp=n-father; if(temp!=NULL else /新节点与其祖父节点不同，或其父节点为起始节点 temp=(struct node *)malloc(sizeof(struct node); /给新节点分配空间 Copy_node(n,temp); /拷贝 n 指向的节点状态 temp-stemp-i_0temp-j_0=temp-stemp-i_0temp-j_0-1; /空格左移 temp-stemp-i_0temp-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-ff) /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-ff) /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(n-j_0father; if(temp!=NULL else /新节点与其祖父节点不同，或其父节点为起始节点 temp=(struct node *)malloc(sizeof(struct node); /给新节点分配空间 Copy_node(n,temp); /拷贝 p 指向的节点状态 temp-stemp-i_0temp-j_0=temp-stemp-i_0temp-j_0+1; /空格右移 temp-stemp-i_0temp-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-ff) /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-ff) /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(n-i_0=1) /空格所在列号不小于 1,上移 temp=n-father; if(temp!=NULL else /新节点与其祖父节点不同，或其父节点为起始节点 temp=(struct node *)malloc(sizeof(struct node); /给新节点分配空间 Copy_node(n,temp); /拷贝 p 指向的节点状态 temp-stemp-i_0temp-j_0=temp-stemp-i_0-1temp-j_0; /空格上移 temp-stemp-i_0-1temp-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-ff) /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-ff) /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(n-i_0father; if(temp!=NULL else /新节点与其祖父节点不同，或其父节点为起始节点 temp=(struct node *)malloc(sizeof(struct node); /给新节点分配空间 Copy_node(n,temp); /拷贝 p 指向的节点状态 temp-stemp-i_0temp-j_0=temp-stemp-i_0+1temp-j_0; /空格下移 temp-stemp-i_0+1temp-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-ff) /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-ff) /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(bingo=1) Print_result(n); /输出解路径 else printf(“问题求解失败！“); /主函数结束 /* /* * /* 计算某个节点状态的代价值 * /* * /* void Calculate_f(int deepth,struct node *p) int i,j,temp; temp=0; for(i=0;isij)!=(s_g.sij) 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 /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;isij)!=(p1-sij) 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-next=NULL; return; else p2=name; p1=p2-next; while(p1) if(Test_A_B(p1,p) return; else p2=p1; /p2 始终指向 p1 指向的前一个元素 p1=p1-next; return; /* * /* * /* 将 p1 指向的节点状态拷贝到 p2 指向的节点中 * /* * /* * void Copy_node(struct node *p1,stru