利用BFS广度优先搜索还原二阶魔方

2023-03-20 04:42| 来源: 网络整理| 查看: 265

利用BFS广度优先搜索还原二阶魔方采用BFS深度优先搜索算法进行了对于魔方求解问题的建模，并且利用C++代码进行了算法实现，能够实现输入魔方状态，自动输出解法的效果。 BFS是图论中一种基本的搜索算法，用于遍历或搜索图数据结构。BFS从图中的某一起始节点开始，遍历图中所有与其相邻且未被访问的节点，并且以距离起始节点的距离来标记节点的访问状态。在搜索过程中，BFS使用队列这一数据结构来维护当前待遍历的节点，即先进先出的规则保证了每次处理离起始节点最近的未被访问的节点。当BFS访问到目标节点时，算法结束。BFS的时间复杂度为O(V+E)，其中V是图中节点的数量，E是图中边的数量。BFS通常用于解决最短路径问题，例如迷宫问题、地图路线规划、网络路由问题等。

利用BFS求解二阶魔方的关键点主要是：魔方状态的定义、操作的定义、搜索算法、检验是否还原、记录路径。接下来我们分别介绍。魔方状态的定义：本次作业我将二阶魔方定义为一个12乘2的二阶数组，在数组中填充魔方24个小块的颜色信息，具体分布格式可以看下图：在这里插入图片描述

Figure 1 位置分布图并且定义白色为1，绿色为2，红色为3，蓝色为4，橙色为5，黄色为6，将色彩信息填充到24个小格中，实现对于魔方颜色信息的定义。在代码中是通过结构体得以实现对于魔方状态的定义的。

// 魔方结构体，内容为魔方的状态和采取操作的队列 struct cube { int a[13][3]; queue steps; } init;

1、操作的定义：在本次作业中我将对于魔方的操作简化为三个操作：左面向下旋转，正面顺时针旋转，下面向右旋转。具体的实现方式见下图：在这里插入图片描述

Figure 2 左面向下旋转在这里插入图片描述

Figure 3 正面顺时针旋转在这里插入图片描述

Figure 4 下面向右旋转

代码实现如下，实现的思路就是将魔方状态二位数组进行转化：

// 对应操作左下 void move_1(cube t) { cube tmp; tmp = t; tmp.a[5][1] = t.a[1][1]; tmp.a[6][1] = t.a[2][1]; tmp.a[1][1] = t.a[10][2]; tmp.a[2][1] = t.a[9][2]; tmp.a[11][1] = t.a[5][1]; tmp.a[12][1] = t.a[6][1]; tmp.a[10][2] = t.a[11][1]; tmp.a[9][2] = t.a[12][1]; tmp.a[3][1] = t.a[4][1]; tmp.a[3][2] = t.a[3][1]; tmp.a[4][1] = t.a[4][2]; tmp.a[4][2] = t.a[3][2]; tmp.steps.push(1); if (check(tmp)) { cout_tmp(tmp); } q.push(tmp); }

2、搜索算法：搜索算法采用BFS，在C++的实现方法是通过队列结合递归，不断进行递归实现的。首先要定义一个容纳魔方状态结构体的队列

// 用于BFS算法，普通BFS算法使用队列实现 queue q;

然后构建BFS递归函数

// DFS void find_best() { if (flag) return; // cout

【本文地址】

公司简介

联系我们