최대 비 지배 집합 알고리즘

Question

다음 문제에 대한 알고리즘을 완료하십시오. 2D 평면에서 n 점의 집합 S가 주어지면 x1> x2이면 점 (x1, y1)이 다른 점 (x2, y2)을 지배하고 y1> y2이다. M이 S의 부분 집합이고 M의 다른 점이 S의 다른 점에 의해 지배되는 점 M의 가장 큰 집합을 찾습니다.

Answer 1

x 좌표를 증가시켜 모든 점을 정렬하십시오. 두 점의 x 좌표가 같으면 y 좌표를 줄여 정렬합니다. 이제, y 좌표가 정렬 순서에서 증가하지 않는 경우에만 하위 점 집합이 비 지배적임을 나타낼 수 있습니다. 즉, 각 y 좌표는 하위 시퀀스의 이전 좌표와 같거나 작습니다.

그래서 알고리즘은 다음과 같습니다

1. 정렬 점을 상기 한 바와 같이. 시간 : O (n * logn).
2. y 좌표의 가장 길지 않은 증가하지 않는 서브 시퀀스를 찾습니다. 시간 : O (n * logn). 이것은 longest increasing subsequence을 찾는 알고리즘을 적용하여 수행 할 수 있습니다.

이것은 O (n * logn)에서 가능한 가장 큰 세트를 제공합니다.

Answer 2

O (n * logn) 시간에이를 수행하는 분할 및 정복 알고리즘이 있습니다.

포인트를 x 좌표에 따라 각각 n/2 크기의 두 개의 절반으로 나눕니다. 우리는 비 지배적 인 점 집합을 양쪽 반에서 찾는다. 오른쪽 반쪽에있는 모든 비 지배 포인트가 최종 목록에 존재한다는 것을 관찰해야합니다.

이 관찰을 통해 우리는 결합 단계를 작성할 수 있습니다. 오른쪽에 비 지배 집합에있는 지점의 가장 높은 y 좌표보다 y 좌표가 낮은 왼쪽 절반에있는 모든 비 지배 지점을 제거합니다 절반. 비 지배 점 집합이 있습니다.

알고리즘 : 시간

Find the median along x axis - O(n) time 
Find non-dominated points in the right half - T(n/2) 
Find non-dominated points in the right half - T(n/2) 
set of non-dominated points could be on O(n) so, the combine step might have to check O(n) points 

식 :가

T(n) = 2T(n/2) + O(n) which is O(n*logn) 

넌 O이 더욱 향상시킬 수있다 (N * logH) H 비 지배 점의 개수 , 문제에 대한 더 많은 통찰력이 필요하며 작업을 진행하는 좋은 연장입니다.