Алгоритм максимального охвата, минимизации использования товара?

Question

У меня есть сценарий, который вы можете представить таким образом:

Начните с изображения шириной 100 пикселей и высотой 1000 пикселей. В дополнение к этому изображению у вас есть набор обрезанных участков этого изображения. Каждый раздел имеет ширину 100 пикселей и высоту 100 пикселей. Часть изображения, содержащаяся в разделе, варьируется. Например, у вас может быть тот, который начинается в самом верху (пиксель 0), затем один в вертикальном пикселе 3, затем один в вертикальном пикселе 9 и т. Д.

Что мне нужно сделать, так это найти способ взглянуть на этот набор небольших картинок и выбрать наименьшее количество секций, которые обеспечили бы мне наибольшее покрытие исходного изображения.

Пара заметок:

1. Содержание изображения на самом деле не имеет значения. Это действительно соответствует координатам, которые имеют значение.
2. При восстановлении на изображении никогда не будет пробелов, но может не хватить частей для достижения дна.
3. Будет много совпадений между разделами. Фактически, будут случаи, когда между двумя секциями будет разность (по вертикали) только в один или два пикселя.

Кто-нибудь может указать мне правильное направление здесь? Я могу сделать такую ​​грубую силу ... но я предполагаю, что есть лучший способ.

Answer 1

Извините, но я не понимаю, почему эта проблема NP-сложная.

Общая идея состоит в том, что вы итеративно удаляете нижние части изображения, выбирая «лучший» раздел,

• Самый большой раздел, который покрывает нижнюю часть изображения
• Если вы не можете найти один (потому что ни один раздел не покрывает последнюю строку пикселей), просто возьмите тот, который ближе всего кbottom.
• Сполосните и повторите

Начните с сортировки разделов.Вы получите что-то вроде (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 (вы удалили часть нижней части исходного изображения) (конечно, удалите из отсортированного списка все разделы, которыеare "> = n")

Я думаю, что установка секций фиксированной высоты (100 пикселей) снимает 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

Эта точная проблема рассматривается алгоритмистом .

Алгоритм алгоритма в стиле строчной линии решит вашу проблему оптимально.

Предполагая, что выЕсли вы хотите сначала охватить как можно больше непересекающихся областей, а затем использовать наименьшее число разделов с учетом первого ограничения, тогда этот алгоритм решит проблему за O (n ^ 2) раз.

Основная идея состоит в том, чтобы идти по порядку сверху вниз и брать раздел только тогда, когда вы «обнажены», то есть не охватывали данный раздел.Когда вы вынуждены занять раздел, выберите тот, который больше всего вас охватит, в «будущее».Эта реализация O (n ^ 2), но вы можете сделать это O (n log (n)), немного улучшив управление Cands.

#!/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)]