Аргумент зарядки

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

Корректность

Чтобы алгоритм оптимально решил задачу максимизации прибыли, алгоритм должен выдать результат, который принесет такую ​​же прибыль, как и оптимальное решение для каждого возможного входа. Пусть | А(Я) | обозначаем прибыль от вывода алгоритма с учетом входных данных I и пусть | ОПТ(I) | обозначаем прибыль оптимального решения для I . Если инъективная функция h : OPT(I) → A(I) существует, отсюда следует, что | ОПТ(I) | ≤ | А(Я) | . Поскольку оптимальное решение приносит наибольшую достижимую прибыль, это означает, что результат, полученный алгоритмом, так же прибыльен, как и оптимальное решение, и, следовательно, алгоритм оптимален.

Правильность аргумента взимания платы для задачи минимизации затрат симметрична. Если | А(Я) | и | ОПТ(I) | обозначают стоимость результата алгоритма и оптимального решения соответственно, тогда существование инъективной функции h : A(I) → OPT(I) будет означать, что | А(Я) | ≤ | ОПТ(I) | . Поскольку оптимальное решение имеет наименьшую стоимость, а стоимость алгоритма равна стоимости оптимального решения задачи минимизации, то алгоритм также оптимально решает задачу.

Вариации

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

Примеры

Проблема интервального планирования

Основная статья: интервальное планирование

Учитывая набор из n интервалов I = {I ₁ , I ₂ , ... , I _n } , где каждый интервал I _i ∈ I имеет время начала s _i и время окончания f _i , где s _i < _fi , цель состоит в том, чтобы найти максимальное подмножество взаимно совместимых интервалов в I . Здесь два интервала I _j и I _k называются совместимыми, если они не перекрываются, в том смысле, что s _j < f _j ≤ s _k < f _k .

Рассмотрим самый ранний жадный алгоритм, описанный следующим образом:

• Начните с пустого набора интервалов.
• Отсортируйте интервалы в I по возрастанию времени окончания.
• Рассмотрим каждый интервал в I в отсортированном порядке. Добавьте интервал в набор, если он не конфликтует с интервалами, уже содержащимися в наборе. В противном случае игнорируйте интервал.

Проблему интервального планирования можно рассматривать как задачу максимизации прибыли, где прибылью является количество интервалов во взаимно совместимом подмножестве. Аргумент зарядки можно использовать, чтобы показать, что алгоритм самого раннего времени окончания является оптимальным для задачи планирования интервалов.

Учитывая набор интервалов I = {I ₁ , I ₂ , ... , I _n } , пусть OPT(I) будет любым оптимальным решением проблемы планирования интервалов, и пусть EFT(I) будет решением самого раннего завершения временной алгоритм. Для любого интервала J € OPT(I) определите h(J) как интервал J' € EFT(I) , который пересекает J с самым ранним временем окончания среди всех интервалов в EFT(I) пересекающих J. , Чтобы показать, что алгоритм самого раннего времени окончания является оптимальным с использованием аргумента зарядки, необходимо показать, что h представляет собой взаимно однозначное отображение интервалов функции в OPT(I) с интервалами в EFT(I) . Предположим, J — произвольный интервал в OPT(I) .

Покажите, что h — функция, отображающая OPT(I) в EFT(I) .

Предположим от противного, что не существует интервала J' ∈ EFT(I), удовлетворяющего h(J) = J' . По определению h это означает, что ни один интервал в (I) не пересекается с J. EFT Однако это также означало бы, что J совместим с каждым интервалом в EFT(I) , и поэтому алгоритм самого раннего времени завершения добавил бы J в EFT(I) , и поэтому J ∈ EFT(I) . Возникает противоречие, поскольку J предполагалось, что не пересекается ни с одним интервалом в EFT(I) , однако J находится в EFT(I) и J пересекается сам с собой. Таким образом, от противного, J должен пересекаться хотя бы с одним интервалом в EFT(I) .

Осталось показать, что h(J) единственен. Согласно определению совместимости, никогда не может быть так, чтобы два совместимых интервала имели одинаковое время окончания. Поскольку все интервалы в EFT(I) взаимно совместимы, ни один из этих интервалов не имеет одинакового времени окончания. В частности, каждый интервал в EFT(I) , пересекающийся с J, имеет разное время окончания, и поэтому h(J) уникален.

Докажите, что h взаимно однозначно.

Предположим от противного, что h не инъективен. есть два различных интервала Тогда в OPT(I) , J ₁ и J ₂ , такие, что h отображает как J ₁ , так и J ₂ в один и тот же интервал J' ∈ EFT(I) . Без ограничения общности предположим, что f ₁ < f ₂ . Интервалы J ₁ и J ₂ не могут пересекаться, поскольку они оба находятся в оптимальном решении, и поэтому f ₁ ≤ s ₂ < f ₂ . Поскольку EFT(I) содержит J' вместо J ₁ , самый ранний алгоритм завершения встретил J' раньше J ₁ . Таким образом, f' ≤ f ₁ . Однако это означает, что f' ≤ f ₁ ≤ s ₂ < f ₂ , поэтому J' и J ₂ не пересекаются. Это противоречие, поскольку h не может отобразить J ₂ в J', если они не пересекаются. Таким образом, от противного, h инъективен.

Следовательно, h — это функция, взаимно однозначно отображающая интервалы в OPT(I) в интервалы в EFT(I) . Согласно аргументу о зарядке, оптимальным является алгоритм самого раннего времени завершения.

Проблема планирования интервалов заданий

Рассмотрим задачу интервального планирования заданий, NP-сложный вариант рассмотренной ранее задачи интервального планирования. Как и раньше, цель состоит в том, чтобы найти максимальное подмножество взаимно совместимых интервалов в заданном наборе из n интервалов, I = {I ₁ , I ₂ , ... , I _n } . Каждый интервал I _i ∈ I имеет время начала s _i , время окончания fi _и класс работы c _i . Здесь два интервала I _j и I _k называются совместимыми, если они не перекрываются и относятся к разным классам.

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

Пусть OPT(I) и EFT(I) обозначают оптимальное решение и решение, полученное с помощью алгоритма с самым ранним временем завершения, как было определено ранее. Для любого интервала J ∈ OPT(I) определите h следующим образом:

$h(J)={\begin{cases}{\mbox{the interval in EFT(I) with the same job class as J, if one exists}}\\{\mbox{the interval with the earliest finishing time amongst all intervals in EFT(I) intersecting J, otherwise}}\end{cases}}$

Чтобы показать, что алгоритм самого раннего времени завершения является алгоритмом 2-аппроксимации, использующим аргумент зарядки, h необходимо показать, что представляет собой функцию два-к-одному, отображающую интервалы в OPT(I) на интервалы в EFT(I) . Предположим, J — произвольный интервал в OPT(I) .

Покажите, что h — функция, отображающая OPT(I) в EFT(I) .

есть некоторый интервал Во-первых, обратите внимание, что либо в EFT(I) с тем же классом заданий, что и J , либо его нет.

Случай 1. Предположим, что некоторый интервал в EFT(I) имеет тот же класс заданий, что и J .

есть интервал Если в EFT(I) того же класса, что и J , то J будет отображаться в этот интервал. Поскольку интервалы в EFT(I) взаимно совместимы, каждый интервал в EFT(I) должен иметь другой класс задания. Таким образом, такой интервал уникален.

Случай 2. нет интервалов Предположим, что в EFT(I) с тем же классом работ, что и J .

нет интервалов Если в EFT(I) того же класса, что и J , то h отображает J в интервал с самым ранним временем окончания среди всех интервалов в EFT(I), J. пересекающих Доказательство существования и единственности такого интервала дано в предыдущем примере.

Докажите, что h равно два к одному.

Предположим от противного, что h не является отношением два к одному. существуют три различных интервала Тогда в OPT(I) , J ₁ , J ₂ и J ₃ , такие что h отображает каждый из J ₁ , J ₂ и J ₃ в один и тот же интервал J' ∈ EFT(I) . По принципу «ячейки» по крайней мере два из трех интервалов были сопоставлены с J', потому что они имеют тот же класс работы, что и J ', или потому, что J ' — это интервал с самым ранним временем окончания среди всех интервалов в EFT(I), пересекающих оба интервалы. Без ограничения общности предположим, что этими двумя интервалами являются J ₁ и J ₂ .

Случай 1. Предположим, J ₁ и J ₂ были сопоставлены с J ', поскольку они имеют тот же класс работы, что и J '.

Тогда каждый J ', J1 _и и J2 _{имеют один} тот же класс работы. Это противоречие, поскольку интервалы в оптимальном решении должны быть совместимыми, а J ₁ и J ₂ — нет.

Случай 2. Предположим, J ' — это интервал с самым ранним временем окончания среди всех интервалов в EFT(I), пересекающих как J ₁ , так и J ₂ .

Доказательство этого случая эквивалентно доказательству в предыдущем примере, показывающем инъективность. Из приведенного выше доказательства следует противоречие.

Следовательно, h отображает не более двух различных интервалов в OPT(I) в один и тот же интервал в EFT(I) и поэтому h равен два к одному. Согласно аргументу взимания платы, самый ранний алгоритм времени завершения представляет собой алгоритм двух приближений для задачи планирования интервалов заданий.

Ссылки

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001.
• Санджой Дасгупта , Христос Пападимитриу и Умеш Вазирани . Алгоритмы , первое издание. МакГроу-Хилл. 2006.
• Allan Borodin [PDF document]. http://www.cs.toronto.edu/~bor/373s11/L2.pdf
• Allan Borodin [PDF document]. http://www.cs.toronto.edu/~bor/373f11/L5-373f11-short.pdf
• Allan Borodin [PDF document]. http://www.cs.toronto.edu/~bor/373s13/L3-actual.pdf