Минимизация количества блоков, охватывающих данный набор интервалов - PullRequest
Новая
       9

Минимизация количества блоков, охватывающих данный набор интервалов

1 голос
/ 22 марта 2010

это вопрос к гуру алгоритмов: -)

Пусть S будет набором интервалов натуральных чисел, которые могут перекрываться, и b размером блока. Предположим, что для каждого интервала диапазон строго меньше, чем b.

Я хочу найти минимальный набор интервалов размером b (назовем его M), чтобы все интервалы в S содержались в интервалах M.

Тривиальный пример: 

S = {[1..4], [2..7], [3..5], [8..15], [9..13]}
b = 10
M = {[1..10], [8..18]}
// so ([1..4], [2..7], [3..5]) are inside [1..10] and ([8..15], [9..13]) are inside [8..18]

Я думаю, что жадный алгоритм может работать не всегда, поэтому, если кто-нибудь знает решение этой проблемы (или аналогичное решение, которое можно преобразовать в), это было бы здорово.

Спасибо!

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

Ответы [ 2 ]

4 голосов
/ 22 марта 2010

Алгоритм может быть следующим.

  1. a = 0
  2. curr = наименьшее число в S, то есть> a. (В нашем случае = 1. в [1..4])
  3. Добавьте интервал [curr..b] к M. (В нашем случае M = {[1..10]})
  4. a = максимальная верхняя граница в M. (В нашем случае a = 10)
  5. Перейти к 2.
3 голосов
/ 22 марта 2010

Да, жадный алгоритм оптимален. Неформально рассмотрим произвольное решение M. Мы преобразуем его в надмножество жадного решения M ', не увеличивая количество интервалов. Повторно рассмотрим крайний левый интервал I в M - M '. Пусть s - самый левый интервал в S, для которого I - самый левый интервал в M, содержащий s. Жадный алгоритм слева направо выбирает интервал I ', левый край которого выровнен с s. Во-первых, я утверждаю, что I «находится справа от I, так как I» - самый правый интервал для содержания s, а во-вторых, что M - {I} U {I '} является допустимым решением, поскольку единственные интервалы, содержащиеся в I но не я 'слева от s и, таким образом, уже содержится в некотором другом интервале. Число интервалов, которых нет в жадном растворе, уменьшается, поэтому мы в конечном итоге достигаем жадного решения.

...