递归如何在分而治之的最大值集算法中工作？

Question

这是 Goodrich 的算法教科书中的伪代码算法，用于在一组点中查找主导二维点，称为查找最大值集：

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)，但我对使用此算法究竟是如何发现的一无所知。我通过蛮力解决了它。这开始是一个硬件问题，从技术上讲我可以继续前进，因为我确实找到了答案，但我真的需要对此有所了解并且我已经尝试了 2 本教科书和 google 但我认为我需要一个人这次。提前谢谢你，因为这是我第一次在堆栈上，请不要犹豫（请）给我任何关于我如何提出问题或提出我的 p 代码的更正

Answer 1

征服部分的想法是，您必须假设 returned 集合 M1 & M2 满足以下条件：

Any pair of points in the same set can be co-existing

也就是说，集合中的任何一对点都必须满足x1 < x2 && y1 > y2

而你合并M1和M2后，你也应该return一个满足这个条件的集合，最后得到的集合就是答案。

需要注意一点，我觉得合并的时候，x其实不需要比较，因为M1中的所有点都应该比那些x <=在 M2

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

如前所述，q不需要与M2
视觉上，q是M2中最小x和最大y的点，如前所述，所有M1的x 应该小于 M2 中的所有点，所以这里的主要点是 q 在 M2 中有最大的 y，因此要覆盖最大的 "potential" 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), Return {(3,1})

划分： (1,4) (2,6); L = (1,4); Return{(1,4)}； R = (2,6); Return{(2,6)}

划分： (4,5) (5,7); L = (4,5); Return{(4,5)}； R = (5,7); Return{(5,7)}

征服： (1,4) (2,6); M1 = {(1,4)}; M2 = {(2,6)} q = (2,6); return 合并集 = {(2,6)}

征服： (1,4) (2,6) (3,1)； M1 = {(2,6)}; M2 = {(3,1)}; q = (3,1); return 合并集 = {(2,6), (3,1)}

征服： (4,5) (5,7); M1 = {(4,5)}; M2 = {(5,7)}; q = (5,7); return 合并集 = {(5,7)}

征服： (1,4) (2,6) (3,1) (4,5) (5,7); M1 = {(2,6), (3,1)}; M2 = {(5,7)}; q = (5,7); return 合并集 = {(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); Return {(6,9}); R = (7,2); Return{(7,2)}

划分： (8,6) (9,3); L = (8,6); Return{(8,6)}； R = (9,3), Return {(9,3)}

征服： (6,9) (7,2); M1 = {(6,9)}; M2 = {(7,2)}; q = (7,2); return 合并集 = {(6,9), (7,2)}

征服： (8,6) (9,3); M1 = {(8,6)}; M2 = {(9,3)}; q = (9,3); return 合并集 = {(8,6), (9,3)}

征服： (6,9) (7,2) (8,6) (9,3); M1 = {(6,9), (7,2)}; M2 = {(8,6), (9,3)}; q = (8,6); return 合并集 = {(6,9), (8,6), (9,3)}

征服： (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); return 合并集 = {(6,9), (8,6), (9,3)}

==> Return {(6,9), (8,6), (9,3)}

递归如何在分而治之的最大值集算法中工作？

How does recursion work in a divide and conquer maxima set algorithm?

algorithm

recursion

divide-and-conquer