Аппроксимационный алгоритм

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

    Концепция аппроксимационного алгоритма была формализована в 1972-м году в статье Гарея, Грэхэма и Ульмана, а позднее Джонсоном.

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

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

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

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

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

    NP-трудные проблемы сильно различаются по возможности аппроксимации.

    Некоторые, среди которых, например, задача об упаковке в контейнеры, могут быть аппроксимированы с любым коэффициентом, большим 1 (это семейство алгоритмов называют приближённой схемой полиномиального времени, или PTAS).

    Другие задачи невозможно аппроксимировать ни с каким постоянным коэффициентом, или даже с полиномиальным коэффициентом (если P ≠ NP), и среди таких задач находится задача о максимальной клике.

    NP-трудные задачи часто можно выразить в терминах целочисленного программирования и решить в точности за экспоненциальное время. Многие экспоненциальные алгоритмы берут своё начало из приведения к задаче линейного программирования целочисленной задачи.Не все аппроксимационные алгоритмы подходят для решения практических задач. Часто они используют в качестве подзадач ЦП/ЛП/полуопределённые задачи, сложные структуры данных или изощрённую технику программирования, что ведёт к сложности реализации.

    Некоторые аппроксимационные алгоритмы имеют неприемлемое время работы, хотя время и полиномиально (например, O(n2000)).

    Всё же изучение даже таких нереальных алгоритмов не преследует чисто теоретические цели, поскольку оно даёт возможность понять суть проблемы.

    Классический пример – начальный PTAS алгоритм для метрической задачи о коммивояжёре, принадлежащий Санджив Арора и имевший практически нереальное время работы. Однако, в течение года, Арора отточил идею до алгоритма, работающего за линейное время.

    Такие алгоритмы пригодны также для задач, в которых время работы и цена могут быть оправданы. К таким задачам относятся Вычислительная биология, Финансовая инженерия, Транспортное планирование и Управление запасами.

    Другое ограничение связано с тем, что подход годится только для задач оптимизации, но не для "чистых" задач распознавания наподобие задачи выполнимости булевых формул, хотя часто бывает, что метод вполне применим для решения оптимизационных версий тех же задач, например, для задачи максимальной выполнимости булевых формул (Max SAT).

    Невозможность аппроксимации является плодотворным полем исследований в области вычислительной сложности с тех пор, как в 1990 году Фейг (Feige), Голдвассер (Goldwasser), Ловаш (Lovasz), Сафра (Safra) и Шегеди (Szegedy) установили невозможность аппроксимации задачи нахождения максимального независимого множества вершин.

    Через год после того, как Арора (Arora) доказал теорему PCP, было доказано, что аппроксимационные алгоритмы Джонсона (Johnson) 1974-го года для задачи о выполнимости булевых формул, задачи о покрытии множества, задачи о независимом множестве и задача о хроматическом числе графа имеют оптимальный аппроксимационный коэффициент (в предположении, что P ≠ NP)

Источник: Википедия

Связанные понятия

Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется...
В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов (обычно — время), требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется сложности в худшем случае, где рассматривается максимальная сложность алгоритма по всем входным данным.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Целочисленное программирование является NP-трудной задачей. Специальный случай, 0-1 целочисленное линейное программирование, в которой переменные принимают значения 0 или 1, является одной из 21 NP-полных задач Карпа.
Обучение с ошибками (англ. Learning with errors) — это концепция машинного обучения, суть которой заключается в том, что в простые вычислительные задачи (например, системы линейных уравнений) намеренно вносится ошибка, делая их решение известными методами неосуществимым за приемлемое время.
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные . Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения...

Подробнее: Временная сложность алгоритма
Обучение с ошибками в кольце (англ. Ring learning with errors, RLWE)— это вычислительная задача, которая была сформулирована как вариант более общей задачи обучения с ошибками (с англ. LWE), с целью использовать преимущество дополнительной алгебраической структуры (т.е. кольца многочленов) из теории решеток, что дало возможность повысить и расширить возможности шифрования тех криптографических приложений, которые ранее основывались на LWE. Задача RLWE стала основой новых криптографических алгоритмов...
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи.
Метод Стронгина — метод решения одномерных задач условной липшицевой оптимизации. Позволяет находить глобально оптимальное решение в задачах с ограничениями неравенствами при условии, что целевая функция задачи и левые части неравенств удовлетворяют условию Липшица в области поиска.
Полуопределённое программирование (en: Semidefinite programming, SDP) — это подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Квадрати́чная зада́ча о назначе́ниях (КЗН, англ. Quadratic assignment problem, QAP) — одна из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций, принадлежащая категории задач размещения объектов.
Задача о размещении объектов, известная также как анализ расположения оборудования или задача k-центра, — это ветвь исследования операций и вычислительной геометрии, исследующей оптимальное расположение объектов с целью минимизировать цены перевозок с учётом таких ограничений, как размещение опасных материалов вблизи жилищ. Техника применима также к кластерному анализу.
Тео́рия алгори́тмов — наука, находящаяся на стыке математики и информатики, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов...
Многокритериальная оптимизация, или программирование (англ. Multi-objective optimization) — это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.
Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Ме́тоды Ру́нге — Ку́тты (в литературе встречаются названия: ме́тоды Ру́нге — Ку́тта или же ме́тоды Ру́нге — Кутта́) — большой класс численных методов решения задачи Коши для обыкновенных дифференциальных уравнений и их систем. Первые методы данного класса были предложены около 1900 года немецкими математиками К. Рунге и М. В. Куттой.
Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной...
Гиперэвристика (гиперэвристический алгоритм) — эвристический метод поиска, направленный на автоматизацию процесса выбора, комбинирования, обобщения или адаптации нескольких более простых эвристик (или их частей) для эффективного решения вычислительной задачи.
В математике методы проверки на простоту с помощью эллиптических кривых (англ. - Elliptic Curve Primality Proving, сокр. ЕСРР) являются одними из самых быстрых и наиболее широко используемых методов проверки на простоту . Эту идею выдвинули Шафи Гольдвассер и Джо Килиан в 1986 году; она была превращена в алгоритм А.О.Л. Аткином в том же году. Впоследствии алгоритм был несколько раз изменён и улучшен, в особенности Аткином и François Morain в 1993. Концепция использования факторизации с помощью эллиптических...

Подробнее: Тест простоты с использованием эллиптических кривых
Метод декомпозиции Данцига — Вулфа представляет собой специализированный вариант симплекс-метода.
Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из одной вершины в другую. Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом кластере (существует также модификация, когда путь должен посетить хотя бы по одной вершине в каждом...
Комбинаторный взрыв — термин, используемый для описания эффекта резкого («взрывного») роста временной сложности алгоритма при увеличении размера входных данных задачи.
Информи́рованный по́иск (также эвристический поиск, англ. informed search, heuristic search) — стратегия поиска решений в пространстве состояний, в которой используются знания, относящиеся к конкретной задаче. Информированные методы обычно обеспечивают более эффективный поиск по сравнению с неинформированными методами.
Постепенная оптимизация — это техника глобальной оптимизации, которая пытается решить трудную задачу оптимизации путём решения сначала сильно упрощённой задачи с последовательным преобразованием этой задачи, пока она не станет эквивалентна исходной трудной оптимизационной задаче.
Эвристический алгоритм (эвристика) — алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным или оптимальным, но достаточный для решения поставленной задачи. Позволяет ускорить решение задачи в тех случаях, когда точное решение не может быть найдено.
Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS) (англ. Broyden — Fletcher — Goldfarb — Shanno algorithm) — итерационный метод численной оптимизации, предназначенный для нахождения локального максимума/минимума нелинейного функционала без ограничений.
В информатике сложность аппроксимации — это область изучения вычислительной сложности поиска решений задач оптимизации, близких к оптимальным.
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться...
Ме́тод моме́нтов — метод оценки неизвестных параметров распределений в математической статистике и эконометрике, основанный на предполагаемых свойствах моментов (Пирсон, 1894 г.). Идея метода заключается в замене истинных соотношений выборочными аналогами.
В вычислительной математике вычислительная устойчивость является обычно желательным свойством численных алгоритмов.
Вероятностно приблизительно корректное обучение (ВПК обучение, англ. Probably Approximately Correct learning, (PAC learning) в теории вычислительного обучения — это схема математического анализа машинного обучения. Схему предложил в 1984 Лесли Вэлиант.
Задача о рюкзаке (или задача о ранце) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике.
Метод наименьших квадратов (МНК) — математический метод, применяемый для решения различных задач, основанный на минимизации суммы квадратов отклонений некоторых функций от искомых переменных. Он может использоваться для «решения» переопределенных систем уравнений (когда количество уравнений превышает количество неизвестных), для поиска решения в случае обычных (не переопределенных) нелинейных систем уравнений, для аппроксимации точечных значений некоторой функции. МНК является одним из базовых методов...
В обучении машин, оптимизация гиперпараметров — это задача выбора набора оптимальных гиперпараметров для обучающего алгоритма.
Критерий оптимальности (критерий оптимизации) — характерный показатель решения задачи, по значению которого оценивается оптимальность найденного решения, то есть максимальное удовлетворение поставленным требованиям. В одной задаче может быть установлено несколько критериев оптимальности.
Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии...
Макроконвейер — распределенная многопроцессорная система, обладающая программной и аппаратной поддержкой организации вычислений по макроконвейерному принципу. Этот принцип был предложен в 1978 году советским математиком В. М. Глушковым. Его суть состоит в том, что при распределении вычислительных заданий между процессорами каждому процессору на очередном шаге вычислений дается такое задание, которое может загрузить его работой на определенное время, без взаимодействия с другими процессорами. Последовательное...
Техника Бренды Бейкер — это метод построения приближенных схем полиномиального времени (ПСПВ, PTAS) для задач на планарных графах. Метод назван именем американской учёной в области информатики Бренды Бейкер, сообщившей о методе на конференции 1983 года и опубликовавшей статью в журнале Journal of the ACM в 1994.
Обобщённый ме́тод моме́нтов (ОММ; англ. GMM — Generalized Method of Moments) — метод, применяемый в математической статистике и эконометрике для оценки неизвестных параметров распределений и эконометрических моделей, являющийся обобщением классического метода моментов. Метод был предложен Хансеном в 1982 году. В отличие от классического метода моментов количество ограничений может быть больше количества оцениваемых параметров.
Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования.
По́иск в простра́нстве состоя́ний (англ. state space search) — группа математических методов, предназначенных для решения задач искусственного интеллекта.
Минимизация эмпирического риска (МЭР, англ. Empirical risk minimization, ERM) — это принцип статистической теории обучения, который определяет семейство алгоритмов обучения и который задаёт теоретические границы производительности.
Метод группового учёта аргументов (МГУА) — семейство индуктивных алгоритмов для математического моделирования мультипараметрических данных. Метод основан на рекурсивном селективном отборе моделей, на основе которых строятся более сложные модели. Точность моделирования на каждом следующем шаге рекурсии увеличивается за счет усложнения модели.
Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
Метод конечных элементов (МКЭ) — это численный метод решения дифференциальных уравнений с частными производными, а также интегральных уравнений, возникающих при решении задач прикладной физики. Метод широко используется для решения задач механики деформируемого твёрдого тела, теплообмена, гидродинамики и электродинамики.
Задача о сумме подмножеств — это важная задача в теории сложности алгоритмов и криптографии.
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я