A前瞻资讯官网
前瞻网
a 当前位置: 前瞻网 » 资讯 » 产经

算法立功!清华毕业教授美国被抢车 警察无能为力自己用“贪心算法”找回

分享到:
 黄琨 • 2019-01-05 17:45:30 来源:前瞻网 E4805G7

算法

人类总是崇敬知识,但并非崇敬所有知识,不少人曾问出过那个振聋发聩的问题:“高数有什么用?买菜用得上吗?”面对高数态度如此,更复杂的算法知识就更不用说了。不过,一位清华毕业计算机教授在美国的经历证明了,算法或许不能在买菜时帮你省几个小钱,但可以在遇到重大事件时,帮你赚回1台车钱。

12月下旬,清华毕业、现任圣母大学计算机系终身副教授、博士生导师、电子系终身副教授史弋宇原计划从芝加哥经纽约前往百慕大旅游,不巧的是,他们在途中遇到了2名持枪匪徒,不仅抢走了他的钱包,“顺便”还开走了他的车。万幸,在警方已经半放弃的情况下,他凭借自己强大的逻辑能力和算法思维,独自找到了车子,虽然旅行泡汤,但至少损失挽回了大半。

事情起于当天中午,当时,他们在芝加哥中国城附近的加油站给轮胎充气,趁他不在车上,2个身材不高大约20来岁的黑人从后面车上下来,对他举起了枪。之后,他们把所有人赶下车,钱拿走,大摇大摆地开走了,顺带带走了史教授一家所有的行李,只给他们留了几个空空的钱包。

之后警方登场了——和诸多美国电影一样,扮演的是反面角色。第1次报警,911表示无法查询到史教授的车牌信息;第2次报警,911帮史教授转接芝加哥中央警察局,警察局表示,这事归911管;第3次报警,终于有警察到场,但是在现场草草转了一圈之后,他们就草草离去了。

警方不靠谱,史教授只能靠自己。在被抢时,史教授耍了个小心机,悄悄把手机留在了车子上,一开始,他寄望于手机定位能帮他找到车,然而劫匪对电子产品的追踪功能非常清楚,相关功能已经无法显示实时位置。之后,他又想到了自己马自达车上几乎没用过的Mazda Mobile Start (MMS)功能。

这个设备的作用是让车主用手机远程发动汽车引擎,给车辆上锁和开锁。那么,既然能用手机远程控制车子,在安装这个MMS的时候也一定启动了 GPS定位的功能。史教授上网一看,果然,MMS具备“CarFinder”的功能,可以大略显示车辆位置和发动机的启动状态。之后,这个功能就成了找到车子的关键。

首先介绍一下这个功能,在CarFinder界面中会显示1个红点和1个大圈,红点代表车的位置,大圈代表车的范围,然后右上角有距离显示81.8英里和相对误差+/- 22 英尺。没有地图,没有提供GPS坐标,换句话说,车主只能知道他和车的直接距离和相对位置。放在一般人身上,信息如此匮乏,基本上可以放弃了。然而,史教授的算法思维在这时候发挥了关键作用。

他先是按照CarFinder指示的相对距离,推断出车子大概是在芝加哥南郊。至于对不对,只要上路随便找1个方向开,距离缩短就是对的。结果上了朝芝加哥南郊的高速后,直线距离果然在快速减小,方向是正确的。

当新车到达芝加哥南郊I-94 130th st出口时,他们和马自达的距离已经减小到了2英里,车子很可能就在出口下面某处。不过,于是史教授从该出口下去以后转了一圈,发现周围都是公园,而且距离也没有继续减小,于是又开回高速。根据这种方法,史教授一路走一路缩小范围,最后对应地图,把目标确定在了下图中的Roseland中。

算法

(图片来源于新智元

在小范围内,相对位置就不那么靠谱了,于是,史教授选择了计算机算法中最直接的贪婪算法,也就是沿着一个方向开,直到距离不再明显变小(这是说明我们前进的方向已经几乎垂直于我们和目标之间连线),就转到垂直方向的街道再继续搜寻。

值得一提的是,在他们打到Roseland小区后,有1辆白色小车一直跟在他们后面,跟了好几个街区,由于对方有枪,史教授和他招来帮忙的学生小王约定,无论如何不要停车,就算停车,也要保持在D裆,随时准备开动。

在小区内转悠半天后,他们终于在直线距离200英尺的地方,转进了1条小路。在这条小路上,MMS显示的距离一路缩短,当开到尽头倒数第3间紧闭着的车库时,MMS发出提示音:车子就在里面!

史教授立刻通知了警察,为了避免打草惊蛇和确保自身安全,他们并没有在那里过多停留,而是选择开出大路等待。然而,没等警察来到,MMS上面突然显示车辆发动,而且离他们越来越远。2名警察到场知悉劫匪跑掉后,让史教授在路边等待,他们会去追踪。

之后,警察再次开始了他们的愚蠢表演。在3通电话中,警方第1通是问史教授软件怎么用;第2次警察说他们已经靠到了400米,史教授告诉他MMS还有个panic功能,手机上点击后可以让车发出很大的警报声;最后1次,警察说没找到车,于是史教授只能自己继续寻找。

好在,有了上午的成功经验,史教授轻车熟路地用贪婪算法,很快在另外一地的加油站找到了被劫车辆。这次他们把车停在了可以看到被劫车辆的位置,才打了911,而且为了防止警方30-40分钟不到、1次只派2-3个人的现象再度出现,他故意把情况报告的更加严重。

果然,这次过了不到五分钟,第一辆警车就到了。在随后的几分钟里,呼啦啦来了七八辆警车把加油站围了个水泄不通,下来的警察都穿着防弹背心,手放在腰间的枪上。一群警察小心翼翼的靠近那辆马自达,很快就确定了车里并没有人。

于是,整辆车“完璧归赵”,不仅如此,史教授还在车里找到了一些不属于自己的东西,比如1双崭新的Nike、一些吃剩的饮食包装,还有弥漫在车里的大麻味。只花了1天就找到被劫车辆,这种远超警方的效率,让警察也不由得感慨道:“They shouldn’t have messed up with computer science professors!”

最后再来介绍一下本次行动的功臣——贪心算法。贪心算法又称贪婪算法,是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。贪心选择是采用从顶向下、以迭代的方法做出相继选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题。

本文来源前瞻网,转载请注明来源。本文内容仅代表作者个人观点,本站只提供参考并不构成任何投资及应用建议。(若存在内容、版权或其它问题,请联系:service@qianzhan.com) 品牌合作与广告投放请联系:0755-33015062 或 hezuo@qianzhan.com

p28q7

分享:
标签: 算法 贪心算法

品牌、内容合作请点这里:寻求合作 ››

前瞻经济学人微信二维码

前瞻经济学人

专注于中国各行业市场分析、未来发展趋势等。扫一扫立即关注。

前瞻产业研究院微信二维码

前瞻产业研究院

如何抓准行业的下一个风口?未来5年10年行业趋势如何把握?扫一扫立即关注。

前瞻经济学人 让您成为更懂趋势的人

想看更多前瞻的文章?扫描右侧二维码,还可以获得以下福利:

  • 10000+ 行业干货 免费领取
  • 500+ 行业研究员 解答你的问题
  • 1000000+ 行业数据 任君使用
  • 365+ 每日全球财经大事 一手掌握
  • 下载APP

  • 关注微信号

文章评价COMMENT

还可以输入2000个字

评论载入中...
前瞻数据库
企查猫
前瞻经济学人App二维码

扫一扫下载APP

与资深行业研究员/经济学家互动交流让您成为更懂趋势的人

下载APP
前瞻经济学人APP

下载前瞻经济学人APP

关注我们
前瞻经济秀人微信号

扫一扫关注我们

意见反馈

×
J