Как доказать оптимальность этого жадного алгоритма?

Даны N целых чисел. Каждое из этих чисел можно увеличить или уменьшить один раз не более чем на заданное натуральное число L. Если после каждой операции какие-либо числа становятся равными, мы считаем их одним числом. Задача состоит в том, чтобы вычислить мощность минимального набора различных целых чисел.

Ограничения: N ‹= 100, L ‹= 3200, целые числа находятся в диапазоне [-32000, 32000]

Пример: N = 3, L = 10 11 21 27

1) увеличить 11 на 10 => 21 21 27
2) уменьшить 27 на 6 => 21 21 21

Ответ 1.

Алго на языке C++:

sort(v.begin(), v.end());
// the algo tries to include elements in interval of length 2 * L
int ans = 0;
int first = 0; 
for(int i = 1; i < N; ++i) {
    if(v[i] - v[first] > 2 * L) { // if we can't include i-th element 
        ans++;                    // into the current interval   
        first = i;                // the algo construct new 
    }
}
ans++;
printf("%d", ans);

Я пытаюсь понять, почему этот жадный алгоритм оптимален. Любая помощь приветствуется.


algorithm proof
person Peach    schedule 21.09.2015    source источник
comment
Разве вы не имеете в виду правильность алгоритма, а не оптимальность?   -  person Yves Daoust    schedule 21.09.2015
comment
Если вы можете доказать (отдельно), что он никогда не переоценивает и никогда не занижает, то вы доказали, что он всегда дает правильный ответ. Предлагаю начать с первого: есть ли ситуации, в которых он может завышать?   -  person j_random_hacker    schedule 21.09.2015
comment
Под оптимальной вы, возможно, имеете в виду временную сложность с точки зрения количества арифметических операций?   -  person nodakai    schedule 21.09.2015
comment
@nodakai Под оптимальным я подразумеваю, почему жадный алгоритм дает правильный ответ.   -  person Peach    schedule 21.09.2015
comment
Этот алгоритм не работает (или у вас неточное описание проблемы). Контрпример: [1, 10, 11, 2] и L=5. Оптимальный ответ — 2, но ваш алгоритм возвращает 3.   -  person Vincent van der Weele    schedule 21.09.2015
comment
@VincentvanderWeele Приведенный выше код правильно возвращает 1 ideone.com/RDANYe Все четыре целых числа можно изменить до 6 не более 5 приращений/уменьшений   -  person nodakai    schedule 21.09.2015
comment
@nodakai мой плохой, я пропустил скрытую сортировку в начале. Тогда это явно работает.   -  person Vincent van der Weele    schedule 21.09.2015

Ответы (1)


arrow_upward
2
arrow_downward

В переформулированном виде мы пытаемся покрыть набор чисел, которые появляются во входных данных, с как можно меньшим количеством интервалов кардинальности 2*L + 1. Вы можете представить, что для интервала [C - L, C + L] все числа в нем скорректированы на C.

Учитывая любой список интервалов в отсортированном порядке, мы можем индуктивно показать в k, что, учитывая только первые k интервалов, первые k жадных покрывают как минимум столько же входных данных. Базовый случай k = 0 тривиален. Индуктивно жадно покрывает следующий непокрытый входной элемент и столько, сколько может дополнительно; интервал в произвольном решении, который покрывает его следующий непокрытый входной элемент, не должен быть после жадных, поэтому произвольное решение больше не имеет покрытия.

person David Eisenstat    schedule 21.09.2015