动态规划解两点多重问题
今天介绍一个有趣的小问题及其解法。
问题的背景是这样的：话说有个游戏叫做 Ingress，分为蓝绿两个阵营，双方的特工日常一般是争夺门泉（portal）的控制权，以及聚会开饭，在公频里互相怼两句之类的，两个阵营虽然价值观理念不同，但双方都有一种神秘的玩家叫做多重党，他们喜欢把控制场（control field）做成很多层，于是地图上经常会自组织出一些被称为多重控制场的谜之结构。
跟多重党相对还有一些玩家叫做胡连（xjbl）党。据调查，多重党最大的敌人不是敌对阵营，而是本阵营的胡连党。
而胡连党最大的敌人是本阵营的其他胡连党。
那我们回过头来，多重有很多种做法，选择因素取决于战机、地形和持有钥匙数量。其中一种最简单粗暴的叫做两点多重，也就是以两个 po 的连线为底边，找出一连串 po，使得每一个跟底边组成的三角形（也就是控制场），都能够包含之前的三角形。
于是问题就来了：如何在一堆 po 里面选择这样的一个子集，使得做出的多重层数最多呢？
当层数不是很多的时候，靠肉眼就能规划出来，但层数一多，肉眼就不好办了。于是需要写个程序来解决。我们有一位叫做猫猫的特工，他最近改名字叫 @ATemporaryName ，不知道是出于什么目的。总之，他是一位执行力很强说干就干的同志，马上写了一个使用贪心算法的规划程序。
猫猫选择了指定最终顶点的方式，因为这样路径比较可控。但这种方式的问题在于，指定的终点不一定是最好的。另外，贪心算法的结果也可能只是局部最优而不是全局最优。
这时大佬 @Allen9527 指出，只要控制好路径，顶点也可以自动选择，另外，这明显是个动态规划送分题啊！
我一看好像还真是！然后就吃咸鱼饭去了。
如果你已经忘了什么是动态规划，下面这段话来自维基百科：
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决。
很快，Allen 大佬给出了伪代码，总之思路就是先定终点，然后用递归倒推选择哪些 po，构成最佳路径。这就是经典的动态规划寻路问题的变种。
想到好多年没写过动态规划，要不我来实现一下好了。那么新的问题来了：倒推也就是递归，在计算规模很大的时候，是很吃亏的。可不可以不要递归，而且不指定终点呢？也就是用正推而不是倒推的方式，逐一算出每个 po 作为终点时，能够做出的最大层数。
实际上是可以的，但有两个困难。首先，每一步的时候，都不知道下一步取哪个或者哪些 po，因为没有方向。如果遍历所有候选，肯定是不能接受的，这点跟经典的简单寻路问题不一样。其次，计算每个 po 的最大层数时，需要知道它包含了哪些 po，这样就要求遍历所有其他 po，N*N 的复杂度。
当然，有多种方式可以解决，我选择了一种简单粗暴的方式来处理：考虑到如果后面的三角形要包含前面的三角形，后面的顶点一定比前面的顶点离底边的距离更远。所以我们可以先对候选 po 按照离底边从近到远排序，然后以这个顺序计算。这样就解决了第一个方向性问题。对于第二个问题，由于排序后只需要从比它自己更近的 po 里面去找包含的顶点，计算量可以减少一半。
计算过程中还会涉及到两个数学问题：
1. 如何判断一个点在一个三角形内部？直接在 stackoverflow 翻答案了，最快的方式是计算这个点相对于三条边的方向，如果这个点在三条边对应的方向（正负）都是一致的，说明在它们围成的区域内。
2. 如何计算一个点离一条直线的距离？在 Wikipedia 翻答案，解析公式套上就得分。
那么最后程序写出来就是这样了。实际在798和颐堤港算了一下，可是算出来的结果大佬们表示很难接受。毕竟优化的目标只有层数，完全没有考虑大佬们也是活生生的人，一个个鲜活的生命。步行距离和人参安全还是需要考虑的。
所以在准备候选 po 数据时，应该剔除那些打死都不愿意去的地方。另外，未来还可以对路径距离再做优化，这样就比较人性化了。
最后作为纯YY，规划了一个北京中轴线从奥森做到xxx广场的巨型两点多重，规划结果有 108 个 po，在我的电脑上目测两秒左右。可以吗，可以的。
要不要试试？目测应该比北京中轴线任务坑一百倍左右。
