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
不过不用担心，在生产实践中这种次优解已经能够解决实际问题，在求解最优解的成本远远高于求解次优解的情况下就可以大胆使用它。这种“次优解即最优解”的思维方式几乎贯穿于所有工业应用领域，后面我们还会介绍很多这样的例子。
1700507600
1700507601
1700507602
1700507603
1700507604
数据科学家养成手册 [:1700503584]
1700507605
数据科学家养成手册 11.7 迭代法——步步逼近
1700507606
1700507607
所谓“迭代法”同样不是一个算法，而是一类算法的解题思路。这种方法用来处理那些无法通过解析解的表达得到精确解的情况。
1700507608
1700507609
1700507610
我们都知道，一元二次方程的求根公式是
1700507611
1700507612
1700507613
1700507614
1700507615
用“配方法”很快就能获解。
1700507616
1700507617
对于一元四次及以下的方程，都可以通过求根公式来得到解析解，带入系数的具体值，即可得到确定的数值解。
1700507618
1700507619
但是，高次方程及有复杂项的方程就没有这种求根公式(5)，而且很多方程的解都无法直接求出。这使我们不得不去寻求其他方法，迭代法就是其中之一。
1700507620
1700507621
数据科学家养成手册 [:1700503585]
1700507622
11.7.1 牛顿法
1700507623
1700507624
迭代法的核心思路就是用步步逼近的方式来接近理论上的精确值，只要发现当前的试探值已经收敛到一个满足场景要求的误差精度，就可以判断迭代结束，并将这个试探值作为求解的目标值。这种方法可以使很多无法直接求解的问题得到一个足够精确的近似解。这同样也是一种以有限成本的“次优”取代无限成本的“最优”的哲学思想。
1700507625
1700507626
迭代法中有一个经典的方法叫“牛顿迭代法”（Newton’s Method，或称“牛顿法”），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。
1700507627
1700507628
例如，有一个一元方程
1700507629
1700507630
f(x)=0