基于Python解决八数码和八皇后问题【100012662】

# 摘要 本文主要分为两个部分，分别采用实验对比对不同的方法进行分析。第一，以八数码问题和八皇后问题为例，对比爬山法，随机重启爬山法，模拟退火算法，遗传算法的搜索性能。第二，以八数码问题为例，分别采用曼哈顿距离和错位棋子数为启发式函数，设计实验，分析启发式搜索方法。 **关键词：**局部搜索方法，启发式搜索 ## **局部搜索方法对比与分析** 局部搜索方法是对一个或多个状态进行评价和修改，而不是系统地从初始状态开始的路径，这些算法适用于关注那些关注解状态而不是路径代价的问题**[1]**。本节我们以八数码问题和八皇后问题为例，分别采用爬山法、随机重启爬山法、模拟退火算法和遗传算法进行实验设计，从而对比各算法的搜索性能。 ### 实验设计方法 #### 八皇后问题描述 八皇后问题，一个古老而著名的问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法[2]，描述如图 1-1 所示。  ​ 图 1-1 八皇后问题 #### 八数码问题描述 八数码问题是指将分别标有数字 1，2，3，4，5，6，7，8 的八块正方形数码牌任意地放在一块 3×3 的数码盘上[3]。放牌时要求不能重叠。于是多出来的一个空格。按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右四个方向可移动，在四个角落上有两个方向可移动，在其他位置上有三个方向可移动，描述如图 1-2 所示。  ​ 图 1-2 八数码问题执行过程 #### 爬山法求解八皇后和八数码设计 爬山法是指从当前的节点开始，和周围的邻居节点的值进行比较。 如果当前节点是最大的，那么返回当前节点，作为最大值，即山峰最高点；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的[4]。如此循环直到达到最高点。我们采用爬山法分别对八皇后和八数码进行算法设计，其中在爬山法求解八数码的问题中，我们采用曼哈顿距离作为启发式函数进行计算。设计流程图见图 1-3 和图 1-4 所示。  ​ 图 1-3 爬山法解八皇后流程图  ​ 图 1-4 爬山法解八数码流程图 #### 随机重启爬山法求解八皇后和八数码设计 随机重启爬山法的思想是通过随机生成初始状态来导引爬山法搜索，直到找到目标状态[5]。对于八皇后问题来说是合情合理的，因为八皇后问题目标就是找到最终状态，所有初始状态随机改变是可以允许的。但是对于八数码问题不合理，因为八数码问题的目标就是给定初始状态，从而找到到达最终状态的路线，初始状态是不能随意改变的，如果使用了随机重启算法，则违反了规则。因此，此处不采用随机重启法对八数码问题进行设计和求解。随机重启爬山法算法设计流程图见图 1-5 所示。  ​ 图 1-5 随机重启爬山法求解八皇后流程图 #### 模拟退火算法求解八皇后和八数码设计 模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素[6]。在迭代更新可行解时，以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。 由 Kirkpatrick 等人在 1983 年提出。我们采用模拟退火算法分别对八皇后和八数码进行算法设计，设计流程图见图 1-6 和图 1-7 所示。  ​ 图 1-6 模拟退火解八皇后流程图  ​ 图 1-7 模拟退火解八数码流程图 #### 遗传算法求解八皇后和八数码设计 遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按指标从解群中选取较优的个体，保留一组候选解，并按指标从解群中选取较优的个体，利用遗传算子对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足收敛指标[7]。我们采用遗传算法分别对八皇后和八数码进行算法设计，设计流程图见图 1-8 和图 1-9 所示。  ​ 图 1-8 遗传算法解八皇后流程图  ​ 图 1-9 遗传算法解八数码流程图 #### 实验设计依据及目的 为了对比爬山法、随机重启爬山法、模拟退火算法和遗传算法的搜索性能，我们分别以八皇后和八数码为例对各算法进行了实验算法设计，所有算法的详细流程图 1-3 至图 1-9 所示。在八皇后问题中，采用相同个数的测试数据，分别计算每种算法的求解的成功率、失败率、成功求解的平均步数、失败的平均步数以及每种算法在进行所有测试数据所花费的时间，然后进行对比试验，分析各算法的搜索性能。同理，在八数码问题求解中，由于随机重启爬山法，当其搜索不到目标状态时，则会重新初始化新的初始状态，而八数码的问题是给定初始状态求解到达目标状态的过程，所以随机重启爬山法不适合应用于求解八数码的问题，因此，在求解八数码的问题中，我们没有对随机重启爬山法进行实验。分别采用爬山法、模拟退火算法和遗传算法进行对比试验。所设计的对比参数同八皇后问题中的对比参数。统计测试结果，进一步分析各算法的搜索性能。 我们之所以采用求解成功率、失败率、成功求解平均路径长度、失败的平均步数以及求解所需的时间作为各算法的对比参数。因为通过这些参数我们可以分析出各算法的最优性、收敛性和时间复杂度等，进而达到分析各算法综合的搜索性能的实验目的。 ### 实验数据及实验结果 为了保证实验结果不受外界因素影响，我们使用配置相同的一台电脑，所有算法均采用同一种语言 python，版本为 python3.6 下，序运行环境为 windows 10，所用编译器为 PyCharm 进行实验。在八皇后问题中，我