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

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

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

你收到圣诞礼物了吗？

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

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

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

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

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

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

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

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

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

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

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

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

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