Анализ алгоритма


Вспомните одномерную последовательность ячеек для задачи взвешенного ин- тервального планирования на рис.
6.5, где был представлен способ итеративного заполнения массива M для этого алгоритма. Для только что разработанного ал- горитма можно использовать аналогичное представление, но на этот раз понадо- бится двумерная таблица, отражающая двумерный массив подзадач. На рис. 6.11 изображено построение подзадач в этой ситуации: значение M[i, w] вычисляется по двум другим значениям M[i - 1, w] и M[i - 1, w - w].

В качестве примера выполнения этого алгоритма рассмотрим экземпляр с пре- дельным весом W = 6 и n = 3 элементами с размерами w1 = w2 = 2 и w3 = 3. Опти- мальное значение OPT(3, 6) = 5 достигается при использовании третьего элемента и одного из первых двух элементов. На рис. 6.12 продемонстрирован процесс заполнения алгоритмом двумерной таблицы значениями OPT строка за строкой.

Следующий вопрос — время выполнения алгоритма. Как и прежде в зада- че взвешенного интервального планирования, мы строим таблицу решений M
и вычисляем каждое из значений M[i, w] за время 0(1) с использованием преды- дущих значений. Следовательно, время выполнения пропорционально количеству элементов в таблице.

Рис. 6.12. Итерации алгоритма для простого экземпляра задачи о сумме подмножеств


(6.9) Алгоритм Subset-Sum(n, W) правильно вычисляет оптимальное значение для задачи и выполняется за время 0(nW).

Обратите внимание: этот метод менее эффективен, чем динамическая про- грамма для задачи взвешенного интервального планирования. В самом деле, его время выполнения не является полиномиальной функцией n; это полиномиальная функция n и W — наибольшего целого, задействованного в определении задачи. Такие алгоритмы называются псевдополиномиальными. Псевдополиномиальные алгоритмы могут обладать неплохой эффективностью при достаточно малых числах {wi} во входных данных; с увеличением этих чисел их практическая при- менимость снижается.

Чтобы получить оптимальное множество элементов S, можно выполнить обрат- ное отслеживание по массиву M по аналогии с тем, как это делалось в предыдущих разделах:

(6.10) Для таблицы M оптимальных значений подзадач оптимальное множе- ство S может быть найдено за время 0(n).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.