覆盖率最大化，最小化项目使用率的算法？

Question

我有一个你可以这样设想的场景：

从100像素宽×1000像素高的图像开始。 除了该图像之外，还有一组该图像的裁剪部分。每个部分宽100像素，高100像素。该部分包含的图像部分不同。例如，您可能有一个从顶部开始（像素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，...，888898，），则n = 898

然后再以N开始= N （你已经删除了原始图像底部的一部分）（当然，从排序列表中删除“> = n”的所有部分）

我认为设置固定高度部分（100 pi xels）去除NP-硬度。

Answer 2

我认为这是http://en.wikipedia.org/wiki/Maximum_coverage_problem - 这些集合的元素是像素（您可以编写代码，使它不会逐像素地处理事物）。

因为它是100x1000，问题不再是NP-hard，可能在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），但是可以通过更好地管理cand来使其成为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)]