В этой задаче определения последовательности заданий, как мы докажем что решение, которое дает жадный подход, является оптимальным?
Более того, я также не могу понять решение O (n), как позже утверждает автор.
Его можно оптимизировать почти до O (n), используя структуру данных union-find.
Оптимальность жадного решения можно увидеть с помощью обменного аргумента следующим образом. Без ограничения общности предположим, что все прибыли различны и что рабочие места отсортированы в порядке убывания прибыли.
Исправьте решение S. Из этого решения удалите все задания, которые не соответствуют сроку. Поскольку при таком преобразовании каждое задание завершается в установленный срок, результирующее решение S1 по-прежнему остается оптимальным. Для задания i рассмотрим интервал I_i:=[0,min(n,deadline(i))] (как в жадном алгоритме). В этом промежутке справа от задания i находятся только задания с большим сроком выполнения (в противном случае они либо были бы рассмотрены ранее нашим заказом, либо могли быть обменены без нарушения их сроков). Поместите задание i в крайнее правое положение в I_i.
Итого имеем следующее утверждение.
Каждое решение S может быть преобразовано в решение S' со следующими свойствами.
S' содержит все задания S, которые завершаются до истечения срока.i в S все задания после i в I_i имеют большее время обработки.i в S нет времени простоя после i в I_i.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*.
I_i означает интервал от нуля до крайнего срока выполнения задания i. Под «правом» на i я имею в виду выполнение позже в каком-то решении. Предполагается, что аргумент работает следующим образом: сначала показано, что только некоторые решения являются «интересными» (а именно те, которые обладают свойствами 1–4) в том смысле, что любое решение можно изменить так, чтобы оно имело свойства 1–4, но с той же прибылью. . Это справедливо, в частности, для оптимального решения, которое затем сравнивается с решением, сгенерированным жадным алгоритмом. Я признаю, что презентация не элегантна.
- person Codor; 14.01.2015
Доказательство правильности. Предположим, что это не правильно. Что это значит? Это значит, что на каком-то шаге мы выбросили задание, потому что нельзя было добавить его, не удалив уже занятое. Если бы мы удалили уже занятое и поместили текущее в его тайм-слот, мы бы ничего не изменили для следующих заданий (набор занятых тайм-слотов был бы таким же). Но общая прибыль уменьшилась бы. Таким образом, решение, полученное по этому алгоритму, является оптимальным.
Сделать это быстрее, чем O(n ^ 2). Для этого нам нужно быстро найти крайнюю правую свободную позицию слева от заданной. Если мы используем структуру union-find для хранения группы занятых позиций, мы можем просто найти группу, в которой находится крайний срок текущей работы, и элемент взятия, расположенный слева от нее. Но все равно O(n log n) из-за сортировки.
Рассмотрим работу стоимостью 2 балла со сроком 4 и три работы по 1 баллу со сроком 3. Это опровергает оптимальность «жадного» алгоритма: выгоднее выполнить три более дешевых работы. во-первых, перед более дорогим.
Что касается O(n^2) против O(n), я думаю, что оба утверждения тоже неверны. «Жадный» алгоритм, как описано, состоит из сортировки заданий — O(nlogn) — плюс однократное сканирование отсортированного списка, заполнение слотов последовательности решений — O(n) — и поэтому составляет O(nlogn).
Чтобы сделать его линейным, нужно было бы что-то сделать с сортировкой, например, с использованием сортировки по основанию, которую можно считать линейной для практических целей.
5. Временной горизонт, по-видимому, равен [0,n], где n — количество заданий, хотя это не очень четко указано в описании проблемы. Задача требует последовательности заданий, что неявно означает, что в расписании нет времени простоя, а это означает, что в любом случае n является верхней границей длины временного горизонта.
- person Codor; 13.01.2015
Приведенное доказательство не является полным. А именно, предложение «работа, которую я занимаю в S*, не может приносить больше прибыли, чем i», не доказано и, я думаю, не может быть доказано. Во всяком случае, можно доказать, что утверждение верно, даже если работа i имеет прибыль больше или равную i''.
для полного доказательства см. http://ggn.dronacharya.info/CSEDept/Downloads/QuestionBank/Even/VI%20sem/ADA/Section-B/job-scheduling1.pdf
