NP-полные задачи

ВВЕДЕНИЕ

      Большинство задач, интересных с практической точки  зрения, имеют полиномиальные (работающие за полиномиальное время) алгоритмы  решения. То есть время работы алгоритма  на входе длины n составляет не более  O(n^k) для некоторой константы k (не зависящей от длины входа). Разумеется, не каждая задача имеет алгоритм решения, удовлетворяющий этому свойству. Некоторые задачи вообще не могут быть решены никаким алгоритмом. Классический пример такой задачи — «проблема остановки» (выяснить останавливается ли данная программа на данном входе). Кроме того, бывают задачи, для которых существует решающий их алгоритм, но любой такой алгоритм работает «долго» — время его работы не есть O(n^k) ни для какого фиксированного числа k.

      Если  мы хотим провести пусть грубую, но формальную границу между «практическими» алгоритмами и алгоритмами, представляющими лишь теоретический интерес, то класс алгоритмов, работающих за полиномиальное время, является разумным первым приближением. Мы рассмотрим класс задач, называемых NP-полными. Для этих задач не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует. Изучение NP-полных задач связано с так называемым вопросом «P = NP». В теории алгоритмов вопрос о равенстве классов сложности P и NP является одной из центральных открытых проблем уже более трех десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас. Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее сложных проблем теории вычислений.

      Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать ее NP-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.

      Эти задачи чрезвычайно важны, а эффективного способа поиска оптимальных путей их решения у нас нет, поэтому в следующей главе мы обратимся к задаче поиска приближенных решений. Рассматриваемые нами задачи образуют класс NP. Мы познакомимся с классическими задачами из этого класса: задача о коммивояжере, задача о раскраске, задача об упаковке рюкзаков, задача о раскладке по ящикам, задача о планировании работ и многие другие. В последующих параграфах мы обсудим, какие свойства задачи позволяют отнести ее к классу NP, а в практической части курсовой работы приведём алгоритм проверки априорных решений.

               Целью моей курсовой работы является определение классов задач Р, NP и NP-полный; объяснение разницы между задачами принятия решений и оптимизации; объяснение причин, по которым задача относится к классу NP; разработка программ на языке высокого уровня типа Pascal и демонстрация решения рассматриваемых алгоритмов в программе Macromedia Flash.

Задачи, которые решались при написании курсовой работы следующие:

1. Написать программы на языке Pascal.
2. Проанализировать быстродействие алгоритмов.
3. Практически продемонстрировать работу алгоритмов в программе Macromedia Flash.
4. Разработать программы по теме “ NP алгоритмы на графах ” в программе Macromedia Flash, которые позволят закрепить знания по данной теме и помогут наглядно увидеть графическую реализацию примеров.

      ГЛАВА 1. НЕДЕТЕРМИНИРОВАННЫЕ АЛГОРИТМЫ  

1. Задачи NP класса

    Большинство алгоритмов, в программировании, имели  полиномиальную сложность. Более того, сложность их всех была O(N3),1 a самым времяемким был алгоритм комплексного умножения. Главное, однако, то, что мы могли найти точное решение таких задач за разумный промежуток времени. Все эти задачи относятся к классу Р — классу задач полиномиальной сложности. Такие задачи называются также практически разрешимыми.

    Есть  и другой класс задач: они практически  неразрешимы и мы не знаем алгоритмов, способных решить их за разумное время. Эти задачи образуют класс NP - недетерминированной полиномиальной сложности. Значение этих слов прояснится к концу параграфа. Отметим только, что сложность всех известных детерминированных алгоритмов, решающих эти задачи, либо экспоненциальна, либо факториальна. Сложность некоторых из них равна 2^N, где N - - количество входных данных. В этом случае при добавлении к списку входных данных одного элемента время работы алгоритма удваивается. Если для решения такой задачи на входе из десяти элементов алгоритму требовалось 1024 операции, то на входе из 11 элементов число операций составит уже 2048. Это значительное возрастание времени при небольшом удлинении входа.

    Словосочетание  «недетерминированные полиномиальные», характеризующее задачи из класса NP, объясняется следующим двух шаговым подходом к их решению. На первом шаге имеется недетерминированный алгоритм, генерирующий возможное решение такой задачи — что-то вроде попытки угадать решение; иногда такая попытка оказывается успешной, и мы получаем оптимальный или близкий к оптимальному ответ, иногда безуспешной (ответ далек от оптимального). На втором шаге проверяется, действительно ли ответ, полученный на первом шаге, является решением исходной задачи. Каждый из этих шагов по отдельности требует полиномиального времени. Проблема, однако, в том, что мы не знаем, сколько раз нам придется повторить оба эти шага, чтобы получить искомое решение. Хотя оба шага и полиномиальны, число обращений к ним может оказаться экспоненциальным или факториальным.

    К классу NP относится задача о коммивояжере. Нам задан набор городов и «стоимость» путешествия между любыми двумя из них. Нужно определить такой порядок, в котором следует посетить все города (по одному разу) и вернуться в исходный город, чтобы общая стоимость путешествия оказалась минимальной. Можно ли найти кратчайший путь, не просматривая их все? До сих пор никому не удалось придумать алгоритм, который не занимается, по существу, просмотром всех путей. Когда число городов невелико, задача решается быстро, однако это не означает, что так будет всегда, а нас как раз интересует решение общей задачи.

    Задача  о коммивояжере, конечно, очень похожа на задачи про графы, где каждый город можно представить вершиной графа, наличие пути между двумя городами — ребром, а стоимость путешествия между ними — весом этого ребра.

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

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

     1) вывести элементы списка в  случайном порядке;

    2) проверить, что s_i < s_i+1 для всех i от 1 до N - 1.

    Это недетерминированный двухэтапный процесс. Первый этап не требует сравнений, и его можно выполнить за N шагов — по одному шагу на выходной элемент списка. Второй этап также полиномиален: для его выполнения необходимо сделать N-1 сравнений. Такая процедура подходит под наше определение класса NP, и можно прийти к выводу, что задача сортировки принадлежит как классу Р, так и классу NP. То же самое можно проделать с любым полиномиальным алгоритмом, поэтому все задачи класса Р лежат и в классе NP, т.е. Р является подмножеством в NP.

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

    В задаче о коммивояжере на первом шаге случайным образом генерируется некоторое упорядочивание городов. Поскольку это недетерминированный процесс, каждый раз будет получаться новый порядок. Очевидно, что процесс генерации можно реализовать за полиномиальное время: мы можем хранить список городов, генерировать случайный номер, выбирать из списка город с этим именем и удалять его из списка, чтобы он не появился второй раз. Такая процедура выполняется за O(N) операций, где N - - число городов. На втором шаге происходит подсчет стоимости путешествия по городам в указанном порядке. Для этого нам нужно просто просуммировать стоимости путешествия между последовательными парами городов в списке, что также требует O(N) операций. Оба шага полиномиальны, поэтому задача о коммивояжере лежит в классе NP. Времяемкой делает ее именно необходимое число итераций этой процедуры.

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

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

    Поясним наше рассуждение примером. Пусть  первая задача состоит в том, чтобы вернуть значение «да» в случае, если одна из данных булевских переменных имеет значение «истина», и вернуть «нет» в противоположном случае. Вторая задача заключается в том, чтобы найти максимальное значение в списке целых чисел. Каждая из них допускает простое ясное решение, но предположим на минуту, что мы знаем решение задачи о поиске максимума, а задачу про булевские переменные решать не умеем. Мы хотим свести задачу о булевских переменных к задаче о максимуме целых чисел. Напишем алгоритм преобразования набора значений булевских переменных в список целых чисел, который значению «ложь» сопоставляет число 0, а значению «истина»— число 1. Затем воспользуемся алгоритмом поиска максимального элемента в списке. По тому, как составлялся список, заключаем, что этот максимальный элемент может быть либо нулем, либо единицей. Такой ответ можно преобразовать в ответ в задаче о булевских переменных, возвращая «да», если максимальное значение равно 1, и «нет», если оно равно 0. 
 

2. NP-полные задачи

    При обсуждении класса NP следует иметь в виду, что наше мнение, согласно которому их решение требует большого времени, основано на том, что мы просто не нашли эффективных алгоритмов их решения. Может быть, посмотрев на задачу коммивояжера с другой точки зрения, мы смогли бы разработать полиномиальный алгоритм ее решения. То же самое можно сказать и про другие задачи, которые мы будем изучать в следующем параграфе.

    Термин  NP-полная относится к самым сложным задачам в классе NP. Эти задачи выделены тем, что если нам все-таки удастся найти полиномиальный алгоритм решения какой-либо из них, то это будет означать, что все задачи класса NP допускают полиномиальные алгоритмы решения.

    Мы  показываем, что задача является NP-полной, указывая способ сведения к ней всех остальных задач класса NP. На практике эта деятельность выглядит не столь уж устрашающе - нет необходимости осуществлять редукцию для каждой NP задачи. Вместо этого для того, чтобы доказать NP-полноту некоторой NP задачи А, достаточно свести к ней какую-нибудь NP-полную задачу В. Редуцировав задачу В к задаче А, мы показываем, что и любая NP задача может быть сведена к А за два шага, первый из которых — ее редукция к В.

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

    Гамильтоновым путем в графе называется путь, проходящий через каждую вершину в точности один раз. Если при этом путь возвращается в исходную вершину, то он называется гамильтоновым циклом. Граф, в котором есть гамильтонов путь или цикл, не обязательно является полным. Задача о поиске гамильтонова цикла следующим образом сводится к задаче о коммивояжере. Каждая вершина графа — это город. Стоимость пути вдоль каждого ребра графа положим равной 1. Стоимость пути между двумя городами, не соединенными ребром, положим равной 2. А теперь решим соответствующую задачу о коммивояжере. Если в графе есть гамильтонов цикл, то алгоритм решения задачи о коммивояжере найдет циклический путь, состоящий из ребер веса 1. Если же гамильтонова цикла нет, то в найденном пути будет по крайней мере одно ребро веса 2. Если в графе N вершин, то в нем есть гамильтонов цикл, если длина найденного пути равна N, и такого цикла нет, если длина найденного пути больше N.

    В 1971 году Кук доказал NP-полноту обсуждаемой в следующем параграфе задачи о конъюнктивной нормальной форме. NP-полнота большого числа задач была доказана путем редукции к ним задачи о конъюнктивной нормальной форме. В книге Гэри и Джонсона, опубликованной в 1979 году, приведены сотни задач, NP-полнота которых доказана.

    Редукция  — настолько мощная вещь, что  если любую из NP-полных задач удастся свести к задаче класса Р, то и все NP задачи получат полиномиальное решение. До сих пор ни одна из попыток построить такое сведение не удалась. 
 

3. Типичные  NP задачи

    Каждая из задач, которые мы будем обсуждать, является либо оптимизационной, либо задачей о принятии решения. Целью оптимизационной задачи обычно является конкретный результат, представляющий собой минимальное или максимальное значение. В задаче о принятии решения обычно задается некоторое пограничное значение, и нас интересует, существует ли решение, большее (в задачах максимизации) или меньшее (в задачах минимизации) указанной границы. Ответом в задачах оптимизации служит полученный конкретный результат, а в задачах о принятии решений — «да» или «нет».