投稿
  1. 首页
  2. C

八数码的3种解法详解 dfs bfs A*算法 c++ 代码有注释

code • 2022-4-2 • C • 阅读 108

八数码的3种解法详解 dfs bfs A*算法 c++ 代码有注释,第1张

八数码的3种解法 八数码难题

3×3九宫棋盘，放置数码为1-8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。


输入示例：

2 0 3
1 8 4
7 6 5

1 2 3
8 0 4
7 6 5

8 3 4
2 6 5
1 7 0

1 2 3
8 0 4
7 6 5

2 1 6
4 0 8
7 5 3

1 2 3
8 0 4
7 6 5

3 1 8
7 6 4
0 2 5

1 2 3
8 0 4
7 6 5

根据题意，需要求解的问题是：给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局

方法1 宽度优先搜索

宽度优先搜索属于盲目搜索的一种，不需进行OPEN表的排序

基本思路：

  1. 设置一个OPEN表，来存放打算访问的矩阵，一个CLOSE表，存放已经访问过的矩阵
  2. 将初始矩阵加入OPEN表
  3. 取出OPEN表中首元素，判断其是否等于目标矩阵，否则找到初始矩阵中0的位置
  4. 将0分别和上、下、左、右的元素交换位置，首先判断是否越界，不越界的话，交换后生成的矩阵是否已在CLOSE表或OPEN表中，如果均不在，则将其加入OPEN表中
  5. 将OPEN表中的首元素从OPEN中删除，并加入CLOSE表，重复3-5步骤直至OPEN表为空或OPEN表中首元素等于目标矩阵

代码：

#include
using namespace std;
typedef struct node{
	int m[3][3],parent = -1;
	// m是状态矩阵，parent是父节点 
}M;
int equal(M a, M b){
	// 比较两个矩阵是否相等，相等返回1，不相等返回0 
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			if(a.m[i][j] != b.m[i][j])
				return 0;
	return 1;
}
void printM(M a){
	// 打印M中的矩阵 
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++)
			cout << a.m[i][j];
		cout << endl; 
	}
	cout << endl;
}
vector <M> OPEN,CLOSE; // 使用动态数组充当OPEN表、CLOSE表 
int ifFindAnswer = 0,cnt; // cnt为OPEN的指针，控制搜索的进度 
int opt[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; 
     // *** 作集      上    下    左     右 
int main(){
	M *s0,*sg,front;// s0:初始状态，sg：最终状态，front：每次OPEN中取出队首元素 
	int x,y; // 用来记录0（即空格）的位置 
	s0 = (struct node *)malloc(sizeof(struct node));
	sg = (struct node *)malloc(sizeof(struct node));
	cout << "请输入初始状态：（请用0代替空格）" << endl;
	// 读入初始状态和最终状态 
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			cin >> s0->m[i][j];
	cout << "请输入目标状态：（请用0代替空格）" << endl;
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			cin >> sg->m[i][j];
	// 将s[0]放入队列第一个 
	OPEN.push_back(*s0);
	while(OPEN.size() != cnt){
		front = OPEN[cnt];
		// 判断是否找到答案 ，如果是，退出循环 
		if(equal(front,*sg) == 1){
			ifFindAnswer = 1;
			break;
		}
		// 1.查找0（也就是空格）位置并记录 
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				if(front.m[i][j] == 0){
					x = i;
					y = j;
					break;
				}
			}
		}
		for(int i = 0; i < 4; i++){
			int flag = 1;
			// 先判断移动后是否合法 
			if(x+opt[i][0] > -1 && x+opt[i][0] < 3 && y+opt[i][1] > -1 && y+opt[i][0] < 3){
				M temp = front;
				swap(temp.m[x][y],temp.m[x+opt[i][0]][y+opt[i][1]]);
				// 判断是否已探索过该节点 
				for(int j = 0; j < CLOSE.size(); j++){
					if(equal(CLOSE[j],temp) == 1) {
						flag = 0;
						break;	
					}
				}
				// 判断是否是已加入OPEN，但未探索的结点 
				for(int i = x+1; i < OPEN.size(); i++){
					if(equal(OPEN[i],temp) == 1){
						flag = 0;
						break; 
					}
				}
				if(flag == 1){
					// flag==1，未探索过该节点，将结点加入OPEN
					temp.parent = cnt;
					OPEN.push_back(temp); 
				}
			}else continue; 
		}
		CLOSE.push_back(OPEN[cnt++]);
	}
	if(ifFindAnswer == 0){
		cout << "找不到路径!!";
	}else{
		// 找到答案，递归输出路径
		cout << "找到路径，路径是：" << endl; 
		stack <M> ans;
		ans.push(OPEN[cnt]);
		while(ans.top().parent != 0){
			ans.push(OPEN[ans.top().parent]);
		} 
		ans.push(OPEN[0]);
		while(ans.size() != 0){
			printM(ans.top());
			ans.pop();
		} 
	}
}
方法2 深度优先搜索

深度优先搜索也属于盲目搜索的一种，不需进行OPEN表的排序

基本思路：经典DFS暴力搜索，访问前通过遍历OPEN表判断是否访问过该矩阵，没访问则将其加入OPEN表并进行访问，访问过则不再进行访问，知道找到解为止。


#include
using namespace std;
typedef struct node{
	int m[3][3],parent = -1;
	// m是状态矩阵，parent是父节点 
}M;
int equal(M a, M b){
	// 比较两个矩阵是否相等，相等返回1，不相等返回0 
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			if(a.m[i][j] != b.m[i][j])
				return 0;
	return 1;
}
void printM(M a){
	// 打印M中的矩阵 
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++)
			cout << a.m[i][j];
		cout << endl; 
	}
	cout << endl;
}
vector <M> OPEN,CLOSE; // 使用动态数组充当OPEN表、CLOSE表 
M *s0,*sg;// s0:初始状态，sg：最终状态，front：每次OPEN中取出队首元素 
int ifFindAnswer = 0,cnt,ans; // cnt为OPEN的指针，控制搜索的进度 ans记录答案的位置 
int opt[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; 
     // *** 作集      上    下    左     右 
void dfs(M a){
	// 如果已找到答案，就结束 
	if(ifFindAnswer == 1) return;
	OPEN.push_back(a);
	int tempcnt = cnt++;
	if(equal(a,*sg) == 0){
		int x,y;// x,y记录0的位置 
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				if(a.m[i][j] == 0){
					x = i;
					y = j;
					break;
				}
		for(int i = 0; i < 4; i++){
			int flag = 1;
			// 先判断是否越界
			if(x+opt[i][0] > -1 && x+opt[i][0] < 3 && y+opt[i][1] > -1 && y+opt[i][0] < 3){
				M temp = a;
				swap(temp.m[x][y],temp.m[x+opt[i][0]][y+opt[i][1]]);
				// 判断是否已访问 
				for(int j = 0; j < OPEN.size(); j++){
					if(equal(OPEN[j],temp) == 1){
						flag = 0;
						break;
					}
				} 
				// 如果没访问过，直接访问
				if(flag == 1){
					cout << tempcnt << endl;
					temp.parent = tempcnt;
					dfs(temp);
				} 
			}
		} 
	}else{
		ifFindAnswer = 1;
		ans = tempcnt;
	} 
} 
int main(){
	s0 = (struct node *)malloc(sizeof(struct node));
	sg = (struct node *)malloc(sizeof(struct node));
	cout << "请输入初始状态：（请用0代替空格）" << endl;
	// 读入初始状态和最终状态 
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			cin >> s0->m[i][j];
	cout << "请输入目标状态：（请用0代替空格）" << endl;
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			cin >> sg->m[i][j];
	dfs(*s0);
	if(ifFindAnswer == 1){
		// 找到答案，递归输出路径
		stack <M> path;
		path.push(OPEN[ans]);
		while(path.top().parent != 0){
			path.push(OPEN[path.top().parent]);
		} 
		path.push(OPEN[0]);
		while(path.size() != 0){
			printM(path.top());
			path.pop();
		} 
	}else{
		cout << "路径不存在！！" << endl; 
	}
}
方法3 A*算法

A*算法属于启发式搜索，想要看懂它，需要先科普一些背景知识：

启发式信息：用来加速搜索过程的有关问题领域的特征信息，用于决定要拓展的我下一个节点的信息，用于决定某些应该从搜索树种抛弃或修剪的节点的信息

启发式搜索：使用启发式信息的搜索方法称为启发式搜索方法

估价函数：用来估算节点处于最佳求解路径上的希望程度的函数，是启发式搜索用来搜索书中

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

  • n：搜索图中的某个当前被拓展的节点
  • f(n)：从初始状态节点s，经由节点n到达目标节点ng,估计的最小路径代价
  • g(n)：从s到n的实际路径代价
  • h(n)：从n到ng估计的最小路径代价

本题的估价函数：f(n) = d(n) + w(n)

其中：d(n)为n的深度

w(n)为不在位的棋子数

本体思路：基于宽度优先搜索的基础上，每次将新节点加入OPEN表后，将OPEN表根据f(n)进行排序，然后再重复宽度优先搜索的思路。


#include
using namespace std;
typedef struct node{
	int m[3][3]; // 状态矩阵 
	int d; // 深度 
	int w; // 不在位的棋子数 
	int f; // = d + w
	struct node * parent; // 父节点 
}M; 

bool cmp(M a,M b);
int f(M a);
int equal(M a,M b);

int ifFindAnswer = 0,cnt; // cnt为OPEN的正在搜索的点下标，控制搜索的进度 
vector <M> OPEN,CLOSE;
M *s0,*sg;
int opt[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; 
    // *** 作集       上    下    左     右 
bool cmp(M a,M b){
	// 根据f(n)进行排序 
	if(a.f != b.f) return a.f < b.f; 
	return a.d > b.d;
}
int f(M a){
	// 计算估价函数 f(n) = d(n) + w(n) 
	int f = 0;
	a.w = 0;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			if(a.m[i][j] != sg->m[i][j]){
				a.w++;
			}
		}
	}
	f = a.w + a.d;
	return f;
} 
int equal(M a,M b){
	// 判断两个矩阵是否相等 
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			if(a.m[i][j] != b.m[i][j])	return 0;
		}
	}
	return 1;
}
int main(){
	int x,y;
	M front;
	s0 = (struct node *)malloc(sizeof(struct node));
	sg = (struct node *)malloc(sizeof(struct node));
	cout << "请输入初始状态：（请用0代替空格）" << endl;
	// 读入初始状态和最终状态 
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			cin >> s0->m[i][j];
	cout << "请输入目标状态：（请用0代替空格）" << endl;
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			cin >> sg->m[i][j];
	s0->d = 999;
	s0->f = f(*s0);
	s0->parent = NULL;
	OPEN.push_back(*s0);
	while(OPEN.size() != 0){
		front = OPEN[0];
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				printf("%d ",front.m[i][j]);
			}
			printf("\n");
		}
		printf("----------------------\n");
		CLOSE.push_back(OPEN[0]);
		if(equal(front,*sg) == 1){
			ifFindAnswer = 1;
			break;
		}
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				if(front.m[i][j] == 0){
					x = i;
					y = j;
					break;
				}
			}
		}
		for(int i = 0; i < 4; i++){
			int flag = 1;
			if(x+opt[i][0] > -1 && x+opt[i][0] < 3 && y+opt[i][1] > -1 && y+opt[i][1] < 3){
				M temp = front;
				swap(temp.m[x][y],temp.m[x+opt[i][0]][y+opt[i][1]]);
				// 判断是否已探索过该节点 
				for(int j = 0; j < CLOSE.size(); j++){
					if(equal(CLOSE[j],temp) == 1) {
						flag = 0;
						break;	
					}
				}
				// 判断是否是已加入OPEN，但未探索的结点 
				for(int i = 0; i < OPEN.size(); i++){
					if(equal(OPEN[i],temp) == 1){
						flag = 0;
						break; 
					}
				}
				if(flag == 1){
					// flag==1，未探索过该节点，将结点加入OPEN
					temp.d = front.d+1;
					temp.f = f(temp);
					temp.parent = &CLOSE[CLOSE.size()-1];
					OPEN.push_back(temp); 
				}
			}else continue; 
		}
		OPEN.erase(OPEN.begin());
		sort(OPEN.begin(),OPEN.end(),cmp);
	}
	if(ifFindAnswer == 0){
		cout << "找不到路径!!";
	}else{
		cout << "存在路径!!" << endl; 
	}
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/562667.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表（0条）

保存