Аргумент зарядки
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Правильность

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

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

Вариации

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

Примеры

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

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

Для набора из n интервалов I = {I 1 , I 2 , ..., I n } , где каждый интервал I i ∈ I имеет время начала s i и время окончания f i , где s i <f i , цель состоит в том, чтобы найти максимальное подмножество взаимно совместимых интервалов в I . Здесь два интервала I j и I k называются совместимыми, если они не перекрываются, в том смысле, что s j <f j ≤ s k<f k .

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

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

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

Для данного набора интервалов I = {I 1 , I 2 , ..., I n } пусть OPT (I) будет любым оптимальным решением задачи интервального планирования, а EFT (I) будет решением самого раннего завершения временной алгоритм. Для любого интервала J ∈ OPT (I) , определим ч (J) , в качестве интервала J»∈ ТРИТОН (I) , которая пересекает J с самым ранним временем отделочного среди всех интервалов в EFT (I) , пересекающей J . Чтобы показать, что алгоритм самого раннего времени окончания является оптимальным, используя аргумент зарядки, hдолжно быть показано, что это функция взаимно однозначного отображения интервалов в OPT (I) в интервалы в EFT (I) . Предположим, что J - произвольный интервал в OPT (I) .

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

Предположим от противного, что не существует интервала J '∈ EFT (I), удовлетворяющего h (J) = J' . По определению ч , это означает , что ни один из интервалов в EFT (I) пересекается с J . Однако это также означало бы, что 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 1 и J 2 , такие, что h отображает J 1 и J 2 в один и тот же интервал J '∈ EFT (I) . Без ограничения общности предположим, что f 1 <f 2 . Интервалы J 1 и J 2 не могут пересекаться, потому что оба они находятся в оптимальном решении, и поэтому f 1 ≤ s 2 <f 2 . Поскольку EFT (I)содержит J ' вместо J 1 , самый ранний алгоритм времени окончания, обнаруженный J' перед J 1 . Таким образом, f '≤ f 1 . Однако это означает, что f '≤ f 1 ≤ s 2 <f 2 , поэтому J' и J 2 не пересекаются. Противоречие, потому что h не может отобразить J 2 в J ', если они не пересекаются. Таким образом, от противного, h инъективен.

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

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

Рассмотрим задачу интервального планирования заданий, NP-сложный вариант задачи интервального планирования, о которой мы говорили ранее. Как и раньше, цель состоит в том, чтобы найти максимальное подмножество взаимно совместимых интервалов в заданном наборе из n интервалов, I = {I 1 , I 2 , ..., I n } . Каждый интервал I i ∈ I имеет время начала s i , время окончания f i и класс работы c i . Здесь два интервала I j и I k считаются совместимыми, если они не пересекаются и имеют разные классы.

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

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

Чтобы показать, что алгоритм самого раннего времени окончания является алгоритмом 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 , то ч отображает J на интервал с самым ранним временем отделочного среди всех интервалов в EFT (I) , пересекающая J . Доказательство существования и единственности такого интервала приведено в предыдущем примере.

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

Предположим от противного, что h не два к одному. Тогда есть три различных интервала в OPT (I) , J 1 , J 2 и J 3 , такие, что h отображает каждый из J 1 , J 2 и J 3 в один и тот же интервал J '∈ EFT (I) . По принципу "голубятни" по крайней мере два из трех интервалов были сопоставлены с J ', потому что они имеют тот же класс работы, что и J ', или потому что J'- это интервал с самым ранним временем окончания среди всех интервалов в EFT (I), пересекающих оба интервала. Без ограничения общности предположим, что эти два интервала - это J 1 и J 2 .
Случай 1. Предположим, что J 1 и J 2 отображены в J ', потому что они имеют тот же класс работы, что и J '.
Тогда каждый J ', J 1 и J 2 имеют один и тот же класс работы. Получили противоречие, поскольку интервалы в оптимальном решении должны быть совместимыми, а J 1 и J 2 - нет.
Случай 2. Предположим, что J '- это интервал с самым ранним временем окончания среди всех интервалов в EFT (I), пересекающих как J 1, так и J 2 .
Доказательство этого случая эквивалентно доказательству предыдущего примера, показавшего инъективность. Противоречие следует из приведенного выше доказательства.

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

использованная литература

Источник « https://en.wikipedia.org/w/index.php?title=Charging_argument&oldid=973893362 »
Contribute a better translation