通過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哈希