分治法最大值集合算法中递归如何工作？

Question

分治法最大值集合算法中递归如何工作？

3

以下是Goodrich算法教材中的伪代码算法，用于在点集中查找支配2D点，也称为查找极大值集：

Algorithm MaximaSet(S):

Input: A set,S,of n points in the plane

Output: The set, M, of maxima points in S 

if n ≤ 1

then return S  

Let p be the median point in S, by lexicographic (x,y)-coordinates 

Let L be the set of points lexicographically less than p in S 

Let G be the set of points lexicographically greater than or equal to p in S 

 M1 ←MaximaSet(L) 
 M2 ←MaximaSet(G) 

 Let q be the lexicographically smallest point in M2 

  for each point, r, in M1 do 

              if x(r) ≤ x(q) and y(r) ≤ y(q) 

              then Remove r from M1 

 return M1 ∪ M2

我的问题在于第10、11行的两个递归调用。我理解的是，第一个调用在第10行呼叫M1将L侧分成另一个L和G集合，然后再将下一个L分成另一个L和G集合，直到只剩一个集合，接下来的一行会对M2的G侧做同样的事情，但现在它如何与q进行比较呢？能有人帮我追踪这个算法的征服部分吗？

给定 (1,4) (2,6), ( 3,1) (4,5) (5,7) (6,9) (7,2), (8,6) (9,3)

我知道最大值集合是(6,9) (8,6) (9,3)，但我卡在了究竟是怎样运用这个算法得出答案。我用暴力法解决了这个问题。这开始作为一个作业问题，虽然我找到了答案，但我真的需要理解这个算法，我已经尝试了两本教科书和谷歌搜索，但我想这次我需要一个人的帮助。预先感谢，并且由于这是我第一次在堆栈上，请不要犹豫（请友好地）向我提出任何关于我提问或呈现P代码的更正。

- Femke

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- shole · Accepted Answer

征服部分的想法是，您必须假定返回的集合M1和M2满足以下条件：

任何同一集合中的两个点都可以共存

也就是说，集合中任意两个点都必须满足x1 < x2 && y1 > y2 在合并M1和M2之后，您还应该返回一个满足此条件的集合，最后得到的集合就是答案。

需要注意的一点是，在合并时，我认为实际上不需要比较x，因为M1中的所有点的x都应该小于等于M2中的点。

我们使用q，M2中的第一个点，与M1中的所有点进行比较，因为：

如前所述，q不需要与M2中的其他元素进行比较

从视觉上看，q是M2中x最小且y最大的点。如前所述，M1中所有的x都应该小于M2中的所有点，因此这里的重点是q在M2中具有最大的y，因此具有最大的“潜力”来覆盖（消除）M1中的点。

综合1和2，算法使用q将所有M1中的点与之进行比较，以尝试消除无望的候选项，并将剩余的与M2联合起来形成一个新的集合，满足上述条件。

让我们使用您的示例进行演示：

划分： (1,4) (2,6) (3,1) (4,5) (5,7) (6,9) (7,2) (8,6) (9,3); L = (1,4) (2,6), ( 3,1) (4,5) (5,7); R = (6,9) (7,2), (8,6) (9,3)

划分： (1,4) (2,6) (3,1) (4,5) (5,7); L = (1,4) (2,6), (3,1); R = (4,5) (5,7)

分治: (1,4) (2,6) (3,1); L = (1,4) (2,6); R = (3,1), 返回 {(3,1})

分治: (1,4) (2,6); L = (1,4); 返回 {(1,4)}; R = (2,6); 返回 {(2,6)}

分治: (4,5) (5,7); L = (4,5); 返回 {(4,5)}; R = (5,7); 返回 {(5,7)}

合并: (1,4) (2,6); M1 = {(1,4)}; M2 = {(2,6)} q = (2,6); 返回合并后的集合 = {(2,6)}

合并: (1,4) (2,6) (3,1); M1 = {(2,6)}; M2 = {(3,1)}; q = (3,1); 返回合并后的集合 = {(2,6), (3,1)}

合并: (4,5) (5,7); M1 = {(4,5)}; M2 = {(5,7)}; q = (5,7); 返回合并后的集合 = {(5,7)}

合并: (1,4) (2,6) (3,1) (4,5) (5,7); M1 = {(2,6), (3,1)}; M2 = {(5,7)}; q = (5,7); 返回合并后的集合 = {(5,7)}

分治: (6,9) (7,2) (8,6) (9,3); L = (6,9) (7,2); R = (8,6) (9,3)

分治: (6,9) (7,2); L = (6,9); 返回 {(6,9}); R = (7,2); 返回 {(7,2)}

Divide: (8,6) (9,3); L = (8,6); 返回 {(8,6)}; R = (9,3), 返回 {(9,3)}

Conquer: (6,9) (7,2); M1 = {(6,9)}; M2 = {(7,2)}; q = (7,2); 返回合并集合 = {(6,9), (7,2)}

Conquer: (8,6) (9,3); M1 = {(8,6)}; M2 = {(9,3)}; q = (9,3); 返回合并集合 = {(8,6), (9,3)}

Conquer: (6,9) (7,2) (8,6) (9,3); M1 = {(6,9), (7,2)}; M2 = {(8,6), (9,3)}; q = (8,6); 返回合并集合 = {(6,9), (8,6), (9,3)}

Conquer: (1,4) (2,6) (3,1) (4,5) (5,7) (6,9) (7,2) (8,6) (9,3); L = (1,4) (2,6) (3,1) (4,5) (5,7); M1 = {(5,7)}, M2 = {(6,9), (8,6), (9,3)}; q = (6,9); 返回合并集合 = {(6,9), (8,6), (9,3)}

==> 返回 {(6,9), (8,6), (9,3)}