1700507550
数据科学家养成手册 [:1700503582]
1700507551
数据科学家养成手册 11.5 回溯法——能省则省
1700507552
1700507553
回溯法（探索与回溯法）是一种选优搜索法，又称“试探法”，有些参考资料上也称其为“剪枝法”。回溯法的核心思路是，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先的选择不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的方法称为“回溯法”，而满足回溯条件的状态点称为“回溯点”。
1700507554
1700507555
这种思路的“上一步”实际上是穷举解空间的思路。在对空间进行穷举的过程中，发现按照当前的穷举路径前进，剩下的解都不可能是所求解，在这种情况下，就放弃当前穷举路径下的所有待选解并回退。所以，在绝大多数情况下都只尝试了穷举空间中的一小部分解，而不是全部解。
1700507556
1700507557
例如，写一个算法来模拟走出迷宫的过程。这个算法可以用递归来写，也可以用非递归的遍历方法来写。如图11-13所示是一个20×20的迷宫，在迷宫的每个方格中都有4个方向可以“走”，除了过来的方向（走过的格子），还有3个方向可以“走”。那么，在遍历的过程中，理论上的计算成本为
1700507558
1700507559
1700507560
1700507561
1700507562
图11-13 迷宫问题
1700507563
1700507564
1700507565
1700507566
1700507567
大约是3.5×10190。在这样的情况下，使用穷举法显然会消耗一段我们无法忍受的时长，而且使用分治法的思路也不明确，无法简化成“局部获解而全局获解”的问题。
1700507568
1700507569
但是，我们可以很容易地发现，迷宫中很多方格的4个方向其实并非全部有效：有的是“墙”，过不去；有的是走到某一步会发现，从这一步开始的所有解树叶节点都不用尝试了，这种情况下，会把“树”上的所有子枝全部剪掉，以节省大量的空间和时间成本，所以叫“剪枝法”也是非常形象的（如图11-14所示）。
1700507570
1700507571
1700507572
1700507573
1700507574
图11-14 三叉树深度优先遍历
1700507575
1700507576
剪枝法不仅可以应用在类似寻找迷宫出口的问题上，在地图导航等领域的应用及变种应用也很多，例如象棋和围棋的对弈软件就是使用类似的方式实现的。不过，近年来随着深度学习领域的理论发展和计算机计算能力的攀升，围棋对弈软件更多使用深度神经网络辅以强化学习的手段来开发。关于深度神经网络解决问题的核心思路，会在11.9节专门讨论。
1700507577
1700507578
1700507579
1700507580
1700507581
数据科学家养成手册 [:1700503583]
1700507582
数据科学家养成手册 11.6 贪心法——局部最优
1700507583
1700507584
“贪心法”这个名字听起来好像不怎么高尚，不过它却是一种常用且实用的思维方式。无独有偶，这种方式也是人类本身所拥有的。
1700507585
1700507586
不管是国家还是个人，在制定自己的发展规划时要做到“从一而终”通常非常困难。就拿一个人来说，有句话叫“计划赶不上变化”——在10岁的时候规划好的理想人生，可能刚过两三年就会因为很多内在和外在的因素发生了变化而不得不重新规划。可以毫不夸张地说，规划的时间跨度越长就越不实用，因为人生中无处不在的变数会潜移默化地对一个人的规划产生影响，这一系列的变化慢慢积累，到最后可能连规划者本人都看不出当前的情况和原来的规划还有什么联系。
1700507587
1700507588
对“帮助计算机解题”来做规划，也会有解决类似问题的困惑，要不怎么说“数据科学贯穿在很多领域之中”呢？而且，对计算机来说，时间和空间成本同样是比较有限的。在一个全局的复杂问题中，如果无法通过穷举、分治、回溯这些问题快速找到一个可行的解决方案，该怎么办？——用贪心法。
1700507589
1700507590
贪心法的思路也很明确，就是在每一步向前试探的时候都找到当前的“最优解”，其他的解（分支）一概不看——在有限的视野寻找最优解作为行动纲领。经典算法中的迪杰斯特拉算法（Dijkstra Algorithm）就是其中之一。
1700507591
1700507592
迪杰斯特拉算法用于求解有向图中的最短路径问题。在生产实践中，其应用场景通常是那些需要快速应答且穷举和回溯成本极高的场合。在学术方面，所有人都承认以迪杰斯特拉算法为代表的贪心法求出的通常是次优解，即每次找到的与当前访问位置连接成本最低的点，都只是在这一无法回溯的情况下对找到“最优解”的单方向试探，当然不排除一些被忽略的访问路径是最优解的情况（如图11-15所示）。每个有向边所标注的权重数字相当于在这个边上前进所发生的成本，当然是从节点A走到节点H时的成本越低越好，而用贪心法在这里求出的解显然不是全局的最优解。
1700507593
1700507594
1700507595
1700507596
1700507597
图11-15 贪心法求解路径问题
1700507598
1700507599
不过不用担心，在生产实践中这种次优解已经能够解决实际问题，在求解最优解的成本远远高于求解次优解的情况下就可以大胆使用它。这种“次优解即最优解”的思维方式几乎贯穿于所有工业应用领域，后面我们还会介绍很多这样的例子。