无人机大挑战

来自计算思维百科
跳转至: 导航搜索
无人机大挑战1.jpg

无人机大挑战是利用人工智能操作车辆进行的竞技赛,先到达目的地的车辆取胜。2004年度的无人机大挑战给出的路线是,跨越沙漠的240km路程。

现要使用4个摄像机全程转播。不过,因路程会跨越沙漠地区,所以能够安装摄像机的地点被限制为7个。这7个地点中如何预设4个摄像机,使得摄像机之间的间距达到最大,这样可以尽可能多地进行转播。

无人机大挑战2.png

解决方案

方案一:蛮力法

蛮力法的思路很简单,就是要从7个地点中选择4个地点安装摄像机,共有210种安装方式,我们可以将所有可能的安装地点列出,并且比较各个方案中摄像机间距,选出最大的作为最终结果。

运用的计算思维

蛮力法就是简单暴力。在不考虑时间消耗和人力消耗的情况下,蛮力法是解决一个问题最直接的方法,体现了机械化的思维方式。

方案二:贪心法

第一步:要使摄像机间距最大,那么摄像机的安装位置要越分散,所以,我们可以将第一台摄像机安装在0处;

无人机大挑战3.png

第二步:第二台摄像机与第一台摄像机的位置要尽可能大,那么最好的位置就是240处;

无人机大挑战4.png

第三步:要使第三台摄像机距离第一和第二台都比较远,那么最好的位置就是中点120处;

无人机大挑战5.png

第四步:第四台可以安装在0~120之间,也可以安装在120~240之间。如果是0~120之间,那么就应安装在70处,如果是120~240之间,那么就应该安装在220处,而两者相比,安装在70处更优;

无人机大挑战6.png

因此,四台摄像机的位置就固定在0、70、120以及240处。

运用的计算思维

贪心法在每一步都选择出当前最优解,同样可以方便地得到问题的解,体现了“优化”的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015