Аппроксимация алгоритм - Approximation algorithm


Из Википедии, свободной энциклопедии

В информатике и исследовании операций , алгоритмы аппроксимации являются эффективными алгоритмами , которые находят приближенный решения NP-трудные задачи оптимизации с доказательными гарантиями на расстоянии возвращенного решения оптимальной. Приближенные алгоритмы естественным образом возникают в области теоретической информатики как следствие широко распространено мнение , P ≠ NP гипотезой. Согласно этой гипотезе, широкий класс задач оптимизации не может быть решен точно в полиномиальное время . Поле алгоритмов аппроксимации, поэтому, пытается понять , насколько близко можно аппроксимировать оптимальные решения таких проблем в полиномиальное время. В подавляющем большинстве случаев, гарантия таких алгоритмов является мультипликативной один , выраженный как отношение аппроксимации или аппроксимации коэффициента т.е., оптимальное решение всегда гарантировано , чтобы быть в пределах заранее заданного () множителя возвращаемого раствора. Тем не менее, существует множество алгоритмов аппроксимации , которые обеспечивают гарантию добавки на качестве возвращаемого раствора. Характерный пример алгоритма аппроксимации , который обеспечивает как классический алгоритм аппроксимации Ленстр , Shmoys и Тардос для календарного планирования на неродственных параллельных машинах .

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

Существует широкий интерес к теоретической информатике , чтобы лучше понять пределы , к которым мы можем аппроксимировать некоторые известные проблемы оптимизации. Например, один из давних открытых вопросов в области компьютерной науки , чтобы определить , существует ли алгоритм , который превосходит алгоритм 1,5 аппроксимации по Христофидес к задачам коммивояжера Metric . Желание понять сложные задачи оптимизации с точки зрения ПРИБЛИЖАЕМОСТИ мотивировано открытием удивительных математических связей и широко применяемых методов разработки алгоритмов для жестких задач оптимизации. Одним из хорошо известных примеров первая является алгоритм Goemans-Виллиэмсон для максимального Cut , который решает проблему график теоретической использованием высокой пространственной геометрии.

Вступление

Простой пример алгоритма аппроксимации один для минимального вершинного Cover задачи, где цель состоит в том, чтобы выбрать наименьшее множество вершин , таких , что каждое ребро во входном графе содержит , по меньшей мере , одну выбранную вершину. Один из способов , чтобы найти вершину крышку, чтобы повторить следующий процесс: найти непокрытый край, добавить оба свои конечные точки к крышке, и удалить все ребра , инцидентные либо вершины из графа. В любой вершины крышки входного графа должны использовать отдельную вершину , чтобы покрыть каждый край , который был рассмотрен в процессе (так как он образует соответствия ), вершина крышки производится, таким образом, не более чем в два раза больше оптимального. Другими словами, это постоянный алгоритм коэффициент аппроксимации с коэффициентом аппроксимации 2. В соответствии с недавним Уникальные игры гипотезой , этот фактор является даже лучшим возможным.

NP-трудные проблемы сильно различаются по их приближаемости; некоторые, такие как Ранцевые проблемы , может быть аппроксимирована в пределах множителя , при любом фиксированном , и , следовательно , производить решения сколь угодно близкой к оптимальной (например , семейство алгоритмов аппроксимации называется полиномиальная схема аппроксимации времени или СПТ). Другие невозможно аппроксимировать в любой постоянной или даже полинома, коэффициент , если P = NP , как и в случае максимальной Clique задачи . Таким образом, важное преимуществом изучения алгоритмов аппроксимации является мелкозернистой классификацией сложности различных NP-трудных задач за пределами одного обеспечиваемой теорией NP-полнота . Другими слова, хотя NP-полные задачи могут быть эквивалентны (при полиномиальном сокращении времени) друг с другом с точки зрения точных решений, соответствующие задачи оптимизаций ведут себя очень по- разному с точки зрения приближенных решений.

методы проектирования алгоритма

В настоящее время существует несколько установленных методами разработки алгоритмов аппроксимации. К ним относятся следующие.

  1. Жадный алгоритм
  2. Локальный поиск
  3. Перечень и динамическое программирование
  4. Решая выпуклое программирование релаксации , чтобы получить дробное решение. Тогда преобразование этого дробное решения в возможное решение по некоторому соответствующему округлению. Популярные послабления включают в себя следующее.
  5. Primal-Dual Методы
  6. Двойное Место
  7. Встраивание проблемы в некоторой метрике, а затем решить вопрос о метрике. Это также известно, как метрики вложения.
  8. Случайная выборка и использование случайности в целом в сочетании с указанными выше методами.

А Гарантии апостериорной

Хотя алгоритмы аппроксимации всегда обеспечивают априорной худшем случае гарантия а (будь то аддитивной или мультипликативной), в некоторых случаях они также предоставляют гарантию апостериорный, которая часто намного лучше. Это часто бывает для алгоритмов , которые работают с помощью решения выпуклой релаксации задачи оптимизации на данном входе. Например, существует другой алгоритм аппроксимации для минимальной Vertex Обложка , которая решает линейную релаксацию программирования , чтобы найти вершину крышку, которая не более чем в два раза превышает значение релаксации. Так как величина релаксации никогда не бывает больше , чем размер оптимальной вершины крышки, это дает другой алгоритм 2-аппроксимации. В то время как это похоже на априорной гарантию предыдущего алгоритма аппроксимации, гарантия последнего может быть намного лучше ( на самом деле , когда значение релаксации LP далеко от размера оптимальной вершины крышки).

Твердость аппроксимации

Приближенные алгоритмы как область исследований тесно связаны и проинформировано теории inapproximability где несуществование эффективных алгоритмов с определенными коэффициентами аппроксимации доказано (обусловлено широко распространенное мнением гипотез , такие как гипотеза P ≠ NP) с помощью сокращений . В случае задачи коммивояжера Metric, самый известный результат inapproximability исключает алгоритмы с коэффициентом аппроксимации меньше , чем 123/122 ≈ 1,008196 исключением случаев , когда P = NP. В сочетании со знанием о существовании алгоритма 1,5 приближения Христофидес, это говорит нам о том , что порог ПРИБЛИЖАЕМОСТИ для метрической коммивояжера (если она существует) находится где - то между 123/122 и 1.5.

Хотя результаты inapproximability были доказаны с 1970 - х годов, такие результаты были получены с помощью одноранговых средств и никакого систематического понимания не было доступно в то время. Только с 1990 года результата Feige, Голдвассер, Lovász, Сафра и Szegedy на inapproximability из независимого набора и известная теорема PCP , что современные инструменты для доказательства результатов inapproximability были обнаружены. Теорема PCP, например, показывает , что Джонсон 1974 алгоритмы аппроксимации для Max SAT , Set Cover , независимый набор и раскраски все достижения оптимального соотношения приближения, полагая P ≠ NP.

практицизм

Не все алгоритмы аппроксимации пригодны для непосредственного практического применения. Некоторые включают решения нетривиальной линейного программирования / семидефинитных релаксаций (которые сами по себе могут вызвать эллипсоид алгоритм ), сложные структуры данных, или сложные алгоритмические методы, что приводит к сложным вопросам реализации или улучшенные эксплуатационные качества времени (более точных алгоритмов) только на непрактично больших входов , Внедрение и запуск проблема времени в стороне, гарантия , предоставляемые алгоритмы аппроксимации может сами по себе не может быть достаточно сильным , чтобы оправдать их рассмотрение на практике. Несмотря на свою неспособность быть использован «из коробки» в практических приложениях, идеи и идеи позади разработки таких алгоритмов могут часто быть включены другими способами в практических алгоритмах. Таким образом, изучение даже очень дорогие алгоритмы не является полностью теоретическим стремление , поскольку они могут дать ценную информацию.

В других случаях, даже если начальные результаты имеют чисто теоретический интерес, с течением времени, с улучшенным пониманием, алгоритмы могут быть усовершенствованы , чтобы стать более практичными. Одним из таких примеров являются начальной PTAS для евклидового TSP по Санджив Арору (и независимо Joseph Mitchell ) , который имел запретительную продолжительность работы для приближения. Тем не менее, в течение года эти идеи были включены в почти линейное время алгоритм для любой константы .

гарантии производительности

Для некоторых алгоритмов аппроксимации можно доказать некоторые свойства о приближении оптимального результата. Например, ρ -аппроксимация алгоритм определяется как алгоритм , для которого было доказано , что значение / стоимость, ф ( х ), приближенного решения А ( х ) к экземпляру х не будет больше (или меньше, в зависимости от ситуации) чем в р раз значение, OPT, в оптимальном решении.

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

Аналогичным образом , гарантия исполнения , Р ( х, у ), из раствора у к экземпляру х определяется как

где F ( у ) есть значение / стоимость решения у для экземпляра х . Очевидно, что гарантия исполнения больше или равно 1 , и равно 1 , если и только если у является оптимальным решением. Если алгоритм A гарантирует возврат решений с гарантией производительности при большем г ( п ), то называется быть г ( п ) алгоритмом -аппроксимации и имеет отношение аппроксимации в г ( п ). Кроме того, проблема с г ( п алгоритма -аппроксимации) называется г ( п ) - аппроксимируемо или иметь коэффициент аппроксимации г ( п ).

Можно отметить , что для задач минимизации, две различные гарантии обеспечивают одинаковый результат и что для задач максимизации, относительная гарантия исполнения р эквивалентно гарантии производительности . В литературе, оба определения являются общими , но это ясно , какое определение используется так, для задач максимизации, так как ρ ≤ 1 , а г ≥ 1.

Абсолютная гарантия производительности некоторого приближение алгоритм А , где х относится к экземпляру проблемы, и где есть гарантия , производительность на й (т.е. ρ для задачи экземпляра х ) является:

То есть сказать , что это самая большая граница отношения аппроксимации, г , что один видит на все возможные случаи проблемы. Аналогичным образом, асимптотическое соотношение производительности является:

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

гарантии производительности
г -approx ρ -approx относительный ошибка относительный ошибка норма. относительный ошибка абс. ошибка
Максимум:
мин:

термины Эпсилон

В литературе, отношение аппроксимации для задачи максимизации (минимизации) с - е (мин: гр + е) означает , что алгоритм имеет коэффициент аппроксимации с ∓ е для любого е> 0 , но это отношение не имеет (или не может) быть показана при е = 0. примером этого является оптимальным inapproximability - неотъемлемость приближения - соотношение 7/8 + ε для выполнимых MAX-3sat случаев из - за Джоен Хастад . Как упоминалось ранее, когда с = 1, то проблема , как говорят , чтобы иметь схему аппроксимации полиномом времени .

Ε-термин может появиться , когда алгоритм аппроксимации вводит мультипликативную ошибку и постоянную ошибку в то время как минимальное оптимум случаев размера п стремится к бесконечности при п делает. В этом случае отношение приближения ск / OPT = C ∓ о (1) для некоторых констант с и к . Учитывая произвольное ε> 0, то можно выбрать достаточно большое N такое , что термин к / OPT <ε для любого п ≥ N . При каждом фиксированном е, экземпляры размера п <N может быть решена с помощью грубой силы, показав тем самым отношение аппроксимации - существование приближенных алгоритмов с гарантией - от гр ∓ е для любого ε> 0.

Смотрите также

Цитирование

Рекомендации

внешняя ссылка