Доказательство оптимальности жадного решения для последовательности работы

Question

В этом Job Sequencing Problem, как мы докажем, что решение, которое жадный подход обеспечит, является оптимальным?

Кроме того, я также не в состоянии выяснить (п) решения O как автор позже утверждает

Он может быть оптимизирован почти O (N) с помощью накидной-структуры данных.

Answer 1

Оптимальность жадного решения можно увидеть аргументом обмена следующим образом. Без ограничения общности предположим, что все прибыли различны и что рабочие места сортируются в убывающем порядке прибыли.

Исправить решение S. Из этого решения удалите все задания, которые не соответствуют установленному сроку. Как и в случае с этим преобразованием, каждое задание заканчивается в течение его крайнего срока, результирующее решение S1 по-прежнему является оптимальным. Для работы i рассмотрим интервал I_i:=[0,min(n,deadline(i))] (как в жадном алгоритме). В этом интервале, справа от работы i, есть только рабочие места с большим временем обработки (если нет, они либо были бы рассмотрены ранее нашим заказом, либо они могли бы быть обменены без нарушения их сроков). Разместить вакансию i в крайнее правое положение возможно в I_i.

В целом, мы имеем следующее утверждение.

Каждое решение S может быть преобразовано в решение S' со следующими propoerties.

1. S' содержит каждую работу S которая завершается до его срока.
2. За все вакансии i в S все вакансии после i в I_i имеют увеличенное время обработки.
3. Для каждого задания i в S, нет времени на простоя после i в I_i.
4. S' имеет такое же объективное значение, что и S.

В частности, существует оптимальное решение S* со свойствами выше. Пусть S - алгоритм, генерируемый жадным алгоритмом. Обратите внимание, что S также имеет свойства 2 и 3 выше. Пусть i будет первым заданием, которое встречается в S, но не в S*. Пусть pos будет временным интервалом i в S. Если pos был пуст в S*, S* можно было бы улучшить, добавив i, что противоречит оптимальности S*. Если pos был не пустым в S*, работа i' в pos в S* не может быть большей прибыли, чем i, так как в противном случае жадный алгоритм выбрал бы i' быть в pos в S. Следовательно, он должен иметь меньшую прибыль, чем i. Это означает, что его можно удалить и заменить на i в S*, что также противоречит оптимальности S*.

Answer 2

Рассмотрите работу, стоящую на 2 очка с предельным сроком 4, и три задания на 1 очко каждый, с предельным сроком 3. Это опровергает оптимальность «жадного» алгоритма: выгоднее сначала выполнить три более дешевых задания , до более дорогой.

Что касается O (n^2) по сравнению с O (n), я думаю, что оба утверждения неверны. «Жадный» алгоритм, как описано, состоит из сортировки заданий - O (nlogn) - плюс одно сканирование отсортированного списка, заполнение слотов последовательности решений - O (n) - и для этого O (nlogn).

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

Answer 3

1. Подтверждение правильности. Предположим, что это неверно. Что это значит? Это означает, что на каком-то этапе мы выбрали задание, потому что его невозможно было добавить, не удалив уже взятый. Если бы мы удалили уже взятый и поставили текущий в свой временной интервал, мы бы ничего не изменили для следующих заданий (набор занятых временных интервалов был бы таким же). Но общая прибыль уменьшилась бы. Таким образом, решение, созданное этим алгоритмом, является оптимальным.

2. Изготовление его быстрее, чем O(n^2). Для этого нам нужно быстро найти крайнее правое положение слева от данного. Если мы используем структуру union-find для поддержания группы занятой позиции, мы можем просто найти группу, в которой находится крайний срок текущего задания, и элемент принятия, расположенный слева от него. Но все равно O(n log n) из-за сортировки.