通过Astar算法实现8数码问题(C语言)

关于A*(Astar)算法的介绍可以参考另一篇博文: A*(Astar)搜索算法的实现(C语言)

1.问题描述

在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

2.问题可解性

八数码问题的一个状态实际上是0~9的一个排列，对于任意给定的初始状态和目标，不一定有解，也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列或相反。如果一个数字0~8的随机排列871526340，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。例如871526340这个排列的 Y=0+0+0+1+1+3+2+3+0=10 10是偶数，所以他偶排列。871625340 Y=0+0+0+1+1+2+2+3+0=9 9是奇数，所以他奇排列。因此，可以在运行程序前检查初始状态和目标状态的窘是否相同，相同则问题可解，应当能搜索到路径。否则无解。

3.求解步骤

1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。 2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。 3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。 4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。 5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。

4.代码实现

二叉堆代码就不贴出来了，在另一篇博文 A*(Astar)搜索算法的实现(C语言) 中已经给出，在本文最后有资源下载的链接。可以拿到完整的代码 astar_8.h

/*
* author:	Atom
* date:		2012/12/04
* file:		astar_8.h
*/
#ifndef ASTAR_8_H
#define ASTAR_8_H

#include "bheap.h"

#define MALLOC(type,n)  (type *)malloc((n)*sizeof(type))

#define MAX(a,b) ((a)>(b))?(a):(b)

#define UP  		-3
#define RIGHT 	1
#define DOWN		3
#define LEFT		-1

int node_distance[9][9];

struct step_node
{
	int step_status[9];
	int f;
	int g;
	int h;
	struct step_node* parent;
};

int _comp(struct Bheap_node* n1, struct Bheap_node* n2);

int _eq(struct Bheap_node* n1, struct Bheap_node* n2);

void astar_8(int start[9], int end[9]);

static int calc_distance(int step_status[9], int end[9]);

static int arr_idx(int n, int step_status[9]);

static void init_node_distance(int node_distance[9][9]);

static int is_end(int step_status[9], int end[9]);

static int is_reachable(int space_idx, int flag);

static int move_space(int step_status[9], int flag);

static void print_step_status(int step_status[9]);

static int check_whether_reach(int start[9], int end[9]);

#endif

astar_8.c

/*
* author:	Atom
* date:		2012/12/04
* file:		astar_8.c
*/
#include "astar_8.h"


int main(int argc, char* argv[])
{
	int i,j;
	
	init_node_distance(node_distance);
	int start[] = {2,3,4,1,8,5,0,7,6};
	int end[] = {1,2,3,8,0,4,7,6,5};
#if 1
	if(check_whether_reach(start, end))
	{
		printf("sorry,No solution!\n");
	}
	else
		astar_8(start, end);
#else
		astar_8(start, end);
#endif
	return (0);
}
static int check_whether_reach(int start[9], int end[9])
{
	int re_st = 0, re_end = 0;
	int tmp = 0;
	int i, j;
	for (i = 0; i < 9; i++)
	{
		for(j = 0; j < i; j++)
			if (start[i] > start[j])
				re_st++;
	}
	
	for (i = 0; i < 9; i++)
	{
		for(j = 0; j < i; j++)
			if (end[i] > end[j])
				re_end++;
	}

	return ((re_st^re_end)&0x01);
}
void astar_8(int start[9], int end[9])
{
	int space_idx;
	int* tmp_step = NULL;
	struct Bheap *o_heap = NULL, *c_heap = NULL;
	struct Bheap_node *inode = NULL, *onode = NULL;
	struct step_node *fnode = NULL;
	struct step_node *omnode = NULL;
	struct Bheap_node *exist_node = NULL;
	size_t idx;
	
	o_heap = Bheap_create(128, BHEAP_TYPE_SMALL);
	c_heap = Bheap_create(128, BHEAP_TYPE_SMALL);
	
	/* 第一步判断可否由start状态到end状态 */
	
	/* 将起始点入open heap */
	if (NULL == (fnode = MALLOC(struct step_node, 1)))
	{
		fprintf(stderr, "malloc fnode error!\n");
		return;
	}
	
	if (NULL == (inode = MALLOC(struct Bheap_node, 1)))
	{
		fprintf(stderr, "malloc inode error!\n");
		return;
	}
	
	if (NULL == (tmp_step = MALLOC(int, 9)))
	{
		fprintf(stderr, "malloc tmp_step error!\n");
		return;
	}

	memset(fnode, 0x00, sizeof(struct step_node));
	memset(inode, 0x00, sizeof(struct Bheap_node));
	memset(tmp_step, 0x00, sizeof(int) * 9);
	
	memcpy(fnode->step_status, start, sizeof(int) * 9);
	fnode->g = 0;
	fnode->h = calc_distance(fnode->step_status, end);
	fnode->f = fnode->g + fnode->h;
	fnode->parent = NULL;

	inode->value = fnode;	
	Bheap_push(o_heap, inode, _comp);
	
	for ( ; ; )
	{
		omnode = NULL;
		
		if (NULL == (onode = Bheap_pop(o_heap, _comp)))
		{
			break;
		}
		else
		{
			omnode = (struct step_node*)onode->value;
			if (is_end(omnode->step_status, end))
				break;
			Bheap_push(c_heap, onode, _comp);
			
			memset(tmp_step, 0x00, sizeof(int) * 9);
			memcpy(tmp_step, omnode->step_status, sizeof(int) * 9);
			space_idx = arr_idx(0, tmp_step);
			/* 上 */
			if (is_reachable(space_idx, (UP)))
			{
				fnode = NULL;
				inode = NULL;
				if (NULL == (fnode = MALLOC(struct step_node, 1)))
				{
					fprintf(stderr, "malloc fnode error!\n");
					return;
				}
	
				if (NULL == (inode = MALLOC(struct Bheap_node, 1)))
				{
					fprintf(stderr, "malloc inode error!\n");
					return;
				}
				
				move_space(tmp_step, (UP));
				memcpy(fnode->step_status, tmp_step, sizeof(int) * 9);
				fnode->g = omnode->g + 1;
				fnode->h = calc_distance(tmp_step, end);
				fnode->f = fnode->g + fnode->h;
				fnode->parent = omnode;
				inode->value = fnode;
				/* 不在open heap和closed heap 中 */
				if (-1 == is_Bheap_contain(o_heap, inode, _eq) 
					&& -1 == is_Bheap_contain(c_heap, inode, _eq))
				{
					Bheap_push(o_heap, inode, _comp);
					if (is_end(tmp_step, end))
						continue;
				}
				else if(-1 != (idx = is_Bheap_contain(o_heap, inode, _eq)))
				{
					/* 在open heap 中*/
					if (NULL != (exist_node = Bheap_get(o_heap, idx)))
					{
						if (fnode->f < ((struct step_node *)exist_node->value)->f)
						{
							((struct step_node *)(exist_node->value))->f = fnode->f;
							((struct step_node*)(exist_node->value))->parent = fnode->parent;
						}
					}
					free(fnode);
					free(inode);
				}
				else
				{
					free(fnode);
					free(inode);
				}
				
				Bheap_push(c_heap, onode, _comp);
			}
			
			memset(tmp_step, 0x00, sizeof(int) * 9);
			memcpy(tmp_step, omnode->step_status, sizeof(int) * 9);
			space_idx = arr_idx(0, tmp_step);
			/* 下 */
			if (is_reachable(space_idx, (DOWN)))
			{
				
				fnode = NULL;
				inode = NULL;
				if (NULL == (fnode = MALLOC(struct step_node, 1)))
				{
					fprintf(stderr, "malloc fnode error!\n");
					return;
				}
	
				if (NULL == (inode = MALLOC(struct Bheap_node, 1)))
				{
					fprintf(stderr, "malloc inode error!\n");
					return;
				}
				move_space(tmp_step, (DOWN));
				memcpy(fnode->step_status, tmp_step, sizeof(int) * 9);
				fnode->g = omnode->g + 1;
				fnode->h = calc_distance(tmp_step, end);
				fnode->f = fnode->g + fnode->h;
				fnode->parent = omnode;
				inode->value = fnode;
				/* 不在open heap和closed heap 中 */
				if (-1 == is_Bheap_contain(o_heap, inode, _eq) 
					&& -1 == is_Bheap_contain(c_heap, inode, _eq))
				{
					Bheap_push(o_heap, inode, _comp);
					if (is_end(tmp_step, end))
						continue;
				}
				else if(-1 != (idx = is_Bheap_contain(o_heap, inode, _eq)))
				{
					/* 在open heap 中*/
					if (NULL != (exist_node = Bheap_get(o_heap, idx)))
					{
						if (fnode->f < ((struct step_node *)exist_node->value)->f)
						{
							((struct step_node *)(exist_node->value))->f = fnode->f;
							((struct step_node*)(exist_node->value))->parent = fnode->parent;
						}
					}
					free(fnode);
					free(inode);
				}
				else
				{
					free(fnode);
					free(inode);
				}
				
				Bheap_push(c_heap, onode, _comp);
			}
			
			memset(tmp_step, 0x00, sizeof(int) * 9);
			memcpy(tmp_step, omnode->step_status, sizeof(int) * 9);
			space_idx = arr_idx(0, tmp_step);
			/* 左 */
			if (is_reachable(space_idx, (LEFT)))
			{
				
				fnode = NULL;
				inode = NULL;
				if (NULL == (fnode = MALLOC(struct step_node, 1)))
				{
					fprintf(stderr, "malloc fnode error!\n");
					return;
				}
	
				if (NULL == (inode = MALLOC(struct Bheap_node, 1)))
				{
					fprintf(stderr, "malloc inode error!\n");
					return;
				}
				move_space(tmp_step, (LEFT));
				memcpy(fnode->step_status, tmp_step, sizeof(int) * 9);
				fnode->g = omnode->g + 1;
				fnode->h = calc_distance(tmp_step, end);
				fnode->f = fnode->g + fnode->h;
				fnode->parent = omnode;
				inode->value = fnode;
				/* 不在open heap和closed heap 中 */
				if (-1 == is_Bheap_contain(o_heap, inode, _eq) 
					&& -1 == is_Bheap_contain(c_heap, inode, _eq))
				{
					Bheap_push(o_heap, inode, _comp);
					if (is_end(tmp_step, end))
						continue;
				}
				else if(-1 != (idx = is_Bheap_contain(o_heap, inode, _eq)))
				{
					/* 在open heap 中*/
					if (NULL != (exist_node = Bheap_get(o_heap, idx)))
					{
						if (fnode->f < ((struct step_node *)exist_node->value)->f)
						{
							((struct step_node *)(exist_node->value))->f = fnode->f;
							((struct step_node*)(exist_node->value))->parent = fnode->parent;
						}
					}
					free(fnode);
					free(inode);
				}
				else
				{
					free(fnode);
					free(inode);
				}
				
				Bheap_push(c_heap, onode, _comp);
			}
			
			memset(tmp_step, 0x00, sizeof(int) * 9);
			memcpy(tmp_step, omnode->step_status, sizeof(int) * 9);
			space_idx = arr_idx(0, tmp_step);
			/* 右 */
			if (is_reachable(space_idx, (RIGHT)))
			{
				
				fnode = NULL;
				inode = NULL;
				if (NULL == (fnode = MALLOC(struct step_node, 1)))
				{
					fprintf(stderr, "malloc fnode error!\n");
					return;
				}
	
				if (NULL == (inode = MALLOC(struct Bheap_node, 1)))
				{
					fprintf(stderr, "malloc inode error!\n");
					return;
				}
				move_space(tmp_step, (RIGHT));
				memcpy(fnode->step_status, tmp_step, sizeof(int) * 9);
				fnode->g = omnode->g + 1;
				fnode->h = calc_distance(tmp_step, end);
				fnode->f = fnode->g + fnode->h;
				fnode->parent = omnode;
				inode->value = fnode;
				/* 不在open heap和closed heap 中 */
				if (-1 == is_Bheap_contain(o_heap, inode, _eq) 
					&& -1 == is_Bheap_contain(c_heap, inode, _eq))
				{
					Bheap_push(o_heap, inode, _comp);
					if (is_end(tmp_step, end))
						continue;
				}
				else if(-1 != (idx = is_Bheap_contain(o_heap, inode, _eq)))
				{
					/* 在open heap 中*/
					if (NULL != (exist_node = Bheap_get(o_heap, idx)))
					{
						if (fnode->f < ((struct step_node *)exist_node->value)->f)
						{
							((struct step_node *)(exist_node->value))->f = fnode->f;
							((struct step_node*)(exist_node->value))->parent = fnode->parent;
						}
					}
					free(fnode);
					free(inode);
				}
				else
				{
					free(fnode);
					free(inode);
				}
				Bheap_push(c_heap, onode, _comp);
			}
		}
	}
	
	if (NULL == omnode)
	{
		printf("not found!\n");
	}
	else
	{
		while(NULL != omnode)
		{
			print_step_status(omnode->step_status);
			printf("\n");
			omnode = omnode->parent;
		}
			
	}
	
}

static int arr_idx(int n, int step_status[9])
{
	int cnt;
	for(cnt = 0; cnt < 9; cnt++)
		if (n == step_status[cnt])
			return cnt;
	
	return (-1);
}

static void init_node_distance(int node_distance[9][9])
{
	int i, j, val;
	
	for (i = 0; i < 9; i++)
	{
		for (j = 0; j < 9; j++)
		{
			val = abs(i - j);
			node_distance[i][j] = (int)val/3 + val%3;
		}
	}
}

static int calc_distance(int step_status[9], int end[9])
{
	int i, tmp, ret_val = 0;
	for (i = 0; i < 9; i++)
		if (-1 != (tmp = arr_idx(step_status[i], end)))
			ret_val += node_distance[i][tmp];
	
	return (ret_val);
}

static int is_end(int step_status[9], int end[9])
{
	int i;
	for (i = 0; i < 9; i++)
		if (step_status[i] != end[i])
			return (0);
	
	return (1);
}

static int is_reachable(int space_idx, int flag)
{
	int x,y;
	
	x = space_idx/3;
	y = space_idx%3;
	
	if(((UP) == flag) && (x > 0))
		return (1);
	else if (((DOWN) == flag) && (x < 2))
		return (1);
	else if (((LEFT) == flag) && (y > 0))
		return (1);
	else if(((RIGHT) == flag) && (y < 2))
		return (1);
	else
		return (0);
}

static int move_space(int step_status[9], int flag)
{
	int zero_idx, tmp;
	zero_idx = arr_idx(0, step_status);
	tmp = step_status[zero_idx];
	
	/* 交换空格的位置 */
	if (((UP) == flag) || ((DOWN) == flag) || ((LEFT) == flag) || ((RIGHT) == flag))
	{
		step_status[zero_idx] = step_status[zero_idx + flag];
		step_status[zero_idx + flag] = tmp;

		return (0);
	}
	
	return (-1);
}

static void print_step_status(int step_status[9])
{
	int i;
	for(i = 0; i < 9; i++)
	{
		printf("%d ", step_status[i]);
		if (0 == ((i+1)%3) && (i != 0))
			printf("\n");
	}
}


/* Bheap_compare_t 函数实现 */
int _comp(struct Bheap_node* n1, struct Bheap_node* n2)
{
	struct step_node *sn1 = NULL, *sn2 = NULL;

	if ((NULL != n1) && (NULL != n2))
	{
		sn1 = (struct step_node*)n1->value;
		sn2 = (struct step_node*)n2->value;

		if (sn1->f > sn2->f)
			return (1);
		else if(sn1->f == sn2->f)
			return (0);
		else
			return (-1);
	}
	else
		return (0);
}

/* Bheap_equal_t 函数实现 */
int _eq(struct Bheap_node* n1, struct Bheap_node* n2)
{
	struct step_node *sn1 = NULL, *sn2 = NULL;

	if ((NULL != n1) && (NULL != n2))
	{
		sn1 = (struct step_node*)(n1->value);
		sn2 = (struct step_node*)(n2->value);
		return calc_distance(sn1->step_status, sn2->step_status);
	}
	else
		return (0);
}

执行结果:

通过Astar算法实现8数码问题(C语言)

代码包下载: 八数码问题实现(C语言) Github地址: https://github.com/xielianghai/astar_8

通过Astar算法实现8数码问题(C语言)

1.问题描述

2.问题可解性

3.求解步骤

4.代码实现

继续阅读

浮点数计算精度控制

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

[转]九大排序算法——C语言实现及详解

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

QR码编码原理三（日本汉字和中文编码）

hdu7108哈希