Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 69
Текст из файла (страница 69)
е, полностью связанное подмножество множества )Г. Алгоритм А„вычисляющий стоимость, здесь просто вычисляет мощность множества Г'; множество 6 в этом случае пусто. Пример 15.3. Сформулируем подобным образом задачу целочисленного линейного программирования (ЦЛП), Нас будет интересовать следующий ее вид: ш!п с'х, Ах=Ь, х)~ 0 целочисленно. В качестве параметров 3 в алгоритме А„будут выступать матрица А и вектор Ь, Для любого данного целочислешюго вектора х алгоритм Ае проверяет справедливость условий Ах=Ь и х)О.
Ал. горитм А, использует в качестве множества параметров Я вектор с и вычисляет с'х для каждого данного допустимого решения х, г) Заметим, что во всех трех приведенных примерах алгоритмы Ае и А, полиномиальны. В дальнейшем это будет частым и необходимым с практической точки зрения предположением. Интересное исключение, в котором с трудно вычислить (более точно, трудно сравнить с целым числом), содержится в п. (а) задачи 17. Таким образом, комбинаторная задачи опгпимиэации — это вычислительная задача следующего вида: 1о.2.
Задачи олтимиэаиии — это три эооачи По данным представлениям параметров 5 и С для алгоричмов А„и А, найти оптимальное допустимое решение. Назовем это оптитиюционным эарипнгпом данной задачи, Однако комбинаторную задачу оптимизации можно также поставить в следующей более слабой форме. По данным 5 и (~ найти стоимость оптимального решения. Этот вариант будет называться вычислительным вариантом комбинаторной задачи оптимизации. В предположении, что алгоритм А, полиномиален — другими словами, что стоимость с не очень трудно вычислить,— моментально получаем, что вычислительный вариант комбинаторной задачи оптимизации не может быть намного сложнее, чем оптимизационный вариант.
Третий вариант комбинаторной задачи оптимизации особенно важен при изучении сложности задачи, поскольку он ближе всего к прототипу вычислительных задач, традиционно изучаемых в теории вычислений. Этот вариант, называемый вариантом распознавания, имеет следующий вид. Для данной индивидуальной задачи — т. е, представления 5 и Я вЂ” и целого числа 1, определить, существует ли такое допустимое решение )Ег", что с()) =1, '). В отличие от двух ранее введенных вариантов вариант распознавания представляет собой вопрос, на который можно ответить да или нет. Очевидно, ответить на этот вопрос ненамного труднее, чем решить соответствующую вычислительную задачу, так как после ее решения остается только сравнить оптимальную стоимость с(р) с 1.
и выда~ь отвег да в том и только в том случае, если с(()((,. Таким образом, используя только одно предположение, что с легко вычислить, мы установили, что каждый из вариантов — оптимизационный, вычислительный и распознавания (именно в этом порядке) — не сложнее, чем предыдущий. Возникает естественный вопрос; ие имеют ли все эти варианты, грубо говоря, одинаковую сложность? Другими словами, нельзя ли решить вычислительный вариант, эффективно используя гипотетический алгоритм, решающий задачу в вариан~с распознавания, и нельзя ли сделать то же самое соответственно для оптимизационного и вычислительного вариантов? При очень общих и реалистичных предположениях — а именно, что стоимость оптимального решения является целым числом, логарифм которого ограничен полиномом от размера входа — можно показать, что всякий раз, когда вариант распознавания может быть решен эффективно, то же самое справедливо и для вычислительного з) Если исходная задача является на самом деле задачей максимизации, такой, как задача о максимальной клике,зто неравенство йрнннмает внд с())~)й.
)йе зйб Гл. РЕ Х Р-полные задачи варианта. Чтобы показать это, нужно некоторым образом вычислить оптимальную стоимость с(у), задавая для различных значений 1. вопросы вида: «Верно ли, что с(1)(Езв Но это можно осуществить с помощью бпнарного поиска, описанного в лемме 8.4. Из нашего предположения о том, что 1оп с(1) ограничен полиномом от размера входа, следует, что для решения вычислительной задачи можно эффективно использовать любой алгоритм, решающий задачу распознавания. Отметим, что наше предположение о логарифме стоимости справедливо для всех задач оптимизации, ко~орые рассматривались или будут рассматриваться в дальнейшем в этой книге, и оно, очевидно, следует из нашего предположения о том, что алгоритм н(, полиномиален. Не известно общего метода для решения оптимизационного варианта задачи с использованием алгоритма для вычислительного варианта.
Однако к некоторым задачам, по-видимому, применимы определенные варианты метода «динамического программирования». Пример 15.4. Рассмотрим задачу о максимальной клике, описанную в примере 15.2, и предположим, что у нас имеется процедура ргоседнге МАКЕКЛ11КА(6) (саиппеп). она выдает наибольшую клику н Еч она рекурсивна и использует процедуру РАЗМЕРКЛИКИ, которая считается данной) и в 6 иет вершин 1йеп гевнгп Я е!ае Ьей1п пусть ч — такая вершина„что РАЗМЕРКЛИКИ (чз(ч))=РАЗМЕРКЛИКИ(чг), где 6(ч) — нодграф графа Ег, порожденный вершиной ч и всеми смежными с ней вершинами; ге1игп (ч) () МАКСКЛИКА(6(ч) — ч); епд Рис. 15.1.
РАЗМЕРКЛИКИ, которая по данному произвольному графу 6 будет вычислять размер максимальной клики в 6. Другими словами, процедура РАЗМЕРКЛИКИ решает вычислительный вариант задачи о максимальной клике. Тогда можно эффективно использовать эту процедуру для решения оптимизационного варианта с помощью процедуры МАКСКЛИКА, представленной на рис. 15.1. В этой рекурсивной процедуре сначала находится вершина о графа 6, которая заведомо входит в максимальную клику. Это делается путем проверки того, что значение, выдаваемое процедурой РАЗМЕРКЛИКИ для графа 6, не уменьшается при выбрасывании всех вершин, не смежных с о (это означает, что и — вершина некоторой максимальной клики).
Затем рекурсивно находится МАКСКЛИКА для подграфа графа 6, состоящего из всех вершин, смежных с о, и соответствующих ребер, и вершина о добавляется к этой клике. В результате заведомо получается максимальная клика графа 6. Если время работы процедуры РАЗМЕРКЛИКИ в применении к графам с п вершинами ограничено функцией С(л), то оценка 1(п) для 357 времени работы процедуры МАКСКЛИКА удовлетворяет соотношениям Т (О) = О (1), Т (и) ( (и + 1) С (и) + Т (и — 1) + О (и) и, следовательно, Т(п)=0(п' С(п)).
Таким образом, если процедура РАЗМЕРКЛИКИ имеет полиномиальную оценку, то это же справедливо и для процедуры МАКСКЛИКА. К сожалению, вскоре мы продемонстрируем, что очень маловероятно, чтобы любой из указанных трех вариантов задачи о максимальной клике мог быть решен эффективно. Д Можно также показать, что аналогичные рассуждения применимы к ЗК (задача 2), а также к многим другим комбинаторным задачам оптимизации, Таким образом, все три варианта таких комбинаторных задач оптимизации эквивалентны, по крайней мере в отношении существования эффективных алгоритмов. 15.3 Классы Р и Р(Р В предыдущем параграфе мы видели, как по данной задаче оптимизации можно определить тесно связанную с ней задачу распознавания, т.
е, вопрос, на который можно ответить да или нет. Однако некоторые хорошо известные вычислительные задачи с самого начала являются задачами распознавания. Таковы задачи, традиционно изучаемые в теории вычислений. В 1 8.1, например, была упомянута ПРОБЛЕМА ОСТАНОВКИ: по данному алгоритму и его входу определить, остановится ли алгоритм когда-нибудь. В гл.
13 была введена задача ВЫПОЛНИМОСТБс по данной булевой формуле выяснить, выполнима ли она. В й 12.6 был введен вариант задачи о гамильтоцовом цикле: выяснить, существует ли в данном графе 6 цикл, проходящий , через каждую вершину ровно один раз. Все эти задачи являются задачами распознавания. Наше определение вариантов распознавания для задач оптимизации позволяет изучать задачи обоих видов в единой постановке. Кроме того, так как мы показали, что вариант распознавания не труднее, чем исходная задача оптимизации, любые отрицательные результаты, доказанные о сложности варианта распознавания, будут также применимы к оптимизационному варианту. Нас интересует классификация задач распознавания по их сложности. Обозначим через Р класс задач распознавания, которые могут быть решены некоторым полиномиальным алгоритмом.
Класс Гл. 15. Гэ'Р-иолиие гадали Р можно определить очень точно с помощью любого математического формального определения алгоритмов, такого, как машина Тьюринга (Тн). Однако оказывается, что все такие разумные модели вычисления обладают замечательным свойством: если задачу можно решить за полиномиальное время в одной из них, то ее можно решить за полиномиальное время во всех остальных. Таким образом, этот класс Р исключительно устойчив относительно вариаций в деталях наших предположений. Поэтому мы удовлетворимся неформальным определением Р как класса задач распознавания, для которых имеются полиномиальные алгоритмы, другими словами, Р— это класс относительно простых задач распознавания, для которых существуют эффекэивные алгоритмы. Нам уже встречалось много представителей класса Р.
Ниже мы выпишем еще несколько примеров. СВЯЗНОСТЬ ГРАФА Выяснить, является ли данный граф 0 связным (см. 99,1), ПУТЬ В ОРГРАФЕ Даны орграф 0=(У, А) и два подмножества 5, Тс:-У. Вьшснить, существует ли в 0 'йуть из какой-нибудь вершины множества 5 в некоторую вершину множества Т (см. ~ 9.1). МАКСИМАЛЬНОЕ ПАРОСОЧЕТАНИЕ Даны граф 0 и целое число к. Выяснить, существует ли в 0 паросочетание с к или более ребрами (см. гл. !0).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
