Показать меню

APX

02.12.2020
33

APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом аппроксимации. В более простых терминах, задачи этого класса имеют эффективные алгоритмы, находящие решения, которые хуже оптимального не более чем на фиксированный процент. Например, существует алгоритм полиномиальной сложности для решения задачи об упаковке в контейнеры, который использует не более чем на 5 % больше контейнеров, чем наименьшее необходимое их число.

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

Константа c называется коэффициентом аппроксимации. В зависимости от того, является ли проблема проблемой максимизации или минимизации, решение может быть в c раз больше или в c раз меньше оптимального.

К примеру, и задача о вершинном покрытии, и задача коммивояжёра с неравенством треугольника имеют простые алгоритмы, для которых c = 2. С другой стороны, доказано, что задачу коммивояжёра с произвольными длинами рёбер (не обязательно удовлетворяющими неравенству треугольника) нельзя аппроксимировать с постоянным коэффициентом, поскольку задачу поиска гамильтонова пути нельзя решить за полиномиальное время (в случае, если P ≠ NP).

Если существует алгоритм решения задачи за полиномиальное время для любого фиксированного коэффициента большего единицы (один алгоритм для любого коэффициента), говорят, что задача имеет полиномиальную по времени схему аппроксимации (PTAS). Если P ≠ NP, можно показать, что существуют задачи, входящие в класс APX, но не в PTAS, то есть задачи, которые можно аппроксимировать с некоторым коэффициентом, но не с любым коэффициентом.

Задача называется APX-трудной, если любая задача из класса APX имеет сведение к этой задаче, и APX-полной, если задача APX-трудна и сама принадлежит к классу APX. Из неравенства P ≠ NP следует, что PTASAPX, P ≠ NP, а отсюда никакая APX-трудная задача не принадлежит PTAS.

Если задача APX-трудна, это обычно плохо, поскольку при P ≠ NP это означает отсутствие PTAS-алгоритма, который является наиболее полезным видом аппроксимационного алгоритма. Одна из наиболее простых APX-полных задач — это задача максимальной выполнимости булевых формул, вариант задачи выполнимости булевых формул. В этой задаче мы имеем булеву формулу в конъюнктивной нормальной форме, и хотим получить максимальное число подвыражений, которые будут выполняться при единственной подстановке значений true/false в переменные. Несмотря на то, что, скорее всего, задача не принадлежит PTAS, верное значение может быть получено с точностью 30 %, а некоторые упрощённые варианты задачи имеют PTAS.

Примеры

  • Алгоритм Кристофидеса
Еще по этой теме:
Квадратное треугольное число
05:27, 02 декабрь
Квадратное треугольное число
В теории чисел квадратным треугольным числом (или треугольным квадратным числом) называется число, являющееся как треугольным, так и квадратным. Существует бесконечное число квадратных треугольных
Производители сельскохозяйственных товаров Тверского региона получат больше одного миллиарда четырёхсот миллионов рублей на субсидирование займов
19:38, 27 февраль
Производители сельскохозяйственных товаров Тверского региона получат больше одного миллиарда четырёхсот миллионов рублей на субсидирование займов
В ходе заседания сотрудников органов исполнительной власти Тверского региона, которое состоялось двадцать первого февраля нынешнего года под руководством главы области Игоря Рудени, большое
Метод группового учёта аргументов (часть 1)
14:33, 13 март
Метод группового учёта аргументов (часть 1)
Будучи мощным инструментом аппроксимации, искусственные нейронные сети, однако, имеют недостаток во встроенном математическом аппарате, не позволяющем ограничивать количество входных параметров или
Пластическая деформация и вязкое течение тела (часть 2)
14:23, 13 март
Пластическая деформация и вязкое течение тела (часть 2)
Кроме величин μ и η в литературе встречается коэффициент пропорциональности (φ (фи), по своему значению он обратно пропорционален вышеупомянутым величинам и называется коэффициентом
Представление в виде функциональной поверхности (часть 2)
14:15, 13 март
Представление в виде функциональной поверхности (часть 2)
Различные методы интерполяции почти всегда будут давать различные результаты. Все методы интерполяции можно разбить на два класса: точные интерполяторы и сглаживающие интерполяторы. Некоторые
Экологическая оценка состояния почв (часть 1)
20:55, 23 октябрь
Экологическая оценка состояния почв (часть 1)
Количественная оценка состояния экосистемы и ее компонентов представляет собой одну из важнейших как в теоретическом, так и в практическом планах задач экологии, находящуюся пока во многом на уровне
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent