Li_阴宅

这个屌丝很懒，什么也没留下！

热门标签

A算法解决八数码问题（C语言实现）_八数码问题a算法c语言

作者：Li_阴宅 | 2024-07-04 12:03:36

踩

八数码问题a*算法c语言

准备两个表

待计算的节点保存在一个open表中，已经计算过的节点则保存在一个closed表中，其中的open表用一个优先队列表示，以使那些未访问过的节点可以按照其估价函数值的顺序出列。

估价函数

f(n) = g(n) + h(n)

g(n)为实际成本，在这里理解为深度depth，h(n)为启发式函数，在这里理解为当前节点相对目标矩阵节点的元素偏移量，即有多少个节点不在目标位置。

估价函数的计算

在这里用一维数组表示矩阵：右图为目标矩阵节点。

左图的g(n)为此时矩阵节点所在的深度，根节点的深度为0。

h(n)为8，因为有8个数字不在目标位置。

想法

初始矩阵变换到目标矩阵的过程，是一个数字移动的过程，相对来说，也是元素0移动的过程，元素0经过向四个方向的多次移动，最终到达了目标节点。

当初始矩阵与目标矩阵逆序数的奇偶性不相同的时候，节点不可达

目标节点：{1,2,3,4,5,6,7,8,0}，逆序数为8

其实节点：{1,6,5,3,8,2,7,4,0}，逆序数为20

两个节点逆序数奇偶性相同，可达。

核心算法astar伪代码


初始化open表、close表
将初始节点加入open表
while(open表不为空) {
	从open表中取出最佳节点node 
    if(node为目标节点) {
    	打印移动过程，循环结束 
    } else {
		for(扩展node所有的邻接节点child) {
			if(child存在于close表) {
    			抛弃child，进入下一次循环 
			}
			更新child节点的属性，包括pred、g、h、depth、blank
			if(child存在于open表) {
				留下最优的节点 
			} else {
				直接将child加入open表 
			}
		}
	}
}

代码（C语言实现）

头文件


#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX_BOARD 9
#define MAX_LIST_ELEMENTS	100000
#define ALPHA (double)1.0
#define BETA (double)2.0
#define MAX_DEPTH 26
#define MAX_VECTOR	4
 
#define RANDINIT()	srand(time(NULL))
#define listCount(x)	((x)->numElements)
#define RANDOM()	((float)rand() / (float)RAND_MAX)
#define RANDMAX(x)	(int)((float)(x)*rand()/(RAND_MAX+1.0))

结构体定义

定义矩阵节点board_t，列表list_t，在扩展时使用到的状态节点


typedef struct board_s {
	//前驱节点 
	struct board_s *pred;
	//f = h + g
	int f;
	int g;
	int h;
	
	char array[MAX_BOARD];
	char blank;
	char depth; 
}board_t;
 
typedef struct {
	//元素个数 
	int numElements;
	//存放指向 board_t 结构体类型的指针 
	board_t *elements[MAX_LIST_ELEMENTS];
}list_t;
 
typedef struct {
  int len;//当前节点0能移动的方向总数 
  int vector[MAX_VECTOR];//0能到达的位置 
} move_t;

初始化表


//创建open表和close表
list_t openList_p;
list_t closedList_p;
//完成表的初始化
void initList(list_t *list_p) {
	int i;
	list_p->numElements = 0;
	for(i = 0; i < MAX_LIST_ELEMENTS; i++) {
		list_p->elements[i] = (board_t*)0;
	}
	return;
}

初始化可达节点


void pri(board_t *child_p) {
	if(child_p != (board_t *)0) {
		printf("f = %d\n", child_p->f);
		printf("g = %d\n", child_p->g);
		printf("h = %d\n", child_p->h);
		printf("blank = %d\n", child_p->blank);
		printf("depth = %d\n", child_p->depth);
		printf("\n");	
	}
} 
 
//矩阵节点的初始化 
board_t *nodeAlloc() {
	board_t *board_p;
	board_p = (board_t*)malloc(sizeof(board_t));
	
	//当前状态的前驱默认为空
	board_p->pred = NULL;
	//fgh初始化为0 
	board_p->f = board_p->g = board_p->h = 0;
	
	return board_p;
}
 
//返回逆序数 
int countInversions(char *array) {
	int i, j, inversions = 0;
	for(i = 0; i < MAX_BOARD - 1; i++) {
		for(j = i + 1; j < MAX_BOARD; j++) {
			if(array[i] > array[j]) {
				inversions++;
			}
		}
	}
	return inversions;	
}
 
//计算位偏移量
int evaluateBoard(board_t *board_p) {
	int i;
	const int test[MAX_BOARD - 1] = {1,2,3,4,5,6,7,8};
	int score = 0;
	
	for(i = 0; i < MAX_BOARD - 1; i++) {
		if(board_p->array[i] != test[i]) {
			score++;
		}
	}
	return score;
}
 
//随机生成节点，直到节点可达然后返回
board_t *initPuzzle() {
	int i, inversions;
	board_t *board_p;
	
	board_p = nodeAlloc();
	//矩阵初始化为123456780 
	for(i = 0; i < MAX_BOARD - 1; i++) {
		board_p->array[i] = i + 1;
	}
	
	board_p->array[i] = 0;
 
	//开始循环，在和1按位与为0的时候结束循环。 
	do {
		//生成0-9的随机数，将矩阵打乱 
		for(i = 0; i < MAX_BOARD; i++) {
			int x = RANDMAX(MAX_BOARD);
			int y = RANDMAX(MAX_BOARD);
			
			int temp = board_p->array[x];
			board_p->array[x] = board_p->array[y];
			board_p->array[y] = temp;
		}
		
		for(int k = 0; k < MAX_BOARD; k++) {
			printf("%d ", board_p->array[k]);
		}
		printf("\n");
		//得到inversions，在inversion
		inversions = countInversions(board_p->array);
		
	} while(inversions & 1);
	
	//找0的位置
	for(i = 0; i < MAX_BOARD; i++) {
		if(board_p->array[i] == 0) {
			board_p->blank = i;
			break;
		}
	}
	
	board_p->f = board_p->h = evaluateBoard(board_p);
	
	board_p->depth = board_p->g = 0;
	return board_p;
}

将节点加入表


//向list队列中加入board_t节点
void putList(list_t *list_p, board_t *board_p) {
	for(int i = 0; i < MAX_LIST_ELEMENTS; i++) {
		if(list_p->elements[i] == (board_t*)0) {
			list_p->elements[i] = board_p;
			list_p->numElements++;
			return;
		}
	}
}

astar


void nodeFree(board_t *board_p) {
	free(board_p);
	return;
}
 
//找到f最小的节点，将该节点保存并返回，然后将该位置的值置为零 
board_t *getListBest(list_t *list_p)
{
  int i, first=1;
  int best=-1;
  double best_f;
  board_t *board_p;
 
  for (i = 0; i < MAX_LIST_ELEMENTS; i++) {
 
    if (list_p->elements[i]) {
 
      if (first) {
        best = i;
        best_f = list_p->elements[best]->f;
        first = 0;
      } else {
		//若节点重复出现，当前节点的f < 最好节点的 f，发生替换 
        if (list_p->elements[i]->f < best_f) {
          best = i;
          best_f = list_p->elements[best]->f;
        }
      }
    }
  }
  
  board_p = list_p->elements[best];
  list_p->elements[best] = (board_t *)0;
  list_p->numElements--;
 
  return board_p;
}
 
//判断当前节点是否在表中，其中的pos为指向int类型的指针变量，若节点存在于表中，使用pos返回存储的位置
int onList(list_t *list_p, char *board_p, int *pos) {
	int i, j;
	for(i = 0; i < MAX_LIST_ELEMENTS; i++) {
		//剪枝
		if(list_p->elements[i] != (board_t*)0) {
			for(j = 0; j < MAX_BOARD; j++) {
				//比较，若所有元素都相同则认为存在于表中
				if(list_p->elements[i]->array[j] != board_p[j]) {
					break;
				} 
			}
			if(j == MAX_BOARD) {
				if(pos)
					*pos = i;
				return 1;
			}
		} 
	}
	return 0;
}
 
board_t *getList(list_t *list_p, char *board_p) {
	int pos, ret;
	board_t *retboard_p = (board_t*)0;
	
	ret = onList(list_p, board_p, &pos);
	//如果存在于该队列中， 
	if(ret) {
		retboard_p = list_p->elements[pos];
		list_p->elements[pos] = (board_t *)0;
		list_p->numElements--;
	}
	return retboard_p;
}
 
 
 
//元素0在每个位置能够移动的方向，如第一行，在下标为0的位置有两个方向可以移动，分别为1和3
const move_t moves[MAX_BOARD] = {
       /* 0 */ { 2, {1, 3}       },
       /* 1 */ { 3, {0, 2, 4}    },
       /* 2 */ { 2, {1, 5}       },
       /* 3 */ { 3, {0, 4, 6}    },
       /* 4 */ { 4, {1, 3, 5, 7} },
       /* 5 */ { 3, {2, 4, 8}    },
       /* 6 */ { 2, {3, 7}       },
       /* 7 */ { 3, {4, 6, 8}    },
       /* 8 */ { 2, {5, 7}       }  };
 
board_t *getChildBoard(board_t *board_p, int index) {
	board_t *child_p = (board_t *)0;
	int i;
	//当前节点0所在的位置 
	int blankSpot = board_p->blank;
	
	//index条件成立时，表示该方向可走。 
	if(index < moves[blankSpot].len) {
		
		child_p = nodeAlloc();
		
		//将元节点进行拷贝，用于位置的移动 
		for(i = 0; i < MAX_BOARD; i++) {
			child_p->array[i] = board_p->array[i];
		}
		child_p->blank = board_p->blank;
		//moveFrom表示0移动到的下一个位置 
		int moveFrom = moves[blankSpot].vector[index];
		//位置移动
		child_p->array[(int)child_p->blank] = child_p->array[moveFrom];
		child_p->array[moveFrom] = 0;
		//更新0的位置 
		child_p->blank = moveFrom;
	}
//	pri(child_p);
	return child_p;
}
 
//矩阵以及信息打印
void emitPuzzleBoard( board_t *board ){
	int i;
	
	for (i = 0 ; i < MAX_BOARD ; i++) {
		if ((i%3) == 0)
			printf("\n");
		if (board->array[i] == 0)
			printf(" ");
		else
			printf("%c", 'A'+board->array[i]-1);
	}
	printf("\n");
	printf("f = %d, g = %d, h = %d\n", board->f, board->g, board->h); 
	printf("\n");
}
 
//展示结果
void showSolution(board_t *goal) {
	board_t *revList[MAX_LIST_ELEMENTS];
	int i = 0, j;
	
	printf("Solution:\n");
	//倒着存 
	while(goal) {
		revList[i++] = goal;
		goal = goal->pred;
	}
	//正着输 
	for (j = i-1; j >= 0; j--) {
		emitPuzzleBoard(revList[j]);
		printf("\n");
	}
}
 
//A*算法
void astar() {
	
	board_t *cur_board_p, *child_p, *temp;
	int i;
	
	while(listCount(&openList_p)) {
		//在open表中选取f最小的节点，并做销毁处理 
		cur_board_p = getListBest(&openList_p);
		//将已经运算过的节点加入colse表 
		putList(&closedList_p, cur_board_p);
		//
		if(cur_board_p->h == 0) {
			//展示形成过程
			showSolution(cur_board_p);
			return;	 
		} else {
			//扩展
			//到达一定的深度找不到结果就停止扩展 
			if(cur_board_p->depth > MAX_DEPTH) continue;
			
			//0能走四个方向
			for(i = 0; i < 4; i++) {
				child_p = getChildBoard(cur_board_p, i);
				
				if(child_p != (board_t *)0) {
					if(onList(&closedList_p, child_p->array, NULL)) {
						nodeFree(child_p);
            			continue;
					}
					//若不在close表中，则先处理该节点
					//深度+1
					child_p->depth = cur_board_p->depth + 1;
					//计算h 
	          		child_p->h = evaluateBoard(child_p);
					//计算g
	          		child_p->g = child_p->depth;
					//计算f = g + h
	          		child_p->f = (child_p->g * ALPHA) + (child_p->h * BETA);
					//判断该新节点是否存在于open表
					if(onList(&openList_p, child_p->array, NULL)) {
						//若存在则取出该节点 
						temp = getList(&openList_p, child_p->array);
						//比较
						if(temp->g < child_p->g) {
							nodeFree(child_p);
							//新的节点g值大，将原本open表的节点放回 
							putList(&openList_p, temp);
						} else {
							child_p->pred = cur_board_p;
							putList(&openList_p, child_p);
						}
						nodeFree(temp);
					} else {
						//若不存在，直接加入open表，当前节点为扩展节点的父节点 
						child_p->pred = cur_board_p;
						putList(&openList_p, child_p);
					}
				}
			}
		}
	}
}

资源释放


//清空表 
void cleanupList(list_t *list_p) {
	int i;
	for (i = 0; i < MAX_LIST_ELEMENTS; i++) {
		if (list_p->elements[i] != (board_t *)0) {
		  nodeFree(list_p->elements[i]);
		  list_p->numElements--;
		}
	}
	return;
}

主函数


int main() {
	//初始节点状态，声明指向 board_t结构体类型的指针 
	board_t *initial_p;
	//设置随机种子，用作随机数的生成 
	RANDINIT();
	//初始化open表
	initList(&openList_p);
	//初始化close表
	initList(&closedList_p);
	//随机生成节点
	initial_p = initPuzzle();
	//将节点放入open表
	putList(&openList_p, initial_p);
	//astar
	astar();
	//清空open表
	cleanupList(&openList_p);
	//清空close表 
	cleanupList(&closedList_p);
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/786742

A*算法解决八数码问题（C语言实现）_八数码问题a*算法c语言