Задача
На какую точность аппроксимации можно рассчитывать? Наш алгоритм по- лучает на входе веса и значения, определяющие задачу, а также дополнительный параметр е (требуемая точность). Он находит подмножество S, суммарный вес которого не превышает W, с суммарным значением , уступающим макси-
мально возможному не более чем на (1 + е). Алгоритм выполняется за полино- миальное время для любого фиксированного выбора е > 0; при этом зависимость от е не является полиномиальной. Назовем этот алгоритм схемой аппроксимации с полиномиальным временем.
Возникает вопрос: возможно ли, чтобы такой сильный аппроксимирующий алгоритм выполнялся за полиномиальное время, когда задача о рюкзаке является NP-сложной? Ведь с целочисленными значениями при достаточном приближе- нии к оптимальному значению мы должны достичь самого оптимума! Загвоздка кроется в неполиномиальной зависимости от желаемой точности: для любого фиксированного выбора е — например, е = 0,5, е = 0,2 или даже е = 0,01 — алгоритм выполняется за полиномиальное время, но при замене е все меньшими и мень- шими значениями время выполнения возрастает. К тому времени, когда е станет достаточно малым для гарантированного достижения оптимума, алгоритм уже не будет алгоритмом с полиномиальным временем.
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача
- 3. Задачи и функции социологии
- Основные задачи МПП.
- Задачи и упражнения