Arora Algorithm 5 Dynamic Programming
Arora算法, 动态规划.
从上述分析可知, 我们的目标是在实例经过扰动和缩放后, 找一条最优的k-light portal-respecting环游, 其中\(k=\frac{24}{\epsilon}+4\). 我们可以使用自底向上的动态规划解决该问题, 具体过程如下.
首先要分析每个level正方形网格的状态数. 假设某level的网格上有\(4m\)个portal, 每个portal被环游穿过的次数只可能是\(0,1,2\)三种情况 (正如上文提到的, 超过\(3\)的穿越次数可由三角不等式减少), 则有至多\(3^4m\)种不同情况. 而当每个portal被环游穿过的次数确定后, 网格内路径的条数就确定了, 但每条路径连接哪两个portal仍然有若干种情况. 设网格内路径有\(r\)条, 则共有\(C(r)\)种不同的连接方式, 其中 \[ C_{r}=\frac{1}{r+1}\left(\begin{array}{c} 2 r \\ r \end{array}\right)=O\left(2^{2 r}\right)=O\left(2^{8 m}\right) \] 代表第\(r\)个Catalan数. 一个\(m=1\)的例子如下图所示.
因此, 该含有\(4m\)个portal的网格, 有至多\(3^{4m}\cdot O(2^{8m})\)个状态.由于\(m=O(\frac{\log n}{\epsilon})\), 因此状态个数为\(O(n^{\frac{1}{\epsilon}})\), 是多项式级别的. 在算法实现种, 有多种方法可以减少该状态数
- 每个portal被环游穿越的次数和必须是偶数, 该和的一半便是网格内含有的路径条数\(r\);
- 网格内的路径不能有交叉, 否则可以通过三角不等式减少其费用;
- 必须是k-light.
接下来考虑如何初始化状态. 对于网格正方形\(s\), 环游经过portal穿越\(s\)的路径分别为\((s_1,t_1),\ldots,(s_l,t_l)\), 设该状态的值为\(A[s,(s_1,t_1),\ldots,(s_l,t_l)]\), 代表经过该方块内所有顶点, 且符合指定进出路径的所有线段费用总和的最小值. 对于每个顶点, 找到包含且仅仅包含该顶点的最大网格块, 记为\(s\), 一个\(n=6\)的例子如下图所示. 遍历在\(s\)中所有可能的路径. 其他不包含顶点的网格也可按照上述方式计算状态值.
一种\(l=3\)的路径分配\((s_1,t_1),(s_2,t_2),(s_3,t_3)\)所对应的状态计算举例如下.
最后给出状态转移方程. 基本思路为按照level递减的顺序, 及网格的分割方式, 依次计算网格的状态值, 每次计算时使用到底层的四个子网格块, 一个例子如下.
具体计算方式见如下例子. 该例的计算方式为 \[
A\left[s,\left(s_{1}, t_{1}\right),\left(s_{2},
t_{2}\right)\right]=A\left[X,\left(a, t_{1}\right)\right]+A[Y,(b,
c)]+A\left[Z,\left(s_{1}, a\right),(d, b)\right]+A\left[Q,\left(s_{2},
d\right),(c, t_2)\right].
\]
