Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
八数码问题c++代码_c语言怎么把两个数组合成一个数组,希望能够帮助你!!!。

八数码实验报告

一、编程语言及环境

语言C++

环境：Visual Studio 2019

二、实验原理算法说明

2.1 问题说明：

八数码问题是指这样一种游戏：将分别标有数字 1，2，3，…，8 的八块正方形数码牌任意地放在一块 3 * 3 的数码盘上。放牌时要求不能重叠。于是，在 3*3 的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。

2.2 问题分析：

八数码问题包括一个初始状态和目标状态，所谓解八数码问题就是在两个状态间寻找一系列可过渡状态。从一个状态出发，找到空位后有最多四种变换方式，一层一层创建树形结构。

这个状态可以有很多种表示方法。第一种是使用 int 表示，这种方法的好处是可以压缩空间，但是这仅使用于八数码问题，如果扩展到 15 数码将无法表示。第二种是使用一维数组，一维数组是较好的一种兼顾空间和时间的表示方法，但是在扩展 15 数码时需要重新对位置转换进行计算。第三种是使用多维数组表示，这种表示方法的好处是简单明了，易于扩充，且可以很方便地看出运行过程，弊端就是时间和空间上的消耗。在本次实验中我选择使用构造节点进行搜索，一个节点就是一个二维数组及其他属性，因此可以清晰地观测搜索顺序及运行结果。

其次要解决的问题是如何判断初始状态到目标状态是否是可达的。两个状态之间是否可达，可以通过计算两者的逆序值，若两者奇偶性相同则可达，不然两个状态不可达。从 3*3 棋盘上可知，移动方式分为上下左右四种，左右移动不会改变逆序数，而上下移动增加 2 或减少 2。因此，如果初始排列和目标排列逆序数奇偶性相同，就认为是有解的。除了使用逆序数判断还可以通过判断 Open 表是否为空来判断。如果状态是可达的，那么最终在 Open 表一定有一个与目标节点相同的节点，此为该题的解，若无解，运行结束后 Open 表为空。这里选择使用搜索前先进行判断即逆序数方法。

在搜索中还有一个需要解决的问题是避免重复搜索，否则有可能进入循环状态。每次得到的新节点与已经搜索过的节点做比较，如果均不相同就说明是可行的，否则就是重复的。

2.3 准备工作：

1. 用逆序数同奇偶判断是否有解。

2. 判断是否为重复搜索节点。使用 is_expandable()和 is_equal()两个函数达到目的。所有搜索过的节点均存储在容器 node_v 中，依次与容器中的节点比较，如果均不相同说明可扩展。

3. 为了较好的输出格式，重写<<。

4. 回溯法输出路径。

2.4 核心算法：

广度优先搜索（BFS）

广度搜索是以接近起始节点的程度一次扩展节点，逐层搜索，在对下一层节点搜索前必须搜索完本层的所有节点。

广度搜索在八数码问题中的应用如下：将新节点放入 Open 表，然后寻找当前节点的空位，并进行上下左右移动，得到的新节点放入 Open 表，将当前节点放入 Close 表。

首次定义为节点定义一个结构体，其中 index 是父节点在 vector 中的下标。

Open 表使用 vector 动态数组实现，若扩展得到的新节点和目标节点相同，就返回当前该节点在 vector 中的下标，即最后一个位置；若和目标节点不同，返回 -1。

深度优先搜索（DFS）

深度搜索是扩展最深的节点，这使得搜索沿着状态空间的某条单一路径从起始节点向下进行，只有当搜索到叶节点的状态时才考虑另外一条路径。为了避免考虑太长的路径，防止搜索过程沿着无益的路径扩展下去，往往给出一个扩展的最大深度界限。任何节点如果达到了深度界限都将作为没有后继节点处理。

深度搜索在八数码问题上的应用如下：考察当前节点是否为目标节点，若不是目标节点则将新节点放入 Open 表前端，这里可以使用栈来辅助运行；若是得到的节点与目标节点相同，使用回溯法打印查询路径。

为一个节点定义一个结构体，self 为当前节点在 vector 中的位置，设置 bool 变量维护搜索状态，初始均未被搜索。

设置深度限度为 7（根节点深度为 0）。未到达深度限度且栈顶元素未被搜索过，将栈顶元素作为当前节点进行搜索，该节点的空位向上下左右四个方向移动后，将可扩展节点依次放入栈和容器中，如果与目标节点相同，返回该节点在容器中的位置，回溯打印路径；否则返回-1。已到达最大深度或栈顶元素已被搜索过，直接弹出，考虑新的栈顶元素。

启发式搜索（A*）

启发式搜索是在路径搜索问题中很使用的搜索方式，通过设计一个好的启发式函数来计算状态的优先级，优先考虑优先级高的状态，可以提早搜索到达目标态的时间。

A*算法的核心是启发式函数 f=g+h，g 是初始节点到节点 n 的一条最佳路径的实际代价，可以用节点所在层数来表示；h 是节点 n 与目标节点的预测距离，可以使用曼哈顿距离计算，每移动一步相当于移动一个数字，如果每次移动都是完美的，那么从初始态到目标态的距离就是曼哈顿距离，也是最少要走的步数。Open 表使用 vector 动态数组，Close 表通过将 h 标记为MAXNUM 达到已搜索过的效果。

首先为一个节点定义一个结构体，src 为初始状态节点，dest 为最终状态节点。

获取 Open 表中估价值最小的节点并将其作为可扩充节点继续向下搜索子节点，每次搜索需要计算估价值。Distance 用于计算 h(n)，g(n)深度递增 1。直到得到目标节点，按照父节点标记向上回溯打印变换过程。

将节点放入 Open 表的过程分别是先查找空位，向上、下、左、右移动判断是否为可扩充节点。

Distance 使用曼哈顿距离计算启发函数

A*算法流程图：

双向广度优先搜索（DBFS）

双向广度搜索是同时从初始节点和目标节点开始搜索，如果它们的路径发生了交汇点就说明找到了路径。这种方式比广度搜索所用时间减少一半。

三、测试案例

Case1 ：src：2 7 3 6 4 5 8 0 1 dest：2 7 3 0 4 5 6 8 1

Case2 ：src：0 5 3 2 7 6 1 8 4 dest：1 2 3 8 5 6 7 0 4

Case3 ：src：8 3 6 7 5 2 1 0 4 dest：5 1 3 8 7 6 2 0 4

四、结果检验

4.1 步数比较

4.2 使用时间

从上面两个表中可以看出，A*算法在搜索步数和所用时间上明显优于其他算法，这也说明启发式搜索比深度搜索和广度搜索两种方法效率更高。

五、十五数码扩展

5.1 问题说明：

数码问题同八数码问题，是人工智能中一个很典型的智力问题。十五数码问题是在 4*4 方格盘上，放有 15 个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格。给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。

5.2 问题分析：

将八数码中的 A*算法扩展到十五数码问题。八数码和十五数码两个问题的

区别主要在于判断是否有解，其次则在于估价函数的选取。

对于 N*N 数码问题，在使用逆序数判断两个状态是否可达时，有如下结论：当 N 为奇数时，两个 N 数码的逆序数奇偶性相同时，可以互达，否则不行；当 N 为偶数时，两个 N 数码的逆序数奇偶性相同且它们的 0 所在行的差值也是偶数，或两个 N 数码的逆序数奇偶性不同且它们的 0 所在行差值为奇数，才能互达。

证明如下：

当 0 左右移动时

这个 N 数码的逆序数是不变的；

当 0 上下移动时，

当 N 为奇数时，上下移动时，中间有 N-1 个数，N-1 为偶数，那么整个数码的逆序数只会有两种可能：加减一个偶数。举例说明：当 N 为 3 时， N-1 为 2，当 0 上下移动时，中间的两个数的逆序数有三种可能，同时加 1 或同时减 1 ，或一个加 1，一个减 1，这三种情况都使得总体的逆序数增加或减少偶数个，所以不管上下移几次，总体的逆序数的奇偶性是不变得；

当 N 为偶数时，上下移动时，中间有 N-1 个数，N-1 为奇数，上下移动一次整个 N 数码的逆序数只会有两种情况：加上或减去一个奇数。举例说明：当 N 为 4 时，N-1 为 3，当 0 上下移动时，中间的 3 个数的逆序数有四种情况，0 个增加 1、3 个减少 1，1 个增加 1、2 个减少 1，2 个增加 1，1 个减少 1，3 个增加 1、0 个减少 1，这四种情况全部都是使全部的逆序数增加或减去一个奇数。

而估价函数 f=g+h 中，h 可以有多种选取方式。

• h(n) = 状态 n 与目标状态不同的元素个数

  效果极差，十五数码问题的状态空间树要远复杂于八数码问题，且十五数码问题中空白块的移动更为复杂，此评估函数不适用。

• h(n) = 状态 n 与目标状态各个位置数字偏差的绝对值

  因为下部数字较大，移动后差值较大造成评估值较大，因此搜索集中在了数值较小的部分，效果很差。

• h(n) = 状态 n 与目标状态各个元素的曼哈顿距离

  效果较理想。

5.3 算法设计：

为了便于扩展，八数码并未使用一元数组存储，因此不必考虑康托展开的区别，仅需对是否有解函数 is_access()按上面的结论进行修改，估价函数本身使用的就是曼哈顿，因此不必改动其他部分。由于其他方法计算量过大，这里只做A*算法的拓展

判断是否有解条件在原来的基础上增加了计算行号的函数 is_minus(),若两行号差为偶数，返回 true，否则返回 false。

Main 函数中无解的判断条件

测试案例：

Case1: src: 2 5 7 13 3 0 8 12 15 1 4 10 9 11 14 6 dest: 2 7 0 13 3 5 8 12 15 1 4 10 9 11 14 6 Case2: src: 8 3 5 0 4 12 9 10 1 7 15 14 11 6 13 2 dest: 8 3 0 5 9 12 7 10 4 15 1 14 11 6 13 2 Case3: src: 8 3 5 0 4 12 9 10 1 7 15 14 11 6 13 2 dest: 8 3 5 4 9 12 7 1 10 0 11 6 14 15 13 2 

结果检验：

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。