Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 258
Текст из файла (страница 258)
Докажите, что если каждая из вершин х, у и з окрашена в один из двух цветов — с(гнид) или с(ульян), — то для изображенного на рисунке структурного элемента правильное 3-раскрашивание возможно тогда и толью тогда, когда цвет хотя бы одной из вершин з, р и х — с(Тнпн). е.
Завершите доказательство )чР-полноты З-СОЬОИ. 34.4. Раслксание с лрибылью и предельными сроками Предположим, что имеется одна вычислительная машина и п заданий аы аз,..., а„. Каждое задание а, характеризуется временем выполнения 1, (временем работы машины, необходимым для выполнения задания), прибылью р и конечным сроком выполнения А5.
В каждый момент времени машина может обрабатывать только одно задание, причем задание а после запуска должно без прерываний выполнаться в течение времени 1 . Если задание а будет выполнено до наступления конечного срока его выполнения Ау, то будет получена прибыль р, но если юнечный срок выполнения будет сорван, то и прибыли не будет. Сформулируем такую задачу оптимизации: пусть для множества и заданий известны время обработки, прибьиь и время выполнения; требуется составить расписание таким образом, чтобы были выполнены все задания и общая сумма прибыли была максимальной.
Все величины — время выполнения, прибыль и конечный срок— неотрицательные числа. а Сформулируйте эту задачу в виде задачи принятия решения. 6. Покажите, что эта задача принятия решения )чР-полная. ж Разработайте алгоритм с полиномиальным временем работы, позволяющий решить задачу принятия решения в предположении, что все времена выполнения выражаются целыми числами от 1 до п.
(Указание: воспользуйтесь методами динамического программирования.) а Разработайте алгоритм с полиномиальным временем работы, позволяющий решить задачу оптимизации в предположении, что все времена выполнения выражаются целыми числами от 1 до ц. Заключительные замечания Книга Гарея (Оагеу) и Джонсона (1оЬпзоп) (128] является замечательным учебником по вопросам 1чР-полноты; в ней не только подробно обсуждается теория, но и описываются многие задачи, )чР-полнота которых была доказана до 1979 года. Из этой книги заимствовано доказательство теоремы 34.13, а список )чР-полных задач, описанных в начале раздела 34.5, взят из содержания этой книги. В 198! — 1992 годах Джонсон написал в .Уоигиа) о~ А18опГйтз серию из 23 статей о новых достижениях в исследованиях 1чр-полноты.
В книгах Хопкрофта (Норсгой), Мотвани (Мопчап() и Ульмана ((Л1пип) (176), Лью- 1156 Часть 171 Избраааыс таыы иса (1.ею)з) и Пападимитриу (Рарасйпп1поц) [235], Пападимитриу [268] и Сипсера (Ярзег) [315] проблема ХР-полноты удачно трактуется в контексте теории сложности. В книгах Ахо (АЬо), Хопкрофта (Норсгой) и Ульмана (1ЛЬпап) [5], Дасгупты (1)азйцрГа), Пападимитриу (Рарасйшйпоп) и Вазирани (Уаа)гав) [8Ц, Джонсонбафа (1оЬпзопЪацйЬ) и Шефера (ЯсЬаеГег) [192] и Кляйнберга (К1е(пЬег8) и Тардоса (Тап)оз) [207] также описывается ХР-полнота и рассматриваются примеры приведений. Класс Р был введен в 1964 году Кобхемом (СоЬЬагп) [7Ц и независимо в 1965 году Эдмондсом (Ейпопбз) [99], который ввел также класс ХР и выдвинул гипотезу о том, что Р ф ХР.
Понятие ХР-полноты впервые было предложено Куком (Соо1с) [74] в 1971 году. Кук представил первое доказательство ХР-полноты задач о выполнимости формул и о 3-СХГ-выполнимости. Левин (Еечл) [233] независимо пришел к этому понятию; он доказал ХР-полноту задачи о мозаике. Карп (Катр) [198] в 1972 году предложил методику приведения и продемонстрировал богатое разнообразие ХР-полных задач. В статье Карпа впервые доказывается ХР-полнота задач о клике, о вершинном покрытии и о гамильтоновом цикле.
С тех пор многими исследователями была доказана ХР-полнота тысяч задач. В 1995 году на заседании, посвшценном 60-летию Карпа, Пападимитрну в своем докладе заметил: "... каждый год выходит около шести тысяч статей, в заголовке, аннотации или списке ключевых слов которых содержится термин 'ХР-полный*. Он встречается чаще, чем термины 'компилятор', 'база данных', 'экспертная система', 'нейронная сеть' или 'операционная система' ". Недавняя работа по теории сложности пролила свет на вопрос о сложности приближенных компьютерных вычислений. В ней приводится новое определение класса ХР с помощью "вероятностно проверяемых доказательств".
В этом определении подразумевается, что для таких задач, как задача о клике, о вершинном покрытии, о коммивояжере, в которой выполняется неравенство треугольника, и во многих других получение хорошего приближенного решения является ХР- сложным, поэтому оно не легче, чем получение оптимальных решений. Введение в эту область можно найти в диссертации Ароры (Агота) [20], в главе Ароры и Лунда ((.цш)) в [17Ц, в обзорной статье Ароры [2Ц, в книге под редакцией Мэйра (Мауг), Премеля (Ргбше() и Стиджера (БГейег) [244], а также в обзорной статье Джонсона (1оЬпаоп) [190].
Глава 35. Приближенные алгоритмы Многие задачи, представляюшие практический интерес, являются ХР-полными. Однако онн слишком важны, чтобы отказаться от их решения лишь на том основании, что неизвестно, как получить их оптимальное решение за полиномиальное время. Но даже для ХР-полных задач остается надежда. Во-первых, если объем входных данных небольшой, алгоритм, время работы которого выражается показательной функцией, вполне может подойти.
Во-вторых, иногда удается выделить важные частные случаи, разрешимые за полиномиальное время. В-третьих, остается возможность найти за полиномиальное время решение, близкое к оптимальному (в наихудшем либо в среднем случае). На практике такие решения часто являются достаточно хорошими. Алгоритм, возврашаюший решения, близкие к оптимальным, называется приближенным алгоритмам (арргохппайоп а!йопбзш). В этой главе описаны приближенные алгоритмы с полиномиальным временем выполнения, предназначенные для решения некоторых ХР-полных задач. Оценка качества приближенных алгоритмов Предположим, мы работаем над задачей оптимизации, каждому из возможных решений которой сопоставляется положительная стоимость, и требуется найти решение, близкое к оптимальному. В зависимости от задачи оптимальное решение можно определить либо как такое, которому соответствует максимально возможная стоимость, либо как такое, которому соответствует минимально возможная стоимость; другими словами, это может быть либо задача максимизации, либо задача минимизации.
Говорят, что алгоритм решения задачи обладает отношением, или коэффициентом, аллрокслмации (приближения) (арргох!шазюп гайо) р(п), если для произвольных входных данных размером п стоимость С решения, полученного в результате выполнения этого алгоритма, отличается от стоимости С* оптимального решения не более чем в р(п) раз: шах —, — < р(п) . (35. !) Алгоритм, в котором достигается коэффициент аппроксимации р(п), будем называть р(гь)-приближенным алгоритмом (р(п)-арргох!ша!!оп а!акоп!!пп), Опре- 115б Часть Г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}
