S중첩 될 수있는 자연수의 간격 세트 (n 개의 간격 포함)이고 N은 숫자 목록 (n 개의 숫자 포함) 이라고합시다 .
나는 목록 N의 각 숫자에 대해 그것을 포함하는 P에 적어도 하나의 간격이 있도록 S의 가장 작은 부분 집합 (P라고 부르 자)을 찾고 싶습니다. P의 간격은 겹칠 수 있습니다.
간단한 예 :
S = {[1..4], [2..7], [3..5], [8..15], [9..13]}
N = [1, 4, 5]
// so P = {[1..4], [2..7]}
동적 알고리즘이 항상 작동하지 않을 수 있다고 생각하므로이 문제에 대한 해결책 (또는 변환 할 수있는 유사한 알고리즘)을 아는 사람이 있다면 좋을 것입니다. O (n ^ 2 솔루션)을 만들려고합니다.
탐욕스러운 접근 방식이 있습니다.
P = {}
for each q in N: // O(n)
if q in P // O(n)
continue
for each i in S // O(n)
if q in I: // O(n)
P.add(i)
break
하지만 그것은 O (n ^ 4)입니다 .. O (n ^ 2)라는 탐욕스러운 접근 방식을 만드는 데 도움이 될 것입니다!
감사!
* 업데이트 : * 나는이 문제에 부딪 혔고 O (n ^ 2) 해결책이 있다고 생각 합니다 !!
내가 옳다고 생각하면 알려주세요 !!!
N = MergeSort (N)
upper, lower = infinity, -1
P = empty set
for each q in N do
if (q>=lower and q<=upper)=False
max_interval = [-infinity, infinity]
for each r in S do
if q in r then
if r.rightEndPoint > max_interval.rightEndPoint
max_interval = r
P.append(max_interval)
lower = max_interval.leftEndPoint
upper = max_interval.rightEndPoint
S.remove(max_interval)
나는 이것이 작동 할 것이라고 생각한다 !! 카운터 솔루션을 찾으려고합니다. 하지만 그래 !!
이 문제는 NP-complete 인 set cover 문제와 유사합니다 (즉, 지수보다 빠른 해가 없음). 다른 점은 간격이 항상 인접한 요소 (N의 임의 하위 집합이 아님)를 포함하므로 더 빠른 솔루션을위한 길을 열어 준다는 것입니다.
http://en.wikipedia.org/wiki/Set_cover_problem
Mike가 제안한 솔루션이 충분하다고 생각합니다. 하지만 저는 꽤 솔직한 O (N ^ 2) 탐욕스러운 알고 있다고 생각합니다. Mike의 솔루션처럼 시작됩니다 (또한 Mike의 솔루션도 비슷한 방식으로 개선 될 수 있다고 생각합니다).
N 개의 숫자를 정렬하고 배열 ELEM에 정렬합니다. 복잡성 O (N * lg N);
이진 검색을 사용하여 각 간격 S [i]에 대해 S [i]에 포함 된 ELEM 요소의 시작 및 끝 인덱스를 식별합니다. 이 숫자 쌍을 배열 COVER에 넣습니다. 두 인덱스의 차이는 얼마나 많은 요소를 다루는 지 알려줍니다. 간단하게 배열 COVER_COUNT를 배치하겠습니다. 복잡성 O (N * lg N);
ELEM에서 N이 이미 포함 된 요소까지 보여주는 인덱스 포인터 p를 도입합니다. p = 0으로 설정하면 0 번째까지 (제외 된) 모든 요소가 처음에 포함됩니다 (즉, 요소가 없음). 복잡성 O (1). 또한 구간 S [i]가 커버리지 세트에 이미 포함되어 있는지를 반영하는 부울 배열 IS_INCLUDED를 도입합니다. 복잡성 O (N)
그런 다음 ELEM의 0 번째 요소부터 시작하여 ELEM [0]을 포함하고 더 큰 커버리지 COVER_COUNT [i]를 포함하는 간격이 무엇인지 확인합니다. i 번째 간격이라고 상상해보십시오. 그런 다음 IS_INCLUDED [i]를 true로 설정하여 포함됨으로 표시합니다. 그런 다음 p를 end [i] + 1로 설정합니다. 여기서 end [i]는 COVER [i] 쌍의 끝 인덱스입니다 (실제로 end [i]까지 모든 요소가 포함됨). 그런 다음 p를 알면 COVER_COUNT의 모든 요소를 업데이트하여 각 간격이 포함하는 아직 포함되지 않은 요소의 요소 수를 반영합니다 (이 작업은 O (N) 시간에 쉽게 수행 할 수 있음). 그런 다음 ELEM [p]에 대해 동일한 단계를 수행하고 p> = ELEM.length까지 계속됩니다. 전체 복잡도가 O (N ^ 2)임을 알 수 있습니다.
O (n ^ 2)에서 끝내고 IS_INCLUDED에서 최적의 커버 세트에 포함 된 S 간격에 대해 참이됩니다.
이 솔루션이 당신에게 합리적이라고 생각하고 내가 모든 것을 잘 계산했는지 알려주십시오.
추신 : algo에 의해 발견 된 솔루션의 최적 성은 귀납과 모순으로 증명 될 수 있다고 덧붙이고 싶었습니다. 모순적으로, 최소 하나의 최적 솔루션이 ELEM [0] 요소를 덮는 가장 긴 간격을 포함한다는 것을 쉽게 보여줍니다. 그렇다면 귀납법을 통해 우리는 알고있는 각 다음 요소에 대해 커버 된 나머지 요소의 수와 관련하여 가장 긴 간격을 선택하고 가장 왼쪽이지만 아직 커버되지 않은 요소를 다루는 전략을 계속 따를 수 있음을 보여줄 수 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다