Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 227
Текст из файла (страница 227)
Один из принимающих алгоритмов с полиномиальным временем работы проверяет, что объект С закодирован как неориентированный граф, убеждается, что и и о — его вершины, с помощью поиска в ширину находит в графе С кратчайший путь из вершины и к вершине о, а затем сравнивает количество ребер в полученном кратчайшем пути с числом «. Если в объекте С закодирован неориентированный граф, и путь из вершины и к вершине о содержит не более й ребер, алгоритм выводит значение 1 и останавливается.
В противном случае он работает бесконечно долго. Однако такой алгоритм не распознает язык РАТН, поскольку он не выводит явно значение 0 для экземпляров, длина кратчайшего пути в которых превышает 1с ребер. Предназначенный для задачи Рлтн алгоритм распознавания должен явно отвергать бинарные строки, не принадлежащие языку Рлтн.
Для такой задачи принятия решения, как задача Рлтн, подобный алгоритм распознавания разработать легко: вместо того чтобы работать бесконечно долго, если не существует пути из вершины и в вершину о, количество ребер в котором не превышает /с, этот алгоритм должен выводить значение 0 и останавливаться. Для других задач, таких как задача останова Тьюринга, принимающий алгоритм существует, а алгоритма распознавания не существует. Можно неформально определить класс сложности (сошр!ехйу с1аза) как множество языков, принадлежность к которому определяется мерой слоисности (сошр!ех!!у шеааше), такой как время работы алгоритма, определяющего, принад- Глава 34.
МР-полнота 1099 лежит ли данная строка я языку Ь. Фактическое определение класса сложности носит более технический характер. Интересующийся читатель найдет его в статье Хартманиса (Напгпашз) и Стирнса (Ягеагпз) (140~. Воспользовавшись описанным выше формализмом теории языков, можно дать альтернативное определение класса сложности Р: Р = (Ь С (О, 1)": существует алгоритм А, разрешающий язык ь за полиномиальное время). Фактически, Р также является классом языков, которые могут быть приняты за полиномиальное время. Теорема 34.2.
Р = (Ь: Ь принимается алгоритмом с полиномиальным временем работы) . Доказательство. Поскольку класс языков, которые распознаются алгоритмами с полиномиальным временем работы, — это подмножество класса языков, которые принимаются алгоритмами с полиномиальным временем работы, остается лишь показать, что если язык Ь принимается алгоритмом с полиномиальным временем работы, то он также распознается алгоритмом с полиномиальным временем работы. Пусть Ь вЂ” язык, который принимается некоторым алгоритмом с полиномиальным временем работы А. Воспользуемся классическим "модельным" аргументом, чтобы сконструировать другой алгоритм с полиномиальным временем работы А', который бы распознавал язык Ь.
Поскольку алгоритм А принимает язык Ь за время О (и"), где к — некоторая константа, существует такая константа с, что алгоритм А принимает язык Ь не более чем за Т = сп" шагов. Для любой входной строки х алгоритм А' моделирует действие алгоритма А за время Т. По истечении интервала Т алгоритм А' проверяет поведение алгоритма А. Если он принял строку х, то алгоритм А' также принимает эту строку, выводя значение 1. Если же алгоритм А не принял строку х, то алгоритм А' отвергает эту строку, выводя значение О. Накладные расходы алгоритма А', моделирующего алгоритм А„приводят к увеличению времени работы не более чем на полиномиальный множитель, поэтому А' — алгоритм с полиномиальным временем работы, распознающий язык Ь.
И Заметим, что доказательство теоремы 34.2 является неконструктивным. Для данного языка ЬеР граница для времени работы алгоритма А, который принимает язык Ь, на самом деле может быль неизвестна. Тем не менее, известно, что такая граница существует, поэтому существует алгоритм А', способный проверить эту границу, даже если не всегда удается легко найти такой алгоритм.
Часть ЧП. Избранные темы 1100 Упражнения 34.1-1. Определим задачу оптимизации Ьонаезт РАтн Ьенстн как отношение, связывающее каждый экземпляр задачи, состоящий из неориентированного графа и двух его вершин, с количеством ребер в самом длинном пути между этими двумя вершинами. Определим задачу принятия решения ЬОхбезт РАтн Ьенстн = ((С, и, о, к): С = (Ъ", Е) — неорнентированный граф, и, и Е 1", Й > 0 — целое число, существует пугь из вершины и в вершину о, состоящий не менее чем из к ребер). Покажите, что задачу оптимизации ЬОМОЕБТ РАТН ЬЕХОТН можно решить за полиномиальное время тогда и только тогда, когда Ьонпезт РАтн Ьенстн е Р.
34.1-2. Дайте формальное определение задачи поиска самого длинного простого цикла в неориентированном графе. Сформулируйте соответствующую задачу принятия решения. Опишите язык, соответствующий этой задаче принятия решения. 34.1-3. Разработайте формальное кодирование для ориентированного графа в виде бинарных строк для представления при помощи матриц смежности. Выполните то же самое для представления с использованием списка смежных вершин. Покажите, что эти два представления полиномиально связаны. 34.1-4. Является ли алгоритм динамического программирования для решения дискретной задачи о рюкзаке, который предлагалось разработать в задаче 16.2-2, алгоритмом с полиномиальным временем работы? Обоснуйте ваш ответ. 34.1-5. Покажите, что алгоритм, который содержит не больше некоторого постоянного количества вызовов процедуры с полиномиальным временем работы, сам работает полиномиальное время.
Если же алгоритм делает полиномиальное число вызовов такой процедуры, то общее время работы может быть экспоненциальным. 34.1-6. Покажите, что класс Р, который рассматривается как множество языков, замкнут относительно операций объединения, пересечения, конкатенации, дополнения и замыкания Клини. Другими словами, если Ьы Ьз Е Р, то Ь1 0 Ьз е Р и т.д. 34.2 Проверка за полиномиальное время Теперь рассмотрим алгоритм, "проверяющий" принадлежность языку. Например, предположим, что в данном экземпляре (С, и, о, Й) задачи принятия решения РАТН задан также путь р из вершины и в вершину щ Легко проверить, превышает ли длина пути р величину к.
Если она не превышает эту величину, путь Глава 34. МР-полнота 1101 р можно рассматривать как "сертификат" того, что данный экземпляр действительно принадлежит РАтн. Для задачи принятия решения Рлтн такой сертификат, по-видимому, не дает ощутимых преимуществ. В конце концов, эта задача принадлежит классу Р (фактически ее можно решить за линейное время), поэтому проверка принадлежности с помощью такого сертификата занимает столько же времени, сколько и решение задачи. А теперь исследуем задачу, для которой пока неизвестен алгоритм принятия решения с полиномиальным временем работы, но если имеется сертификат, то легко выполнить его проверку.
Гамильтоиовы циклы Задача поиска гамильтоновых циклов в неориентированном графе изучается уже более ста лет. Формально гамилътоигв цикл (папп1гоп1ап сус1е) неориентированного графа С = (У, Е) — это простой цикл, содержащий все вершины множества К Граф, содержащий гамильтонов цикл, называют гамильтоновым (Ьашй1оп1ап); в противном случае он является ивгвмильтоиовым (попЬашй1ошап). В книге Бонди (Вопс$у) и Мьюрти (МпгГу) 145) цитируется письмо Гамильтона (ЖК.
Наппйоп) с описанием математической игры на додекаэдре (рис. 34.2а), в которой один игрок отмечает пятью булавками пять произвольных последовательных вершин, а другой игрок должен дополнить этот путь, чтобы в результате получился путь, содержащий все вершины.
Додекаэдр является гамильтоновым графом, и один из гамильтоновых циклов показан на рис. 34.2а. Однако не все графы являются гамильтоновыми. Например, на рис. 34.2б показан двудольный граф Рис. 34.2. Примеры гамильтонового (а) и негамильтонового (б) графов Часть ч11. Избранные темы 1102 с нечетным количеством вершин.
В упражнении 34.2-2 предлагается доказать, что все такие графы негамильтоновы. Задачу о гамильтоновых циклах (лаш111ошап-сус1е ргоЫеш), в юторой нужно определить, содержит ли граф С гамильтонов цикл, можно определить как форма ьиый язык: НАм Сусли = ((С): С вЂ” гамильтонов граф) . Как алгоритм мог бы распознать язык НАм Сус1.в? Для заданного экземпляра задачи (С) можно предложить алгоритм принятия решения, который бы формировал список всех перестановок вершин графа С, а затем проверял бы каждую перестановку, не является ли она гамильтоновым путем.
Чему равнялось бы время работы такого алгоритма? При использовании "рационального" юдирования графа с использованием матриц смежности количество вершин т графа равно й (~/й), где п = !(С) ! — длина юда для графа С, Всего имеется т! возможных перестановок вершин, поэтому время работы алгоритма равно й (т!) = й (~/й1) = й (2~к), и оно не ведет себя в асимптотическом пределе как О (и") ни для какой юнстанты к. Таким образом, время работы подобного прямолинейного алгоритма не выражается полиномиальной функцией.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
