A*搜索算法代码,C代码库,德仔网

代码语言
代码分类
【C】 A*搜索算法
作者:suojiumian / 发布于2013/10/23/ 667
A*搜索算法在八数码问题中应用

	#include <stdlib.h>
	#include <stdio.h>
	#include <math.h>

	
	//节点结构体
	typedef struct Node
	{
	 int data[9];
	double f,g;
	struct Node * parent;
	}Node,*Lnode;


	//OPEN CLOSED 表结构体
	typedef struct Stack
	{
	Node * npoint;
	struct Stack * next;
	}Stack,* Lstack;

	
	//选取OPEN表上f值最小的节点，返回该节点地址
	Node * Minf(Lstack * Open)
	{
	Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open);
	Node * minx;
	 while(temp->next != NULL)
	{
	 if((temp->next ->npoint->f) < (min->npoint->f))
	 {
	 min = temp->next;
	 minp = temp;
	 }
	 temp = temp->next;
	}
	minx = min->npoint;
	temp = minp->next;
	minp->next = minp->next->next;
	free(temp);
	
	return minx;
	}

	//判断是否可解
	int Canslove(Node * suc, Node * goal)
	{
	int a = 0,b = 0,i,j;
	for(i = 1; i< 9;i++)
	 for(j = 0;j < i;j++)
	 {
	 if((suc->data[i] > suc->data[j]) && suc->data[j] != 0)
	 a++;
	 if((goal->data[i] > goal->data[j]) && goal->data[j] != 0)
	 b++;
	 }
	 if(a%2 == b%2)
	 return 1;
	 else
	 return 0;
	}

	
	//判断节点是否相等 ，1相等，0不相等
	int Equal(Node * suc,Node * goal)
	{
	for(int i = 0; i < 9; i ++ )
	 if(suc->data[i] != goal->data[i])
	 return 0;
	 return 1;
	}

	//判断节点是否属于OPEN表 或 CLOSED表，是则返回节点地址，否则返回空地址
	Node * Belong(Node * suc,Lstack * list)
	{
	Lstack temp = (*list) -> next ;
	if(temp == NULL)
	 return NULL;
	while(temp != NULL)
	{
	 if(Equal(suc,temp->npoint))
	 return temp -> npoint;
	 temp = temp->next;
	}
	return NULL;
	}

	
	//把节点放入OPEN 或CLOSED 表中
	void Putinto(Node * suc,Lstack * list)
	{
	 Stack * temp;
	temp =(Stack *) malloc(sizeof(Stack));
	temp->npoint = suc;
	temp->next = (*list)->next;
	(*list)->next = temp;
	}

	//计算f值部分-开始
	double Fvalue(Node suc, Node goal, float speed)
	{
	//计算f值
	double Distance(Node,Node,int);
	double h = 0;
	for(int i = 1; i <= 8; i++)
	 h = h + Distance(suc, goal, i);
	return h*speed + suc.g;
	//f = h + g;
	//speed值增加时搜索过程以找到目标为优先因此可能不会返回最优解
	}

	double Distance(Node suc, Node goal, int i)
	{
	//计算方格的错位距离
	int k,h1,h2;
	for(k = 0; k < 9; k++)
	{
	 if(suc.data[k] == i)h1 = k;
	 if(goal.data[k] == i)h2 = k;
	}
	return double(fabs(h1/3 - h2/3) + fabs(h1%3 - h2%3));
	}

	//计算f值部分-结束
	//扩展后继节点部分的函数-开始
	int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed)
	{
	//判断子节点是否属于OPEN或CLOSED表 并作出相应的处理
	Node * temp = NULL;
	int flag = 0;
	
	if((Belong(*suc,Open) != NULL) || (Belong(*suc,Closed) != NULL))
	{
	 if(Belong(*suc,Open) != NULL)
	 temp = Belong(*suc,Open);
	 else
	 temp = Belong(*suc,Closed);
	 if(((*suc)->g) < (temp->g))
	 {
	 temp->parent = (*suc)->parent;
	 temp->g = (*suc)->g;
	 temp->f = (*suc)->f;
	 flag = 1;
	 }
	}
	
	else
	{
	 Putinto(* suc, Open);
	 (*suc)->f = Fvalue(**suc, goal, speed);
	}
	return flag;
	}

	//判断空格可否向该方向移动1，2，3，4表示空格向上向下向左向右移
	int Canspread(Node suc, int n)
	{
	int i,flag = 0;
	for(i = 0;i < 9;i++)
	 if(suc.data[i] == 0)break;
	 switch(n)
	 {
	 case 1:if(i/3 != 0)
	 flag = 1;break;
	 case 2:
	 if(i/3 != 2)
	 flag = 1;break;
	 case 3:
	 if(i%3 != 0)
	 flag = 1;break;
	 case 4:
	 if(i%3 != 2)
	 flag = 1;break;
	 default:break;
	 }
	
	 return flag ;
	}


	//扩展child节点的字节点n表示方向0，1，2，3表示空格向上向下向左向右移
	void Spreadchild(Node * child,int n)
	{
	int i,loc,temp;
	for(i = 0;i < 9;i++)
	 child->data[i] = child->parent->data[i];
	for(i = 0;i < 9;i++)
	 if(child->data[i] == 0)
	 break;
	 if(n==0)
	 loc = i%3+(i/3 - 1)*3;
	 else if(n==1)
	 loc = i%3+(i/3 + 1)*3;
	 else if(n==2)
	 loc = i%3-1+(i/3)*3;
	 else
	 loc = i%3+1+(i/3)*3;
	 temp = child->data[loc];
	 child->data[i] = temp;
	 child->data[loc] = 0;
	}

	
	//扩展后继节点总函数
	void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, float speed)
	{
	int i;
	Node * child;
	for(i = 0; i < 4; i++)
	{
	 if(Canspread(**suc, i+1))
	 //判断某个方向上的子节点可否扩展
	 {
	 //扩展子节点
	 child = (Node *) malloc(sizeof(Node));
	
	 child->g = (*suc)->g +1;
	 //算子节点的g值
	
	 child->parent = (*suc);
	 //子节点父指针指向父节点
	
	 Spreadchild(child, i);
	 //向该方向移动空格生成子节点
	
	 if(BelongProgram(&child, Open, Closed, goal, speed))
	 // 判断子节点是否属于OPEN或CLOSED表并作出相应的处理
	 free(child);
	 }
	}
	}

	//扩展后继节点部分的函数-结束
	Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, float speed)
	{
	//总执行函数
	while(1)
	{
	 if((*Open)->next == NULL)return NULL;
	 //判断OPEN表是否为空，为空则失败退出
	 Node * minf = Minf(Open);
	
	 //从OPEN表中取出f值最小的节点
	 Putinto(minf, Closed);
	 //将节点放入CLOSED表中
	 if(Equal(minf, *goal))return minf;
	 //如果当前节点是目标节点，则成功退出
	 Spread(&minf, Open, Closed, **goal, speed);
	 //当前节点不是目标节点时扩展当前节点的后继节点
	}
	}

	//递归显示从初始状态到达目标状态的移动方法
	int Shownum(Node * result)
	{
	if(result == NULL)return 0;
	else
	{
	 int n = Shownum(result->parent);
	 for(int i = 0; i < 3; i++)
	 {
	 printf("\n");
	 for(int j = 0; j < 3; j++)
	 {
	 if(result->data[i*3+j] != 0)
	 printf(" %d ",result->data[i*3+j]);
	 else printf(" ");
	 }
	 }
	 printf("\n");
	 return n+1;
	}
	}


	//检查输入
	void Checkinput(Node *suc)
	{
	int i = 0,j = 0,flag = 0;
	char c;
	while(i < 9)
	{
	 while(((c = getchar()) != 10))
	 {
	 if(c == ' ')
	 {
	 if(flag >= 0)flag = 0;
	 }
	 else if(c >= '0' && c <= '8')
	 {
	 if(flag == 0)
	 {
	 suc->data[i] = (c-'0');
	 flag = 1;
	 for(j =0; j < i; j++)
	 if(suc->data[j] == suc->data[i])flag = -2;
	 i++;
	 }
	 else if(flag >= 0)flag = -1;
	 }
	 else
	 if(flag >= 0)flag = -1;
	 }
	 if(flag <0 || i < 9)
	 {
	 if(flag < 0)
	 {
	 if(flag == -1)
	 printf("含有非法字符或数字!\n请重新输入:\n");
	 else if(flag == -2)
	 printf("输入的数字有重复!\n请重新输入:\n");
	 }
	 else if(i < 9)
	 printf("输入的有效数字不够!\n请重新输入:\n");
	 i = 0;
	 flag = 0;
	 }
	}
	}

	void main()
	{
	//主函数
	
	//初始操作，建立open和closed表
	Lstack Open = (Stack *) malloc(sizeof(Stack));
	Open->next = NULL;
	Lstack Closed = (Stack *) malloc(sizeof(Stack));
	Closed->next = NULL;
	Node * org = (Node *) malloc(sizeof(Node));
	org->parent = NULL; //初始状态节点
	org->f =1;
	org->g =1;
	 Node * goal = (Node *) malloc(sizeof(Node)); //目标状态节点
	Node * result;
	float speed = 1;//speed搜索速度
	char c;
	
	
	printf("0-8 9个数字以空格隔开,回车表示输入结束\n");
	printf("-----------------------------------\n");
	printf("首先，请输入初始状态:\n");
	Checkinput(org);
	
	printf("然后，请输入目标状态:\n");
	
	Checkinput(goal);
	
	if(Canslove(org, goal))
	{
	 //A*算法开始，先将初始状态放入OPEN表
	 printf("请输入搜索速度(默认速度是1):");
	 scanf("%f",&speed);
	
	 while((c = getchar()) != 10);
	 printf("搜索中，请耐心等待......\n");
	 Putinto(org,&Open);
	 result = Process(&org, &goal, &Open, &Closed, speed); //进行剩余的操作
	
	 printf("总步数:%d,搜索速度:%f\n",Shownum(result),speed);
	 printf("\n");
	 printf("Press Enter key to exit!");
	 while((c = getchar()) != 10);
	}
	else
	 printf("程序认定该起始状态无法道达目标状态!\n");
	}
试试其它关键字
　搜索　
同语言下
可能有用的
suojiumian贡献的其它代码(1)
.A*搜索算法