<<
>>

Задача

В этом разделе рассматривается NP-полная задача, для которой возможно построе- ние алгоритма с полиномиальным временем, обеспечивающим очень сильную ап- проксимацию. Мы рассмотрим слегка обобщенную версию задачи о рюкзаке (или задачи о сумме подмножеств).
Допустим, имеется n предметов, которые нужно уложить в рюкзак. Каждый предмет i = 1, ..., n обладает двумя целочисленными параметрами: весом w. и значением v. Для заданной емкости рюкзака Wтребуется найти подмножество S предметов, обладающее максимальным значением, при ус- ловии, что общий вес подмножества не превышает W. Другими словами, требуется максимизировать при условии ∑зн

На какую точность аппроксимации можно рассчитывать? Наш алгоритм по- лучает на входе веса и значения, определяющие задачу, а также дополнительный параметр е (требуемая точность). Он находит подмножество S, суммарный вес которого не превышает W, с суммарным значением , уступающим макси-

мально возможному не более чем на (1 + е). Алгоритм выполняется за полино- миальное время для любого фиксированного выбора е > 0; при этом зависимость от е не является полиномиальной. Назовем этот алгоритм схемой аппроксимации с полиномиальным временем.

Возникает вопрос: возможно ли, чтобы такой сильный аппроксимирующий алгоритм выполнялся за полиномиальное время, когда задача о рюкзаке является NP-сложной? Ведь с целочисленными значениями при достаточном приближе- нии к оптимальному значению мы должны достичь самого оптимума! Загвоздка кроется в неполиномиальной зависимости от желаемой точности: для любого фиксированного выбора е — например, е = 0,5, е = 0,2 или даже е = 0,01 — алгоритм выполняется за полиномиальное время, но при замене е все меньшими и мень- шими значениями время выполнения возрастает. К тому времени, когда е станет достаточно малым для гарантированного достижения оптимума, алгоритм уже не будет алгоритмом с полиномиальным временем.

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

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.
  17. Задачи и упражнения