Н.М. Новикова - Дискретные и непрерывные задачи оптимизации (1125224), страница 4
Текст из файла (страница 4)
Но П Е ХР, значит, П Е ХР по утверждению 5. С учетом произвольности П' Е ХР получили, что со-Р1Р С ХР. Обратное включение доказывается на основании очевидного равенства П = П. Напомним, что гипотеза Р1Р = со-11Р в настоящее время кажется нереальной (реальная гипотеза Р = ХРПсо-КР), и вряд ли для какой-либо ХР-полной задачи удастся доказать принадлежность классу ео-ЯР. Поэтому для конкретной недерминированно полиномиальной массовой задачи ПЕТР, если ее решение представляет интерес, имеет смысл попытаться доказать включение П Е г1Р (т.е. ее хорошую характеризапию) и затем построить полиномиальный алгоритм решения, либо, когда указанное включение не доказывается, надо попробовать полиномиально свести к П одну из известных ХР-полных задач (т.е.
показать ИР-полноту П) и в случае успеха подыскивать переборную схему решения (учитывая ограничения на размерность практически решаемых индивидуальных задач). Доказательство универсальности П, т.е. включения ПЕТЕРС, удается не всегда, и в теории сложности был введен объемлющий 11РС класс ХР-шрудныя задач, содержапшй 1) П распознавания свойств, для которых доказано, что П' «и П для П' Е ХРС, но не показано, что П Е г1Р (в частности, зто задачи ПЕсо-ИРС); 2) П оптимизапни, для которых соответствующие П распознавания свойств ХР-полны (например, задача коммивояжера из п.1 31); 3) и остальные массовые задачи (не обязательно распознавания свойств), к которым сгодювся во Тьюриигу какие-либо г1Р-полные задачи П' Е ХРС, где сводимость по Тьюрингу — П' ~хт П вЂ” означает, что из существования полиномнального алгоритма решения П следует существование полиномиального алгоритма и для П'.
Задачи П (не обязательно распознавания свойств), для которых ЭП' Е г1РС: П' ест П и ЗПл Е ЯР: П ест П", называются задачами из класса ХР-экгягаленшныя. И Все рассмотренные нами классы задач П вЂ” классы слолсиоспзивключаются в общий класс РБРАСЕ массовых задач (не обязательно распознавания свойств), для решения которых существуют алгоритмы, требующие не более чем полиномиальной памяти. Вопрос о равенстве Р и РБРАСЕ является открытым. Рабочая гипотеза состоит в наличии строгого включения РСРБРАСЕ, при этом ХР-полные, ХР-трудные и ХР-эквивалентные задачи должны включаться в РБРАСЕ1Р. (Соответствующую диаграмму взаимосвязи классов сложности см. в [2, с.
412].) Заметим, что теоретически рассмотренную схему построения классов сложности можно применять и для других схем классификации; в частности, вводят также класс РБРАСЕ-полных задач (к которым полиномиально сводится любая задача из класса РБРАСЕ). Кроме полиномиальной сводимости можно аналогично говорить о логарифмической сводимости, о задачах, требующих логарифмической памяти и т.п.
В настоящее время наиболее интенсивно изучаемым здесь оказывается класс МС (%ск С!аяя, автор г1. Р1ррепйег) задач, решаемых за время, ограниченное полиномом от логарифма длины входа, и требующих полиномиальной памяти (логарифмическое время при возможности полиномиального числа процессоров). К сожалению, изложение полученных для ИС результатов выходит за рамки введения в теорию сложности. З..ранее уже отмечалось, что с практической точки зрения разница между полиномиальным алгоритмом (для полиномов высоких степеней) й экспоненциальным весьма условна, а все дело в возможности или невозможности избежать полного перебора. Вопрос, все ли ХР-полные и ИР-трудные задачи трудны для практического счета, мы обсудим ниже в этом параграфе.
Рассмотрим самую простую (по формулировке) ИР-трудную задачу — задачу о рюкзаке (ЗР), заключающуюся в том, чтобы из имеющегося набора полезных вещей собрать рюкзак ограниченного объема с наибольшей пользой. Формально требуется найти в э (~,';~ ~,, <к), к: хз610,1) У1ж1,...,п укн ую1 18 где с! б Е~ — полезность (ценность), цу б И+ — объем (вес) ~-й вещи, а переменная яу определяет класть или не класть ее в рюкзак; максимально возможный объем (вес) рюкзака задается параметром К Е Е.!. Соответствующая задача распознавания свойств — существует ли булево решение системы двух линейных неравенств ся >В и ~~! !зэка<К с натуральными коэффициентами — ! 1Р-полна (доказательство не следует, из утверждения 8, так как рассматривается частный случай БЛН, поэтому см.
(1, с. 87 или 2, с. 386)). Пля решения ЗР известен следующий метод (динамаческоео врограммироеяяия). Произвольная индивидуальная задача 1бЗР погружается в семейство задач поиска е л Г!(Е) =' шах (~~! с!г1'! ~~ юуя1 < К вЂ” Е), х: к!Я(0,!1 У1=4,...,п Г!(0) — значение ЗР. И решаются все задачи данного семейства по рекуррентным формулам, где 1 убывает с и до 1. А именно, положим Е!(Е) ='0 ЧЕ > К, %. Имеем ЧЕ= О,К вЂ” 1: ( О, Е>К вЂ” щ„ ( с„ иначе, и !6 = и — 1,...,2: г!(Е) = шах(Ке!(Е), с;+ р!+!(Е+ щ)) =' !пах (сюхя + р';.!.!(Е+ н!!з!))' Г!(0) =. шах(Гз(0) с! + Гз(!с!)) гчя10,!1 Число итераций предложенного алгоритма равно пК и того же порядка будет его временная сложность. Отметим, что алгоритм не является полиномиальным, ибо для записи числа К требуется порядка 1ойэ К символов; он также оказывается переборным — перебирает все варианты заполненности рюкзака.
Однако при не очень больших объемах рюкзака можно довольно быстро получить решение. Пля обобщения указанного свойства дадим 19 ОЛРеделение 8. Обозначим через пшп(1) максимальное по модулю целое число (ылы О), фигурирующее при задании числовых параметров для индивидуальной задачи 1, и через )Ц =' )г(1)~ — длиыу записы 1.
Алгоритм А решения массовой задачи П (не обязательно распознавания свойств) называется асгоооаоляиомиальиым, если для некоторого полннома р(, ) выполнено ТАОЦ) < р(~Ц,пнш(1)). Примером псевдополыномиального алгоритма является алгоритм динамического программирования для решения ЗР. Лля многих других задач (в частности, КМ) псевдополиномиальных алгоритмов не известно.
Чтобы выделить класс таких задач, введем понятие воАяиомвяльного суэсгивя массовой задачи П как множества тех индивидуальных задач, числовые параметры которых не превосходят полыыома от длины входа, Пр01 = (1 б П~ пшп(1) < р(~Ц)). Опгедепение 9. Массовая задача П распознавания свойств называется сально ХР-волков, если ее полиномиальное сужение ХР- полно, т.е. Чр( ) — полипом: Пр01 б ХРС. Прымерами сильно ХР-полных задач являются ВЫП и 3-ВЫП (как совпадающие со своими полнномыальными сужениями), БЛН (поскольку ВЫП была сведена к ее полыномиальному сужению, в котором модулы правых частей не превышают в), ЦЛН (как обобшеные БЛН в отличие от ЗР), а также КМ [1, с.
123-124). ТеОРемА 4. Если Р ф ЯР, то ны для какой сильно 1з1Р-полной задачи не существует псевдополыномнального алгоритма решения. ЛокАЗАтелъотво проведем от противного. Пусть ЛА4Т А решает сильно ХР-полную задачу П и ТА(~Ц) < р'(~Ц,пнш(1)) для полинома Р'(, ). Тогда зТ б Пр01 ТА(~Ц) < Р'(~Ц,РОЦ)) = Ро(~Ц), т.е. ПрН б Р— пРотивоРечие с Пр01 б ХРС или УтвеРждением 6. Сильно ЯР-полные задачи считаются наиболее трудными для счета среди всех задач класса ХР. Лалее мы покажем, что для подобных задач в оптимизационной постановке отсутствуют эффективные алгоритмы поиска даже приближенного решения.
Рекомендуемым подходом к нх решению является разбиение на подзадачи П'. ЩП') С В(П), У(П') = х (П) ОВ(П'), анализ сложносты подзадач и разработка схем перебора (см. в Ц10,12) для П' б ЯРС. При этом 20 для сильно ХР-полных подзадач не удается использовать метод динамического программирования в качестве способа перебора (ибо, по-видимому, реализующие его алгоритмы псевдополиномиальны) и следует ориентироваться на схему метода ветвей и границ (Ц10,1!). 14. Приближенное решение задач комбинаторной оптимизации Определение задача комбинаторноб оптимиэвцни и приближенного алгоритма ге решение.
Утверждение о разнице между приближенным и точным оптимумом длз задачи о рюкзаке. Определение с-приближенного а ыориглма и полносглью полиномиальноб приближгнноб схемы (ПППС). Связь между существованием ПППС и псгедопо ьиномиальностью. Теорема об отсутствии ПППС длз задач оптимизации, соответствующих сильно ХР-полным задачам распознавания свойств. Пример задача о коммивояжере. Важный класс массовых задач образуют задачи дискретной (комбинаторной) оптимизации.
11ля оптимизационной постановки задачи П решением каждой индивидуальной задачи 1бП является произвольная реализация оптимума Ор1п(1) =' /н(1, з), в взп (1) 'т.е. такая точка з'(1) б Яп(1), для которой,1п(1, з'(1)) = Ор1п(1). Здесь Ян(1) — область допустимых значении дискретной (целочисленной) переменной з, 1п(1, ): Яп(1) Š— целевая функция индивидуальной задачи 1 оптимизации, знак шах в постановке задачи может быть заменен на пцп. Будем обозначать оз и ою те компоненты входного слова о = е(1), определяюшего параметры индивидуальной задачи 1 б П, которые задают допустимую область (ограничения задачи) и функпию цели соответственно.
Например, для ЗР имеем узр(о,з) = (с,з), Пзю (о) = (з = (з1, ° °,зь)1зу б (0,1) Чу = 1,п и (ю,з) < К), оз — (и, ю, К) и о = с. Здесь и далее знак (., ) обозначает скалярное произведение векторов. ОПРЕЛЕЛЕНИЕ 10. Алгоритм А называется приближенным алгоритмом решения массовой задачи П оптимизации, если И б П 21 он находит некоторую точку из допустимой области гл(1) б Яп(1), приыимаемую за приближенное решение. Значение /п(1,гд(1)) называется приближенным значением оптимума и обозначается А(1). Говорить об абсолютной погрешности приближенного алгоритма решения массовой задачи оптимизации (на классе всевозможных индивидуальных задач) не имеет большого смысла, как показывает Утвкрждвнив 11.
Если Р ф ХР, то ыи для какой константы С > О не существует полиномиальыого приближенного алгоритма А решения ЗР с оценкой !Ор$зр(1) — А(1)! < С И б ЗР. Доказательство проведем от противного. Пусть найдены такие С и А. Построим алгоритм А' следующим образом: э1 б ЗР домыожим все коэффициенты с на С+ 1 — получим индивидуальную задачу 1' б ЗР, к которой применим алгоритм А и разделим получеыыый ответ на С+ 1, т.е. А'(1) = А(1')/(С+ 1).
Очевидно, Орезр(1') = (С+ 1)ОрФзр(1) и иэ полиыомиальыости алгоритма А вытекает полиномиальность А'. При этом его точность равна !Ор4зр(1) — А'(1)! = !Орйзр(1') — А(1')!/(С+ 1) < С/(С+ 1) < 1, т.е. равна нулю (так как все значения целевой функции целые). Получили полиыомиальный алгоритм точного решения ЗР. Проверка Ор$зр(1) > В полиномиальна, значит, построили и полиномиальыый алгоритм решения ЗР в постановке распознавания свойств, что с учетом уыиверсальности последней противоречит утверждению 6. Определение 11. Приближенный алгоритм А решения массовой задачи П оптимизации называется г-приближенным алгоритмом решения П для некоторого г > О, если !Ор1п(1) — А(1)! !Орсп(1) ! т.е. его относительыэл погрешность не превосходит г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
