这每个字我都认识怎么放一起就看不懂了呢 | 关于《动态规划解两点多重问题》的进一步讨论

做为一名好久没开游戏，偶尔看看群，看看微信的老咸鱼，今天看到了群里有人在问北京启蒙军公众号上的《动态规划解两点多重问题》（下简称《问题》）一文里面的算法有没有实现好的轮子，作为一名好久没写程序的老咸鱼，也难免兴奋地搓手，有些跃跃欲试。但是，为啥记忆化搜索就写的这么简洁，而直接递推却要搞这么复杂呢？如果你急着出去抢 AP 不想看后文，那么这里是概括： field 之间的包含关系是一个偏序关系，所以问题本质是在有向无环图（偏序关系）上的动态规划。《问题》 中按照点到底边的距离排序，本质上是找出了一种此问题下有向无环图的拓扑序。

问题重述: 平面上有点 和 ， 称为底边。又有点集 ， 其中的点两两不重合(  ).

求一个最大的  使得  都有线段 ，  分别不与线段，相交。

很容易看出, 对于一个 ,, 要么 在 里面, 要么 在 外面. 如果我们将 定义为其覆盖的区域的点集,

那么我们可以将问题用包含于（ ）重述为

 (1)

注意, 包含于（）的等号成立时当且仅当.

那么, 当两个点不相同时 () 这种包含关系一定是真包含 ().

我们可以发现，三角形的包含关系是一个偏序关系。下面讨论一下在 上的相对应的偏序关系.

定义

为 上的二元关系。那么，是：

• 自反的：

• 反对称的： ，

• 传递的： ，

因此,  是 上的偏序关系. 下面将 简记为 .

现在我们可以将 (1) 式用偏序关系 重新描述如下:

那么可以看出来,  是 的一条链 (chain). 也是全序的. 所以, 问题就转换成了求一个偏序集上的最长链. 

令 为 中, 以 为结尾的最长链 (即 的满足全序性质的子集, 且 是其中的最大元) 的最大长度. 

 (*)

那么

就是《问题》文中的状态转移方程.

可以看出, 这是一个经典的动态规划问题. 动态规划问题的求解顺序非常关键, 这个问题通常使用记忆化搜索, 或者按照 DAG 图的拓扑序 (对应于偏序关系的线性扩展) 来递推. 很容易证明, 将  中的点, 按照到底边的距离升序排序, 是一个合法的线性扩展 (拓扑序), 这也是《问题》文中方法的正确性的关键.

记 为 到底边 的距离, 那么, 

 (2)

为了证明此命题, 我们证明

为假命题 (这是由于  ). 证明如下:

显然只需证当时,  . 容易知道

 可以有许多种取法, 比如, 分别由 和 向 作垂线 和 , 那么两条垂线要么在一条直线上,要么平行. 当他们在一条直线上时, 可以在上取得. 当他们平行时, 过 做 的平行线交 于. 那么, 可以在 上取得.

所以 

因此, (2) 为真. 

现在, 我们根据 来定义一个二元关系:

简记为 . 那么根据(*), 可以知道

又因为 是从 到 的映射, 所以 是一个全序关系. 因此, 也是 的一个线性扩展 (linear extension). 所以, 使用  来做为动态规划的顺序是正确的. 

由于我几乎所有名字里面带有“数”的课程都是 60 多分飘过, 或者重修过, 所以可能这些本来很简单的东西我却说得非常啰嗦, 或者蕴含了许多 bug, 所以欢迎评论指出错误. 另外, 欢迎在评论区提出新的改进,比如新的线性扩展方法, 或者更简洁的  的取法.