爬山法、模拟退火算法、遗传算法、启发式搜索方法解决八皇后问题

摘要

这篇文章包含两个主要部分，通过实验对比来评估不同方法的表现。首先，以八数码和八皇后问题为研究对象，比较爬山法，随机重启爬山法，模拟退火算法，以及遗传算法在搜索效率上的优劣。其次，针对八数码问题，选用曼哈顿距离和错位棋子数作为启发式函数，开展实验研究，探讨启发式搜索方法的作用效果。

关键词：局部搜索方法，启发式搜索

1. 局部搜索方法对比与分析

局部搜索策略针对单个或少数状态进行评估与调整，并非从初始点出发遍历完整路径，这类方法适合那些更注重结果状态而非过程成本的场景。本章选取八数码和八皇后两种情形，通过应用攀爬技巧、随机重置攀爬技巧、模拟冷却机制及基因进化策略开展对比实验，以分析不同算法的搜索效率差异。

1.1 实验设计方法

1.1.1 八皇后问题描述

八皇后问题是一个历史悠久且广为人知的问题，它典型地展示了回溯算法的应用。这个问题的提出者是国际西洋棋棋手马克斯·贝瑟尔，时间是 1848 年。问题的具体内容是在 8×8 的国际象棋棋盘上放置八个皇后，要求这些皇后彼此之间无法互相攻击，也就是说，任意两个皇后不能位于同一行、同一列或者同一斜线位置。问题的核心在于计算有多少种不同的摆放方法，其示意图参见图1-1。

图1-1 八皇后问题

1.1.2 八数码问题描述

八数码问题涉及八块分别带有数字1到8的正方形牌，这些牌可以任意放置在3×3的盘子上。放置时，牌块之间不能相互覆盖。因此，盘面上会剩下一个空白位置。游戏规则规定，每次只能将空白位置与其相邻的牌块进行位置交换。通过不断移动空白位置，并使其与相邻牌块互换，最终的目标是达到预设的完成状态。方块在中间时能向四方移动，在角落处能向两方移动，在其余位置能向三方移动，具体情况如图1-2所示。

图1-2 八数码问题执行过程

1.1.3 爬山法求解八皇后和八数码设计

逐点检测，将当前点的数值与其邻近点的数值进行对照。倘若当前点的数值为最大，则直接输出该点，将其视为最高峰；倘若不是，则选取数值最大的邻近点，以此点替代当前点，借此方式向山峰的顶点逐步移动。不断重复这一过程，直至抵达峰顶。我们运用爬坡技巧分别针对八皇后和八数码开展算法构思，在爬坡技巧解决八数码的情境下，选用曼哈顿距离充当启发式函数来执行运算，构思的步骤图示于图1-3和图1-4之中

图1-3 爬山法解八皇后流程图

图1-4 爬山法解八数码流程图

1.1.4 随机重启爬山法求解八皇后和八数码设计

随机重启爬山法的核心在于，它借助随机产生的起始条件，来推动爬山法进行探索，直至达成目标条件。针对八皇后问题而言，这种方法十分适用，毕竟该问题的宗旨就是寻获一个圆满的解，而各个起始条件的随机性变动，并不会对结果产生影响。八数码问题不适用这种方法，该问题的核心在于从指定起点寻找到达终点的路径，起点的状态必须固定，不能随意调整，一旦采用随机重置的策略，就会违背游戏规则，所以不采用这种重启方法来处理八数码问题，具体的设计步骤请参考图1-5。

图1-5 随机重启爬山法求解八皇后流程图

1.1.5模拟退火算法求解八皇后和八数码设计

模拟退火方法本质上属于贪心策略的一种变体，其运算步骤中融入了随机性成分。在反复调整可用方案时，会依据特定几率采纳一个较当前方案质量更低的选项，这样或许能挣脱局部最优状态的束缚，进而寻得全局最优结果。此方法由Kirkpatrick等人于1983年研发而成。我们运用模拟退火方法，针对八皇后问题与八数码问题，完成了算法的构思，构思步骤的示意图参见图1-6和图1-7。

图1-6 模拟退火解八皇后流程图

图1-7 模拟退火解八数码流程图

1.1.6 遗传算法求解八皇后和八数码设计

遗传算法属于一类算法，它通过模拟自然界中的生物选择和遗传过程来执行随机搜索任务。它通过模仿生物繁衍、基因重组和变异等机制运作，每次循环都会筛选出部分优质方案，依据特定标准从现有方案中挑选表现更佳的个体，继续保留这些优选方案，并借助遗传算法对这些个体进行配对，从而生成新一代的备选方案集合，不断重复这一步骤，直至达到预设的稳定条件。我们运用遗传算法针对八皇后和八数码开展算法规划，规划步骤见图1-8以及图1-9。

图1-8 遗传算法解八皇后流程图

图1-9 遗传算法解八数码流程图

1.1.7 实验设计依据及目的

为分析登山法、随机重试登山法、模拟降温法和基因法的效果，我们挑选了八皇后和八数码作为测试对象，针对每种方法都进行了实验方案制定，具体步骤参见图1-3至图1-9的流程图。在八皇后问题上，针对等量的测试样本，分别统计各类方法的成功次数、失败次数、成功求解的平均步数、失败的平均步数，以及各类方法处理所有测试样本所需的总时长，随后开展对比研究，评估不同方法的搜索效率。类似地，在处理八数码难题时，因为随机重启的爬山策略，一旦搜索不到期望结果kaiyun全站网页版登录，就需要重新设定起始条件，而八数码难题的核心是给定一个初始布局，找到达成目标布局的路径，所以这种随机重启的搜索方式并不适合用来解决八数码难题，因此，在研究八数码难题时，我们没有进行随机重启爬山策略的测试。通过登山策略、模拟冷却过程以及遗传学原理开展对照实验，参照八皇后课题中的对照标准设定实验参数，对实验数据加以汇总，深入剖析各种方法在搜寻方面的优劣表现。

我们选择成功率、失败率、成功求解平均路径长度、失败的平均步数以及求解所需的时间来对比各算法，目的是通过这些参数分析各算法的优劣、收敛速度和时间效率，从而全面评估各算法的搜索能力。

1.2 实验数据及实验结果

为确保实验数据不受环境干扰，我们选用了一台配置完全一致的计算机，所有算法都统一使用python语言开发，具体版本是python3.6，运行环境设定为windows 10开yun体育app官网网页登录入口，并借助PyCharm软件完成所有测试工作。在八皇后难题里，我们随机选了1000组数据做实验，每组数据都用爬山策略、随机重置的爬山策略、模拟退火方法和遗传策略来测试，最后统计了每组数据用每种策略成功解决问题的数量、失败的数量、成功时平均走的步数、失败时平均用的步数，以及解决问题总共花了多少时间。同样地，针对八数码情形，随机生成一千个起始配置，所有配置的目标格局保持一致，随后依次运用攀爬策略、模拟冷却机制和物种进化方法开展评估。各方法在八皇后场景下的检验数据参见表一。我们针对随机重启算法，尝试了多样的随机重启上限次数来开展测试，其它条件均保持一致；在模拟退火算法方面，我们变换了不同的退火速率来执行实验；对于遗传算法，我们调整了不同的繁衍代数进行测试，以此探究参数对实验成效的作用；同样的，各个算法在处理八数码问题时的测试数据已汇总于表2。详细的实验测试代码参见附件1。

表1 各算法在求解八皇后问题实验结果

表2 各算法在求解八数码问题实验结果

1.3 实验结论

根据1.2节实验验证结果，表1清晰揭示，登山策略应用于八皇后及八数码课题时，解题成效均欠佳，在八皇后课题中，其成功解题比例仅达14.2%，在八数码课题里，成功解题比例更是微乎其微，仅占0.002%。不过，该策略具备解题耗时短的优势。通过分析，成功解题的平均步骤数稳定在4.01，这表明登山策略通常能以更短的路径抵达全局最优解。表1显示，随机重启爬山法比单纯爬山法效果显著增强，在八皇后问题中，若设定随机重启次数上限为5，求解成功率可达到60.1%，而将上限参数提高到50时，成功率为100%，这表明随机重启次数上限越高，成功率也随之提升。重启次数少的时候，成功率、解的长度、解的用时都比较低，重启次数多的时候，成功率会显著提高，当重启次数足够大时，随机重启爬山法几乎总能找到解，因为只要给随机重启设定足够大的次数限制，最终总能生成目标状态作为初始状态。解八皇后难题时，我们观察到，当随机重试次数为五十时，就能确保百分之百成功找到解法。不过，这种方法存在一个明显缺陷，就是随着重试次数的增多，所得到的解法路径长度和计算资源消耗也随之急剧上升。鉴于随机重试爬山策略对于解决八数码问题并不适用，所以在此不再展开讨论。运用模拟退火算法处理八皇后难题时，若起始温度定为5，降温比例设为0.99，结果显示并非每次都能得出答案，得解几率达到77.8%。与攀岩策略相比，明显可见模拟退火法所需的平均尝试次数大幅增长。这表明攀岩策略在时间利用上效率极高，其既是长处也是短处。此外，我们采用多种退火速度开展对照实验，发现，在不同退火速度条件下kaiyun全站登录网页入口，求解任务的达成率、解的规模、解题所需时间均呈现相应变动，退火过程越迟缓，模拟退火方法解决八皇后难题的成效就越显著，然而伴随成效提升，达成任务平均所需的步骤数也显著增大，模拟退火技术在处理八数码与八皇后两类问题时展现出相似特性。随着初始温度升高，数值随之增长，并且解的长度和所需时间显著增加。表2表明，模拟退火算法获得成功的概率远远超过爬山法，成功率达到52.1%，然而它所花费的时间却大幅减少。通过上述对比可以发现，模拟退火算法的效率与其参数密切相关，只要参数调整合理，这种算法的搜索能力将比穷举法强得多。八皇后问题的遗传算法求解效率因参数不同而有所差异，所需时间也各不相同，表明求解速度与初始种群密切相关。表1显示，针对同一问题，若初始种群不同，求解所需代数可相差巨大。故可通过启发式算法获得更优的初始种群，从而提升收敛速率。在八皇后和八数码问题上，各种算法的表现不尽相同，可以明显看出，就搜索代价而言，爬山法所用的移动次数相对较少，能够在较短的步骤内迅速找到答案，效率十分突出，然而其成功解决问题的比例却非常低，令人失望。而随机重启爬山法，当预设的重启次数增加时，其成功解决问题的概率也会跟着提高，不过这样会导致时间上的消耗不断加大。这两种算法的成效显著，然而其移动频次极高，探寻过程耗时良久，所需付出相应增加。另外，它们对参数的敏感度较强。

2、启发式搜索方法对比与分析

试探性探寻是在整体状况布局里进行的，针对每一个探寻点进行判定，选定最优点，然后从这里继续探寻直至抵达终点。这种方式能够舍弃许多没有必要的探寻路线，从而提升成效。本节针对八数码问题，通过曼哈顿距离和错位棋子数这两种启发式函数开展实验研究，具体内容可参考1.1.2节所述，实验旨在探究不同启发式函数对算法性能的影响，并解析造成性能差异的关键因素，总结算法在各个方面的表现特点。

2.1 实验设计方法

2.1.1 错位棋子数作为启发式函数解决八数码设计

本节我们运用移位棋子技巧作为启发式函数开展实验，接着，我们设定评估函数如下：

f(n) =g(n)+w(n) (1)

f(n)表示从起始位置经过节点n到最终位置的总成本预估，这个函数被称为成本估算；g(n)代表在状态集合中从起始位置移动到节点n的实际花费，这个指标被称为节点深度；w(n)是节点n到最终位置的成本预估，这个函数被称为启发式评估，在此处w(n)具体指节点n在数据库里位置不正确的棋子数量。

我们借助启发式搜索中的A*算法完成了实验方案制定，所以必须先确认方案符合A*算法的要求，要检查该方案是否满足A*算法的两个必要条件，其一，我们设定的预估函数中的w(n)值应当大于w'(n)，w'(n)代表从当前节点通往目标点的实际最优代价。其次，新增节点的评估值至少等于其父节点的评估值，这一点从设计的估价方法中可以明显看出，所以接下来要验证的是另一项条件是否成立。因为定义的估价方法里g(n)代表节点的层级，所以每次扩展都会使层级比父节点多一。对于w(n)来说，每次移动数字，最多能让一个数字回到正确位置，或者说错位的数字减少一个。w(n)的值最多降低一个单位，g(n)用来标示层级，每次计算时其数值都会增长一个单位。因此，f(n)等于g(n)加上w'(n)这个表达式不会出现下降，由此可以确认条件二成立，表明算法完全符合A*的运行要求。按照A*算法和错位数目技巧来处理八数码难题的步骤，体现在流程图2-1中

图2-1 基于错位棋子数法解决八数码问题设计流程图

2.1.2 曼哈顿距离作为启发式函数解决八数码设计

本节我们选用曼哈顿距离方法作为启发式函数开展实验，接着，我们确定估价函数的形式如下：

f(n)=g(n)+p(n) (2)

那个f(n)表示从起始位置经过节点n到最终位置的总成本预估，叫做预估函数；g(n)说明在状态集合中从起始位置移动到节点n的真实花费，称为节点深度；p(n)描述从节点n到最终位置的预估成本，称作启发式函数，这里p(n)是指把所有数字调整到目标位置所需要的最少操作次数总和。

我们同样要确认它是否符合A*算法的两大要求。这种手段能够统计出将所有数字调整到正确位置所需的最少步数总和。当作启发式函数，第一个要求很显然是成立的。至于第二个，每次交换最多只能使数字向目标位置靠近一步，而g(n)的值每次递增一，所以g(n)+p(n)的合计数不会低于初始值，也就是说第二个要求也能成立。由此可见A*算法是适用的。根据流程图2-2，采用A*算法结合曼哈顿距离来处理八数码难题的步骤如下。

2.1.3 实验设计依据及目的

为了分析两种启发式函数的差异，一种是基于错位棋子数量，另一种是利用曼哈顿距离，需要考察它们对算法表现的不同作用。我们首先选用相同的编程语言和硬件设备开展研究，在确认这些外部条件不会干扰实验的前提下，接着分别运用两种不同的启发式函数，基于同一初始状态和同一目标状态，检测它们在处理八数码问题时的耗时以及达到目标所需的移动次数，通过这些数据对比两种启发式函数对算法效率的影响，并深入探究导致性能差异的具体因素。

2.2 实验数据及实验结果

图2-2 基于曼哈顿距离解决八数码问题设计流程图

我们随机挑选了10套不同的起始条件数据，分别用错位棋子数量当作启发式函数，又用曼哈顿距离当作启发式函数开展对比测试，这10套起始条件数据具体是：

初始状态1： {8,2,5,1,0,3,4,7,6}

初始状态2： {3,1,4,0,6,7,5,2,8}

初始状态3： {1,5,7,4,8,2,3,6,0}

初始状态4： {5,3,1,7,4,0,8,2,6}

初始状态5： {5,4,7,8,6,0,2,3,1}

初始状态6： {4,0,8,2,5,1,7,3,6}

初始状态7： {0,2,7,3,8,6,1,4,5}

初始状态8： {5,4,2,7,3,1,6,8,0}

初始状态9： {2,4,8,6,3,1,5,0,7}

初始状态10：{8,2,6,7,3,0,4,1,5}

每组数据的目标集合都包含数字1到8，以及一个零值元素。为了排除实验条件的干扰，我们使用统一的编程语言，在配置为Windows 10且安装有JDK 1.8.0的计算机上开展测试，具体的编码实现请参考附件2。实验结果参见表二一，其中差异值代表错位棋子数量，用作评估依据，哈顿距离值代表距离度量，同样作为评估依据。

表2-1 采用错位棋子数和曼哈顿距离作为启发式函数实验结果

2.3 实验结论

启发式搜索存在多种实现方式，例如局部最优选择策略，以及最优优先探索路径等，其中涵盖了 A*算法，这些方法都依赖启发式函数，只是在确定最优搜索节点时的具体实施步骤有所区别。本章节通过两种不同的启发式函数开展设计实验，分别选用错位棋子数和曼哈顿距离作为评估标准，对比分析其效果差异。实验结果显示，以错位棋子数作为参考指标时，算法运行时间明显长于采用曼哈顿距离的情况。这一现象表明，启发式函数的选取对整体算法效率具有显著作用，恰当的函数选择能够大幅优化算法表现。实验结果表明，采用启发式搜索策略时，必须设计合理的评估函数，而评估函数的选择对实验结果具有显著作用。例如在本实验中，针对我们设定的评估函数f(n)，第一种实现方式将错位棋子的数量作为启发式依据，通过比较各个状态与目标状态之间错位棋子的多少来进行评估。若其他条件保持一致，那么错位棋子数量最少的那个状态，很可能就是距离目标状态最近的状态。这种思路并未充分利用棋盘布局提供的全部细节，因为它忽略了棋子必须行进的必要步数。实验结果显示，该方法的运算时间相当可观，第二种方案则选用曼哈顿距离作为指导原则，将所有错位数字需要跨越的格子数量累加起来，为了精确计算，每个数字移动的每一步都计为一个计量单位，这种做法比前一种更高效。另外，实验数据表明，两种不同的启发式规则都存在缺陷，例如当探索的层次非常高时，第二种方案依然非常耗费时间。若启发式规则挑选不当，算法的效率就会显著降低。由此可见，仍有诸多改进空间，比如采用迭代加深的A*搜索等策略。

3. 总结

本文选取八数码和八皇后两大课题，将爬山策略，随机重启爬山策略，模拟退火策略以及遗传策略的搜索效能进行对照研究。针对八数码课题，选用曼哈顿距离和错位数目作为指导函数，开展实验，探讨启发式搜索途径。例如，爬山策略在解题时耗时较少，却常卡在非最优解中。随机重试爬山法，随着重试次数的增加，成功找到解的概率会提高，但所需付出的时间代价也在增长。启发式搜索，依据所使用的不同启发式函数，其表现也会有差异。