做为一名好久没开游戏，偶尔看看群，看看微信的老咸鱼，今天看到了群里有人在问北京启蒙军公众号上的《动态规划解两点多重问题》（下简称《问题》）一文里面的算法有没有实现好的轮子，作为一名好久没写程序的老咸鱼，也难免兴奋地搓手，有些跃跃欲试。但是，为啥记忆化搜索就写的这么简洁，而直接递推却要搞这么复杂呢？如果你急着出去抢 AP 不想看后文，那么这里是概括： field 之间的包含关系是一个偏序关系，所以问题本质是在有向无环图（偏序关系）上的动态规划。《问题》 中按照点到底边的距离排序，本质上是找出了一种此问题下有向无环图的拓扑序。
问题重述: 平面上有点 和 ， 称为底边。又有点集 ， 其中的点两两不重合( ).
求一个最大的 使得 都有线段 ， 分别不与线段，相交。
很容易看出, 对于一个 ,, 要么 在 里面, 要么 在 外面. 如果我们将 定义为其覆盖的区域的点集,
那么我们可以将问题用包含于（ ）重述为
(1)
注意, 包含于（）的等号成立时当且仅当.
那么, 当两个点不相同时 () 这种包含关系一定是真包含 ().
我们可以发现，三角形的包含关系是一个偏序关系。下面讨论一下在 上的相对应的偏序关系.
定义
为 上的二元关系。那么，是：
• 自反的：
• 反对称的： ，
• 传递的： ，
因此, 是 上的偏序关系. 下面将 简记为 .
现在我们可以将 (1) 式用偏序关系 重新描述如下:
那么可以看出来, 是 的一条链 (chain). 也是全序的. 所以, 问题就转换成了求一个偏序集上的最长链.
令 为 中, 以 为结尾的最长链 (即 的满足全序性质的子集, 且 是其中的最大元) 的最大长度.
(*)
那么
就是《问题》文中的状态转移方程.
可以看出, 这是一个经典的动态规划问题. 动态规划问题的求解顺序非常关键, 这个问题通常使用记忆化搜索, 或者按照 DAG 图的拓扑序 (对应于偏序关系的线性扩展) 来递推. 很容易证明, 将 中的点, 按照到底边的距离升序排序, 是一个合法的线性扩展 (拓扑序), 这也是《问题》文中方法的正确性的关键.
记 为 到底边 的距离, 那么,
(2)
为了证明此命题, 我们证明
为假命题 (这是由于 ). 证明如下:
显然只需证当时, . 容易知道
可以有许多种取法, 比如, 分别由 和 向 作垂线 和 , 那么两条垂线要么在一条直线上,要么平行. 当他们在一条直线上时, 可以在上取得. 当他们平行时, 过 做 的平行线交 于. 那么, 可以在 上取得.
所以
因此, (2) 为真.
现在, 我们根据 来定义一个二元关系:
简记为 . 那么根据(*), 可以知道
又因为 是从 到 的映射, 所以 是一个全序关系. 因此, 也是 的一个线性扩展 (linear extension). 所以, 使用 来做为动态规划的顺序是正确的.
由于我几乎所有名字里面带有“数”的课程都是 60 多分飘过, 或者重修过, 所以可能这些本来很简单的东西我却说得非常啰嗦, 或者蕴含了许多 bug, 所以欢迎评论指出错误. 另外, 欢迎在评论区提出新的改进,比如新的线性扩展方法, 或者更简洁的 的取法.
It's Time to Move!
点击阅读全文
欢迎登陆北京ingress蓝军官网
扫一扫关注我们吧↓
本文还将被推送到
历史文章请访问 https://bjres.net 查看
投稿邮箱：tougao@bjres.net
如投稿后未得到回复，请Tele联系 @alexrowe