首页
学习
活动
专区
工具
TVP
发布

为圣诞老人设计“送礼路线”

冬季送温暖,圣诞老人排忧解难。

图文版本送给不方便打开的朋友 (°u°)」

你收到圣诞礼物了吗?

传说圣诞老人住在芬兰拉普兰地区的圣诞老人村(Santa Claus' House),每年 12 月 24 日,他会在夜晚出发,驾着 9 只驯鹿拉的雪橇,挨家挨户爬烟囱、送礼物。

地球这么大,如何为圣诞老人安排一个合理的「送礼路线」?

解决这件事有一个专有名词:「路径规划」,指的是对起点和终点间未知路径进行决策的研究

在开始规划之前,我们需要先确定这条路径需要满足的条件,比如所有地点只经过一次,毕竟每家只用送一次礼物;再比如时间有限,要尽量少走回头路。

基于这些条件,我们可以选择图方法,或是树方法。

图方法即将所有必须经过的地点设为节点,可以通过的路径设置为线,依据条件寻找最优路径;树方法则是从起点开始向外拓展树状结构,随机踩点直到找到抵达终点的方法。

送快递、送外卖,都是典型的路径规划场景。更复杂的还有滴滴这类出行软件。

对于滴滴来说,路径规划核心是价格最低、司机效率最高和交通系统运行效率最佳,需要进行大量运算。他们的选择是机器学习,从过往出行数据中寻找最优解。

路径规划是一个非常常见的课题,应用也非常广泛。

游戏里的 NPC 应该如何移动,才不至于那么傻?

城市道路网又该如何规划,才能保证交通效率最高?

狭义的路径规划只有决策,更广义的路径规划还包含信息的获取、感知、通信、控制和执行

听起来是不是有点熟悉,自动驾驶很大程度上就是一个路径规划过程

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20191225A0RFBS00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券