적용 범위를 최대화하고 항목 사용을 최소화하는 알고리즘?

Question

나는 이런 식으로 상상할 수있는 시나리오를 가지고있다 :

너비가 100 픽셀, 높이가 1000 픽셀 인 이미지로 시작한다. 해당 이미지 외에도 해당 이미지의 잘린 섹션 집합이 있습니다. 각 섹션의 너비는 100x100 픽셀입니다. 섹션에 포함 된 이미지의 일부가 다릅니다. 예를 들어 맨 위 (픽셀 0)에서 시작한 다음 세로 픽셀 3에서 시작한 다음 세로 픽셀 9에서 시작하는 등의 작업을 수행 할 수 있습니다.

내가해야 할 일은 작은 사진 세트를보고 원본 이미지를 가장 많이 차지하는 부분을 선택하는 것입니다.

노트의 몇 :

1. 이미지의 내용은 정말 중요하지 않습니다. 중요한 좌표와 실제로 일치합니다.
2. 재구성 할 때 이미지에 틈이 생기지는 않지만 일 수 있습니다.은 바닥에 도달하기에 충분하지 않습니다.
3. 섹션 사이에 많은 겹침이 있습니다. 실제로 두 섹션 사이에 픽셀 또는 두 개의 (수직) 차이 만있을 수 있습니다.

누구나 올바른 방향으로 나를 가리킬 수 있습니까? 이런 종류의 무자비한 일을 할 수는 있지만 더 좋은 방법이 있다고 가정합니다.

Answer 1

미안하지만이 문제가 NP-hard 인 이유를 알 수 없습니다.

일반적인 아이디어는 당신이 "최고"섹션을 선택하여 이미지의 반복적 하단 부분을 제거하는 것이 오, 즉

• 당신이 만약 이미지
• 의 바닥을 커버 가장 큰 부분 (마지막 부분의 픽셀을 다루는 섹션이 없으므로) 가장 가까운 것을 취하면됩니다.
• 린스와

이 섹션을 정렬하여 시작 반복합니다. (0,1,3,10, ..., 988,999)와 같은 것을 얻을 것입니다. 여기서 0은 상단 픽셀에서 시작하는 섹션에 해당합니다. (그리고 999에 해당하는 것은 단 한 줄만 포함합니다)

원본 이미지가 100xN이라고 가정합니다. 초기에는 N = 1000입니다.

원본 이미지의 끝 부분을 가장 잘 나타내는 이미지의 인덱스를 n이라고합니다. 즉, n은 해당 목록에서 n + 100> = N과 같이 가장 작은 숫자입니다. 그러한 숫자가 없다면, n은 단순히 가장 큰 숫자입니다.

하여 정렬 된리스트이면 (0,1, ... 899, 900, 901, ..., 999)을, N = 900

하여 정렬 된리스트 인 경우

(0,1, ... 899 , 905, 910, ..., 999) 사용자의 정렬 된리스트의 경우, N = 905

(0,1, ..., 888,898) 다음에 n = 898

이어서 N = N 다시 시작할 (물론 원본 이미지의 맨 아래 부분을 제거했습니다.) (물론, 정렬 된 목록에서 "> = n"인 모든 섹션을 제거하십시오.)

고정 된 높이 섹션 xels)은 NP 경도를 제거합니다.

Answer 2

나는 이것이 http://en.wikipedia.org/wiki/Maximum_coverage_problem이라고 생각합니다. - 세트의 요소는 픽셀입니다 (픽셀 단위로 처리하지 않도록 코드를 작성할 수 있습니다).

100x1000이므로이 문제는 더 이상 NP 하드가 아니며 아마도 P 짝수입니다. 욕심 많은 접근 방식은 효과가 없지만 다음과 같이 동적 프로그래밍 솔루션이 있습니다. 이는 충분히 펼쳐진 경우 대략 O(N) 시간에 작동합니다. 그렇지 않은 경우 O(N * max_overlap_#)입니다. 트릭은 "앞뒤로 이동"입니다.

input: 
    [      ] to fill 
    [ (] ) { ([}) ] ([) ] 
return: 
    Result set of squares which maximize cover, secondarily 
    minimizing the size of the Result set if covered areas are equal 

the score of the leftmost element is {area:100^2, num:1} 
for each square S in order, left->right: 
    (Assuming you pick S in Result...) 
    let Candidates = {all squares which overlap S and are left of S} 
        + {first non-overlapping square left of S} 
    for each candidate C: 
     let score(S) = score(C) + {area:new_area_covered_by_S, num:1} 
     pick candidate BestC which maximizes score(S) 
     draw a line between S and BestC 

Take the square with the best score, and work your way backwards 
along the chain of best-picks, returning only those squares. 

이 "는 사각형으로 다루,이 사각형으로 덮여 있어야합니다 가능하다면, 모든 지점에서"당신은 여분의 0.0001 % 적용 범위에 대해서도, 즉 여분의 제곱을 추가 할 것입니다 가정합니다. 이 알고리즘을 적절하게 교환하기 위해 수정할 수 있습니다.

이것은 거의 모든 사각형이 단일 지점에서 서로 겹치지 않는다고 가정합니다 (약간 펼쳐지지만 여전히 겹칠 수도 있음). 그렇지 않으면 오랜 시간이 걸릴 수 있습니다.

또한 정사각형으로 채워지지 않은 부분이있을 때마다 문제를 하위 문제로 나눌 수 있습니다.

Answer 3

이 정확한 문제는 algorithmist에 있습니다.

욕심 많은 sweep line 스타일 알고리즘 알고리즘이 문제를 최적으로 해결합니다.

첫 번째 제한 조건에서 가능한 한 비 분리 영역을 최대한 처리하고 두 번째로 첫 번째 제약 조건을 사용한다고 가정하면이 알고리즘은 O (n^2) 시간 동안 문제를 해결합니다.

기본 아이디어는 위에서 아래로 순서대로 진행하고 '누드'상태 일 때만 섹션을 가져 오는 것입니다. 즉, 해당 섹션을 다루지 않았습니다. 섹션을 강요 당할 때 가장 중요한 부분을 '미래'로 간주하십시오. 이 구현은 O (n^2)이지만, Cands를 조금 더 잘 관리하면 O (n log (n))로 만들 수 있습니다.

#!/usr/bin/python 

START_EVENT, END_EVENT = 0, 1 # handle starts before ends at same point 

def max_future(cands): 
    return max(cands, key=lambda c: (c[1], c)[1]) 

def cover_max_segment_min(intervals): 
    events = [] 
    for interval in intervals: 
    events.append((interval[0], START_EVENT, interval)) 
    events.append((interval[1], END_EVENT, interval)) 
    cands = [] 
    outputs = [] 
    alive = None 
    # Handle events by 
    # event time, 
    # starts before ends, 
    # longer endings before shorter endings 
    events.sort(key=lambda x: (x[0], x[1], -x[2][1])) 
    for k, event_type, interval in events: 
    if event_type == START_EVENT: 
     cands.append(interval) 
    if event_type == END_EVENT: 
     cands.remove(interval) 
     if interval is alive: 
      alive = None 
    if not alive and cands: 
     outputs.append(max_future(cands)) 
     alive = outputs[-1] 
    return outputs 

assert cover_max_segment_min([(0, 3), (1, 4), (3, 5)]) == \ 
    [(0, 3), (3, 5)] 
assert cover_max_segment_min([(0, 3), (3, 5), (1, 4)]) == \ 
    [(0, 3), (3, 5)] 
assert cover_max_segment_min([(0, 3)]) == [(0, 3)] 
assert cover_max_segment_min([]) == [] 
assert cover_max_segment_min([(-10, 10), (1, 2), (3, 5)]) == [(-10, 10)] 
assert cover_max_segment_min([(1, 2), (2, 3), (3, 4)]) == \ 
    [(1, 2), (2, 3), (3, 4)] 
assert cover_max_segment_min([(1, 4), (1, 2), (3, 3)]) == \ 
    [(1, 4)]