让计算机教授找回被劫车辆的贪心算法，究竟多实用？

By 超神经

去年的圣诞节假期里，在美国圣母大学计算机系任职终身副教授，博士生导师，兼任电子系终身副教授史弋宇，经历了一场好莱坞式的寻车事件。

史教授在车辆被劫走的 24 小时内，通过车辆本身提供的模糊定位功能，用 greedy approach 贪心算法，快速准确定位了车辆，并找回了自己的爱车。

案件回顾

South Bend

Chicago

出发

午餐休息

Day1 12：00 AM

歹徒劫车

史教授停靠在加油站，预备给轮胎增压。在史教授检查车况之际，两位歹徒乘机劫车，慌乱中，史教授偷偷将手机放在座椅背后的口袋。

Day1 17：00 PM

开始追踪

报警无果后，史教授选择自己尽快找到汽车的位置。回到学校开始追踪，但是手机定位已经失效。

Day2 5：00 AM

模糊定位

史教授通过汽车自带的Mazda Mobile Start (MMS)，找到了汽车的模糊位置，与自己相距八十多公里，系统误差 6-7 米间。

Day2 7：00AM

相距 60 米！

史教授通过贪心算法的快速推论：当发现相对距离不再缩小时，就及时停止，转而往垂直方向继续搜索。

史教授通过这样的方式，曾使得距离到达仅仅 60 米，最终准确定位在一个车库内。

Day2 9：00 AM

警察束手无策

等待警察到达时，史教授和小王发现劫匪可能发现了异常，将车开走。史教授将手机交给警察，继续追踪车辆，警察并未能按照史教授的算法提示进行搜索。

Day2 10：00 AM

追回爱车！

史教授重获手机之后，继续使用自己的寻车算法，终于在一个停车场找到了失窃的汽车，警察顺利将汽车交还到史教授手中。

史教授的追车必杀技：贪心算法

这次紧张的劫车事件能在短短 24 校内被侦破，全靠史教授的执行力和准确的算法推演。

连警察们都被史教授能够如此迅速解决此事而惊叹：

「They shouldn’t have messed up with computer science professors ! 他们是不是傻，怎么能打劫计算机教授？」

史教授解释关于定位车辆的关键技术，其实就是计算机算法中最直接的 greedy approach。

贪心算法(Greedy Algorithm)，又称贪婪算法，是数学与计算机领域最为著名和经典的算法之一。

它在对问题求解时，不管之前或之后发生了什么，只与当前状态有关，只对当前的子问题得出最优解。但是，只要能根据每次所求得的局部最优解，就能够推导出全局最优解或最优目标。

而史教授将贪心算法应用在找车上的技巧：

当行驶时，发现自己与车的相对距离不再缩小时，就及时停止行进，

转而往垂直方向继续搜索。

这就是一个螺旋搜索结构，确保自己始终在沿着距离下降的方向单调搜索可以收敛的。

所以最终史教授在只有两人一车的情况下，通过误差 3 公里的导航软件的指引下，迅速定位失窃车辆，贪心算法就是最准确的工具。

贪心算法的其他经典应用

作为经典算法之一，贪心算法的应用并不算很广泛。

因为贪心算法只能通过解局部最优解的策略，来达到全局最优。因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。

比如背包问题、路径问题，下面举例经典算法来解释贪心之美：

Dijkstra 单源最短路径算法

Dijkstra 算法是一种用于计算带权有向图中单源最短路径（SSSP：Single-Source Shortest Path）的算法，由计算机科学家 Edsger Dijkstra 于 1956 年构思并于 1959 年发表。

其解决的问题是：

给定图 G 和源顶点 v，找到从 v 至图中所有顶点的最短路径。

Dijkstra 算法采用贪心算法（Greedy Algorithm）范式进行设计：

按路径长度递增的顺序，逐个产生各顶点的最短路径。算法过程中需要维护一个顶点集 SS ,此顶点集保存已经找到最短路径的顶点。还需要维护一个距离数组 dist, dist[i] 表示第i个顶点与源结点 s 的距离长度。

S 初始化时只包括源节点s;
dist[]dist[] 初始化：dist[i]= arc[s][i], arc 为图的邻接矩阵。
V−SV−S 表示未被找到最短的路径的顶点集合；

把 distdist 按递增的顺序，选择一个最短路径，从 V−SV−S 把对应顶点加入到 S 中，每次 S 中加入一个新顶点 u , 需要对 distdist 更新，即 s 能否通过顶点 u 达到其他顶点更近。
即若 dist[u] + arc[u][v] < dist[v] ,则更新 dist[v]=dist[u]+arc[u][v]