威利在哪里:美工程师开发最快路径策略

2015-02-15 09:08  阅读 621 次 评论 0 条

软曼网:《威利在哪里?》是英国画家马丁·汉福德(Martin Handford)在1986年开创的一个绘本系列。其中读者的任务就是要从大量的各色人物中找出一个名叫威利的人,这个小伙子总是身穿红白条纹的衣服, 戴着毛绒帽。由于画面上人物太多,场景繁杂,有时候连成年人都难以找到威利在哪里。

威利在哪里:美工程师开发最快路径策略

由于这项任务的艰巨性,奥尔森利用机器学习的方法,基于一种算法来拟近所谓“最优化搜寻路径”。使用这种算法运行5分钟之后,奥尔森得到了一条最优化路径。

威利在哪里:美工程师开发最快路径策略

《威利在哪里?》是英国画家马丁·汉福德在1986年开创的一个绘本系列。近日,一名美国工程师设计了一款程序,通过将人物呈现在画面中的不同位置,能够自动创建出找到威利的最快搜寻路径策略。

威利在哪里:美工程师开发最快路径策略

如果遵循这样的规则,奥尔森自己可以对大部分作品在10秒钟之内扫完全图。另外他还发现,至少在4次试验中,一套图书的第一本里出现了例外的情况,他的这套战略没能奏效。


据英国《每日邮报》报道,在英国有一套几乎家喻户晓的经典儿童绘画读物——《威利在哪里?》(Where's Wally?)这套书在美国被称作《瓦尔多在哪里?》(Where’s Waldo?)。它曾经让数以百万计的孩子为之着迷。

简单来说,《威利在哪里?》是英国画家马丁·汉福德(Martin Handford)在1986年开创的一个绘本系列。其中读者的任务就是要从大量的各色人物中找出一个名叫威利的人,这个小伙子总是身穿红白条纹的衣服, 戴着毛绒帽。由于画面上人物太多,场景繁杂,有时候连成年人都难以找到威利在哪里。而现在,为了让威利变得好找一些,一名美国密歇根州的计算机工程师近日 设计了一款基于机器学习以及算法的战略程序。通过将人物呈现在画面中的不同位置,兰德尔·奥尔森(Randal Olson)研发的程序能够自动创建出找到威利的最快搜寻路径策略。

他所采用的这一方法是基于此前一个名叫本·布莱特(Ben Blatt)的人在2013年11月发表在美国《Slate》杂志上的一项策略。在那项研究中,布莱特总结了该绘本系列7套书中威利出现过的68个位置。 奥尔森使用了这些位置点的数据并据此创建了一个所谓“核心密度估计”结果。这样就建立起了在某一页面上的某一特定点上威利出现的概率统计。

基于此,奥尔森发现威利极少出现在页面左上方位置或是页面的边缘位置上,这样做的原因可能是为放置规则说明框以及印刷时对边缘留有空白余量的考虑。同样,威利从未出现在页面右侧的底部位置。

接着,奥尔森利用著名的“旅行商问题”来搜寻威利可能出现的任何位置上的最快检索路径,也即让重复路径减到最小。奥尔森表示:“用计算机术语来 说,这就意味着我们创建了68个威利可能会出现的点的列表,随后进行逐项检验。这全部的68个点可以被组织为2.48*10^96种可能组合。做一下对比 的话,这个数字超过了宇宙中所有原子的数量总和。”

威利在哪里:美工程师开发最快路径策略

“威利”的经典形象——这个小伙子总是身穿红白条纹的衣服,戴着毛绒帽。

威利在哪里:美工程师开发最快路径策略

他所采用的这一方法是基于此前一个名叫本·布莱特的人发表在美国《Slate》杂志上的一项策略。在那项研究中,布莱特总结了该绘本系列7套书中威利出现过的68个位置。

威利在哪里:美工程师开发最快路径策略

奥尔森使用位置点的数据并据此创建了一个所谓“核心密度估计”结果。这样就建立起了在某一页面上的某一特定点上威利出现的概率统计。

由于这项任务的艰巨性,奥尔森利用机器学习的方法,基于一种算法来拟近所谓“最优化搜寻路径”。使用这种算法运行5分钟之后,奥尔森将其路径划分为4个部分:第一部分用蓝色表示,第二部分用橘色,第三部分用绿色,第四部分则用红色。

奥尔森表示:“这条路径代表了在某一页面上找到威利的最短可能路径。因此如果我们能够精确地遵照这条路径,我们将最有可能比一般人使用传统方法更快的找出威利。”

不过,奥尔森先生也承认人们一般根本不可能记得住那么复杂的路径,因为人脑毕竟不是电脑,于是它也给出了一些“走捷径”的小建议。

他表示,进行搜寻的人应该先从页面左侧的底部开始,而如果威利不在页面左侧底部,那么很有可能他根本就不在页面的左侧!页面右侧的上部1/4区 域则是第二个需要搜寻的区域,奥尔森表示:“威利似乎喜欢藏在右侧页面的上面1/4区域。”接下来再检查一下右侧页面的右侧底部。

奥尔森表示,威利似乎非常憎恨出现在右侧页面的左侧底部位置,因此人们不应该在那一区域浪费时间,弄得自己在检查其他区域时感到疲惫。如果遵循这样的规则,奥尔森自己可以对大部分作品在10秒钟之内扫完全图。

另外奥尔森还发现,至少在4次试验中,一套图书的第一本里出现了例外的情况,他的这套战略没能奏效。这也就是说,这样一套书里,其中的第一本书 是最有可能不适用这一搜寻战略的。他说:“我做这些纯粹就是为了好玩,我可不推荐你在休闲时随意玩这种游戏的时候运用我的这个策略。生活里有那么多事情, 寻找威利让人享受的其实就是这种寻找的过程,而不是它的结果。”

历史上的今天:

本文地址:http://www.ruanman.net/archives/5969.html
版权声明:本文为原创文章,版权归 ﹖右掱邊﹎ヤ 所有,欢迎分享本文,转载请保留出处!

发表评论

您必须 登录 才能发表留言!