搜索算法案例分析

• A*算法案例场景-路径规划
• • 案例场景
  • 解决方案
  • 改进点
  • 思考
• 贪婪最优算法案例场景-罗马尼亚度假问题
• • 案例场景
  • 解决方案
  • 改进点
  • 思考
• 爬山法案例场景-八皇后问题
• • 案例场景
  • 解决方案
  • 改进点
  • 思考
• 模拟退火算法案例场景-TSP
• • 案例场景
  • 解决方案
  • 改进点
  • 思考
• 遗传算法案例场景-寻路问题
• • 案例场景
  • 解决方案
  • 改进点
  • 思考
• 粒子群搜索案例场景-多目标优化
• • 案例场景
  • 解决方案
  • 改进点
  • 思考
• Minimax案例场景-博弈问题
• • 案例场景
  • 解决方案
  • 改进点
  • 思考

A*算法案例场景-路径规划

案例场景

路径规划是指的是机器人的最优路径规划问题，即依据某个或某些优化准则（如工作代价最小、行走路径最短、行走时间最短等），在工作空间中找到一个从起始状态到目标状态能避开障碍物的最优路径。机器人的路径规划应用场景极丰富，最常见如游戏中NPC及控制角色的位置移动，百度地图等导航问题，小到家庭扫地机器人、无人机大到各公司正争相开拓的无人驾驶汽车等。

解决方案

典型的最短路径的算法是迪杰斯特拉算法，由荷兰计算机科学家迪杰斯特拉于1959年提出，用来求得从起始点到其他所有点最短路径。该算法采用了贪心的思想，每次都查找与该点距离最近的点，也因为这样，它不能用来解决存在负权边的图。解决的问题可描述为：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点vs到其余各点的最短路径。

A*算法通过函数来计算每个节点的优先级。

f(n) = g(n) + h(n)
g(n) = 到达n的费用
h(n) = 从n到目标的估算费用（已确定值，对路径启到校正作用）
f(n) = 通过n到达目标的总估算费用

改进点

在极端情况下，当启发函数h(n)始终为0，则将由g(n)决定节点的优先级，此时算法就退化成了Dijkstra算法。

如果h(n)始终小于等于节点n到终点的代价，则A*算法保证一定能够找到最短路径。但是当h(n)的值越小，算法将遍历越多的节点，也就导致算法越慢。

如果h(n)完全等于节点n到终点的代价，则A*算法将找到最佳路径，并且速度很快。可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。

如果h(n)的值比节点n到终点的代价要大，则A*算法不能保证找到最短路径，不过此时会很快。

在另外一个极端情况下，如果h(n)相较于g(n)大很多，则此时只有h(n)产生效果，这也就变成了最佳优先搜索。

对于网格形式的图，如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离。如果图形中允许朝八个方向移动，则可以使用对角距离。如果图形中允许朝任何方向移动，则可以使用欧几里得距离。

思考

信息：尽可能基于现有信息的搜索策略，也就是说搜索过程中尽量利用目前已知的诸如迭代步数，以及从初始状态和当前状态到目标状态估计所需的费用等信息。A*算法可以选择下一个被检查的节点时引入了已知的全局信息，对当前结点距离终点的距离作出估计。

其他典型应用场景：路径分析，机器人运动规划，语言分析，机器翻译，语音识别，车辆分配与路线安排

贪婪最优算法案例场景-罗马尼亚度假问题

案例场景

罗马尼亚度假问题，寻找从Arad到Bucharest的一条最短路径

解决方案

贪婪最优算法通过函数f(n)=h(n)来计算每个节点的优先级
在最短路径问题中，启发函数为此刻城市节点到终点城市Bucharest的直线距离，每一次搜索，下一个节点选择与此刻城市连接的所有节点中，与Bucharest的直线距离最短的城市节点。

改进点

贪婪最佳优先搜索不是最优的。经过Sibiu到Fagaras到Bucharest的路径比经过Rimnicu、Vilcea到Pitesti到Bucharest的路径要长32公里。

启发函数代价最小化这一目标会对错误的起点比较敏感。考虑从Iasi到Fagaras的问题，由启发式建议须先扩展Neamt，因为其离Fagaras最近，但是这是一条存在死循环路径。

贪婪最佳优先搜索也是不完备的。所谓不完备即它可能沿着一条无限的路径走下去而不回来做其他的选择尝试，因此无法找到最佳路径这一答案。

在最坏的情况下，贪婪最佳优先搜索的时间复杂度和空间复杂度都是O（b^n）

思考

信息：利用节点到目标节点之间所形成路径的最小代价值。

其他典型应用场景：零钱兑换

爬山法案例场景-八皇后问题

案例场景

八皇后问题：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

解决方案

是一种局部择优的贪心搜索算法，其本质上是梯度下降法。该算法每次从当前的节点开始，与周围的邻接点进行比较：若当前节点是最大的，那么返回当前节点，作为最大值；若当前节点是最小的，就用最高的邻接点替换当前节点，从而实现向山峰的高处攀爬的目的。

改进点

爬山法获取的最优解的可能是局部最优，如果要获得更好的解，多次使用爬山算法（需要从不同的初始解开始爬山），从多个局部最优解中找出最优解，而这个最优解也有可能是全局最优解。

思考

信息：随机选择一个登山的初始时间T，这个参数是随机选择的。只要当T大于一个边界值EPS时，就将当前点与其邻接点进行比较：如果res<newRes，转移答案，并记录新坐标点pos；如果res>newRes，不转移。
其他典型应用场景：求解目标函数

模拟退火算法案例场景-TSP

案例场景

模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温，粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，终形成处于低能状态的晶体。

解决方案

模拟退火算法从某一较高的温度出发，这个温度称为初始温度，伴随着温度参数的不断下降，算法中的解趋于稳定，但是，可能这样的稳定解是一个局部最优解，此时，模拟退火算法中会以一定的概率跳出这样的局部最优解，以寻找目标函数的全局最优解。如上图中所示，若此时寻找到了A点处的解，模拟退火算法会以一定的概率跳出这个解，如跳到了D点重新寻找，这样在一定程度上增加了寻找到全局最优解的可能性。

改进点

理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢，相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能终得不到全局优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。

要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续m次的转换过程没有使状态发生变化时结束该温度下的状态转换。终温度的确定可以提前定为一个较小的值，或连续几个温度下转换过程没有使状态发生变化算法就结束。选择初始温度和确定某个可行解的邻域的方法也要恰当。

思考

信息：模拟退火用到了Metropolis准则判断是否接受新解

其他典型应用场景：VLSI(超大规模集成电路)的最优设计，如全局布线、布板、布局和逻辑最小化等等。图像恢复工作。

遗传算法案例场景-寻路问题

案例场景

遗传算法起源于对生物系统所进行的计算机模拟研究，是一种随机全局搜索优化方法，它模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体，从而求得问题的优质解。

解决方案

遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。

染色体编码可以采用二进制编码以及十进制编码等方式。

初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

改进点

算法容易导致早熟，后期搜索迟钝。可以采取有条件的最佳保留机制；采用遗传-灾变算法；采用适应度比例机制和个体浓度选择机制的加权和；引入主群和属群的概念；适应度函数动态定标；多种群并行进化及自适应调整控制参数相结合的自适应并行遗传算法，对重要参数的选择采用自适应变化而非固定不变。

思考

信息：群体规模、交叉概率、变异概率、进化代数

其他典型应用场景：主要用于寻找目标函数最优解（最大，最小值）。相对退火法，遗传算法更有可能跳出局部最优解，得到全局最优解

粒子群搜索案例场景-多目标优化

案例场景

粒子群算法是通过模拟鸟群捕食行为设计的一种群智能算法。区域内有大大小小不同的食物源，鸟群的任务是找到最大的食物源（全局最优解），鸟群的任务是找到这个食物源。鸟群在整个搜寻的过程中，通过相互传递各自位置的信息，让其他的鸟知道食物源的位置最终，整个鸟群都能聚集在食物源周围，从而找到了最优解，问题收敛。

解决方案

基础粒子群算法步骤较为简单。粒子群优化算法是由一组粒子在搜索空间中运动，受其自身的最佳过去位置pbest和整个群或近邻的最佳过去位置gbest的影响。每次迭代粒子i的第d维速度，同时更新粒子i的第d维位置

改进点

若需要算法快速收敛，需要将加速度常数调大。但是这么做可能会导致算法出现“早熟”。若把惯性权重调大，可增加粒子探测新位置的“积极性”，避免过早陷入局部最优，但也会降低算法的收敛速度。对于有些改进算法，在速度更新公式最后一项会加入一个随机项，来平衡收敛速度与避免“早熟”。并且根据位置更新公式的特点，粒子群算法更适合求解连续优化问题。

思考

信息：给空间中的所有粒子分配位置和随机速度，并不断迭代直至满足要求。

其他典型应用场景：PSO训练神经网络

Minimax案例场景-博弈问题

案例场景

假设有一个游戏，只有两个玩家参与，两轮便定出胜负。则称两个玩家为MAX和MIN。每个玩家在各自的回合中，都有2个到1个行动可选。MAX先手。假设游戏只有两轮，所以游戏进行到第四层时，游戏的胜负就已经知道了，从而评估该层各个状态的效用值，来表示玩家MAX的胜负多少，对于这一层的结果，MIN和MAX双方都是知道的。

解决方案

一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法

改进点

在Minimax算法中，MIN和MAX过程将所有的可能性省搜索树，然后再从端点的估计值倒推计算，这样的效率非常低下。可以引入α-β算法提高运算效率，对一些非必要的估计值进行舍弃。当生成结点到达规定深度时，立即进行静态估计，一旦某一个非端点的节点可以确定倒推值的时候立即赋值，节省下其他分支拓展到节点的开销。

思考

信息：该算法需要满足零和博弈，若有两个玩家进行游戏，如果其中一方得到利益那么另一方就会失去利益，游戏利益的总和为0。

其他典型应用场景：棋类游戏