Нахождение минимального покрытия интервала с подинтервалами

Question

Предположим, у меня есть интервал (a, b) и несколько подинтервалов {(a _i , b _i )} _i , объединение все (а, б). Есть ли эффективный способ выбрать подмножество минимальной мощности этих подинтервалов, которое все еще охватывает (a, b)?

Answer 1

Жадный алгоритм, начинающийся с a или b, всегда дает оптимальное решение.

Доказательство: рассмотрим множество S _a всех подинтервалов, охватывающих a. Понятно, что один из них должен принадлежать к оптимальному решению. Если мы заменим его подинтервалом (a _max , b _max ) из S _a , правая конечная точка которого b _max максимальна в S _a (достигает крайнего правого края), оставшийся непокрытый интервал (b _max , b) будет подмножеством оставшегося интервала из оптимального решения, поэтому он может быть покрыт не больше субинтервалов, чем аналогичный непокрытый интервал из оптимального решения. Следовательно, решение, построенное из (a _max , b _max ) и оптимального решения для оставшегося интервала (b _max , b), также будет оптимальным.

Итак, просто начните с a и итеративно выбирайте интервал, доходящий до крайнего правого края (и закрывающий конец предыдущего интервала), повторяйте, пока не нажмете b. Я считаю, что выбор следующего интервала может быть сделан в log (n), если вы сохраняете интервалы в расширенном дереве интервалов.

Answer 2

Звучит как динамическое программирование.

Вот иллюстрация алгоритма (предположим, интервалы в списке отсортированы по времени окончания):

//works backwards from the end
int minCard(int current, int must_end_after)
{
    if (current < 0)
        if (must_end_after == 0)
            return 0; //no more intervals needed
        else
            return infinity; //doesn't cover (a,b)

    if (intervals[current].end < must_end_after)
        return infinity; //doesn't cover (a,b)

    return min( 1 + minCard(current - 1, intervals[current].start),
                minCard(current - 1, must_end_after) );
           //include current interval or not?
}

Но это также должно включать кэширование (запоминание).

Answer 3

Есть два случая для рассмотрения: Случай 1: нет интервалов перекрытия по истечении времени окончания интервала. В этом случае выберите следующий интервал с наименьшим временем начала и наибольшим временем окончания. (амин, бмакс). Случай 2: существует 1 или более перекрывающихся интервалов с последним просматриваемым интервалом. В этом случае время начала не имеет значения, потому что вы уже рассмотрели это. Так что оптимизируйте время финиша. (a, bmax).

Случай 1 всегда выбирает первый интервал в качестве первого интервала и в оптимальном наборе (доказательство совпадает с тем, что предоставил @RafalDowgrid).

Answer 4

Вы имеете в виду, что подинтервалы все еще перекрываются таким образом, что (a, b) остается полностью покрытым во всех точках?

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

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

Нашел ссылку на журнал, но не смог ее прочитать. (

Это будет проблема с ударным набором и вообще NP_hard.
Не могу прочитать это , но выглядит как проблема противоположного типа.
Не могу прочитать, но есть другая ссылка , в которой упоминаются интервалы разделения.
Здесь является доступной ссылкой на рандомизированные алгоритмы для задач геометрической оптимизации.
Страница 35 этого PDF-файла имеет жадный алгоритм.
Страница 11 из Karp (1972) упоминает ударный набор и часто упоминается.
Google результат . Исследование было забавным, но мне нужно идти.