使用动态编程查找最大间隔

Question

http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf 我正在为练习做这些问题,我遇到了一个困扰我的问题.

7.(a)假设我们在平面中给出了一组L个n个线段,其中每个线段在线y = 0上有一个端点,线y上有一个端点y = 1,并且所有2n个端点都是不同的.描述并分析算法以计算L的最大子集,其中没有一对段相交.

(b)假设我们在平面中给出了一组L个n个线段,其中每个线段的端点位于单位圆x 2 + y 2 = 1上,并且所有2 n个端点都是不同的.描述并分析算法以计算L的最大子集,其中没有一对段相交.

在O(n log n)时间内,我想出了如何做7a(问题是找到增加数字的最大子集的伪装问题).我几乎接近放弃7b,因为我无法找到一种方法来做到这一点.

但是,有没有办法将7b的前提转换为更像7a的东西？我觉得这是解决问题的正确方法,任何帮助解决这个问题都会非常感激.

Answer 1

我无法想出一种 O(n*log(n)) 算法，但这里有一个 O(n ² ) 算法。

我们的想法是，我们构建一个有向图，其中顶点表示给定集合中的段，边表示“位于右侧”关系。

令 L 为线段列表：{(a ₁ , b ₁ ), (a ₂ , b ₂ ), ..., (a _n , b _n )}，其中 a _k和 b _k是第 k 个线段的端点。

令 L' 为段列表：{(a ₁ , b ₁ ), (b ₁ , a ₁ ), (a ₂ , b ₂ ), (b ₂ , a ₂ ), ..., (a _n , b _n ), (b _n , a _n )}。

令图的顶点具有从 1 到 2*n 的索引，每个索引 k 代表线段 L'[k]，即 (a _k/2 , b _k/2 ) 如果 k 是奇数，并且 (b _k/2 , a _k/2 ) 如果 k 是偶数。

当点 a ₁、 a ₂、b ₂、 b ₁按顺时针顺序放置在单位圆上时，称线段 ( a _{1 , b 1 ) 位于线段 (a 2} , b _{2 )}的右侧。

请注意，1）如果一个线段位于另一线段的右侧，则它们不相交；2) 如果 L 中的两条线段不相交，则 L' 中四个相应线段中的两条线段必然位于另一条线段的右侧；3) L 中的任何一组不相交线段都由 L' 的一系列线段定义，每个线段位于前一个线段的右侧。

算法概要：

for every k1 from 1 to 2*n:
    for every k2 from 1 to 2*n:
        if (L'[k1].a, L'[k1].b) lies to the right of (L'[k2].a, L'[k2].b):
            add a directed edge (k1, k2) to the graph 
Find the longest path in the graph: (k1, k2, ..., km). 
The answer to the problem is: (k1/2, k2/2, ..., km/2).