Разработка алгоритма
Алгоритмы с псевдополиномиальной зависимостью от значений часто могут использоваться для разработки схем аппроксимации с полиномиальным временем, и разработанный нами алгоритм очень наглядно демонстрирует эту базовую стра- тегию. В частности, мы используем алгоритм динамического программирования с временем выполнения O(n2v*) для разработки схемы аппроксимации с полино- миальным временем: если значения являются малыми целыми числами, то значе- ние v* мало, а задача уже может быть решена за полиномиальное время. С другой стороны, если значения велики, то нам не обязательно работать с ними в точном виде, так как нас интересует только аппроксимированно-оптимальное решение. Мы используем параметр округления b (значение которого будет задано позднее) и будем рассматривать значения, округленные до целого, кратного b.
Алгоритм динамического программирования будет использоваться для решения задачи с округленными значениями. А точнее, для каждого элемента ∕ за его округленное значение принимается К К Обратите внимание: округленное и исходное значения достаточно близки друг к другу.(11.34) Для каждого элемента выполняется v, < V, < v. + b.
Что нам дает округление? Если значения были изначально большими, то мень- ше они не станут. Однако все округленные значения представляют собой целые числа, кратные общему параметру b, поэтому вместо решения задачи с округлен- ными значениями v можно сменить «единицы измерения»; мы разделим все зна- чения на b и получим эквивалентную задачу Пусть v7∙ = vi ∕ b = [v. ∕ fe| для i = 1,..., п.
(11.35) Задача о рюкзаке со значениями и масштабированная версия задачи
■ч 0
со значениями имеют одинаковое множество оптимальных решении, оптималь- ные решения отличаются точно множителем b, а масштабированные значения являются целочисленными.
Теперь все готово к представлению аппроксимирующего алгоритма. Будем счи- тать, что все элементы имеют вес, не превышающий W (так как элементы с весом w > W заведомо не входят в решение и поэтому могут быть удалены). Также для простоты будем считать, что е-1 является целым числом.
Knapsack-Approx(e).·
Пусть b = (е/(2w)) mахлт
Решить задачу о рюкзаке со значениями ⅜ (эквивалентно V, ). Вернуть множество S найденных элементов
Еще по теме Разработка алгоритма:
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
- Разработка Плана
- 2.7. Разработка анкеты
- 6. Разработка перспектив
- Разработка и принятие Основного закона
- Состояние научной разработки проблемы.
- Правило разработки веера версий
- Правило разработки графических схем
- Правило разработки графических схем
- Правило разработки веера версий