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 задачи

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

    В пункте 1.1 мы занимались оптимизационным вариантом задачи о коммивояжере. Это задача минимизации, и нас интересовал путь минимальной стоимости. В варианте принятия решения мы могли бы спросить, существует ли путь коммивояжера со стоимостью, меньшей заданной константы С. Ясно, что ответ в задаче о принятии решения зависит от выбранной границы. Если эта граница очень велика (например, она превышает суммарную стоимость всех дорог), то ответ «да» получить несложно. Если эта граница чересчур мала (например, она меньше стоимости дороги между любыми двумя городами), то ответ «нет» также дается легко. В остальных промежуточных случаях время поиска ответа очень велико и сравнимо со временем решения оптимизационной задачи. Поэтому мы будем говорить вперемешку о задачах оптимизации и принятия решений, используя ту из них, которая точнее отвечает нашим текущим целям.

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

ГЛАВА 2 ЗАДАЧА О КОМИВОЯЖЕРЕ 

    В 1859 г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил  детскую головоломку, в которой  предлагалось совершить «круговое  путешествие» по 20 городам, расположенных в различных частях земного шара. Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере. Коммивояжер – не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами как угодно.

    Задача  о коммивояжере относится к классу NP-трудных задач. Методы решения задачи о коммивояжере различны. В данной курсовой кратко рассказывается только о некоторых наиболее известных.

    К эвристическим методам решения  задачи коммивояжёра следует отнести  «жадный» алгоритм, на каждом шаге выбирающий ребро наименьшей стоимости из множества  рёбер, не нарушающих корректности решения. Эти методы имеют большую погрешность. Хорошо исследована область генетических алгоритмов, показавших свою эффективность для данной задачи, но они довольно громоздки. Метод перебора прост, но только лишь при небольшом количестве итераций. 

2.1. Постановка задачи

Рис.1

    Предположим, что бродячий торговец должен, покинув город, которому присвоим номер 1, объехать еще N – 1 городов и вернутся снова в город номер 1. В его распоряжении есть дороги, соединяющие эти города. Он должен выбрать свой маршрут – порядок посещения городов так, чтобы путь, который ему придется пройти, был как можно короче. Основное условие этой задачи состоит в том, что коммивояжер не имеет права возвращаться снова в этот город, в котором он однажды уже побывал.

    Эту задачу можно применять, например, для  определения порядка эффективного сбора мусора из баков на улицах города или выбора кратчайшего пути распространения информации по всем узлам компьютерной сети. Восемь городов можно упорядочить 40 320 возможными способами, а для десяти городов это число возрастает уже до 3 628 800. Поиск кратчайшего пути требует перебора всех этих возможностей. Предположим, что у нас есть алгоритм, способный подсчитать стоимость путешествия через 15 городов в указанном порядке. Если за секунду такой алгоритм способен пропустить через себя 100 вариантов, то ему потребуется больше четырех веков, чтобы исследовать все возможности и найти кратчайший путь. Даже если в нашем распоряжении имеется 400 компьютеров, все равно у них уйдет на это год, а ведь мы имеем дело лишь с 15 городами. Для 20 городов миллиард компьютеров должен будет работать параллельно в течение девяти месяцев, чтобы найти кратчайший путь. Ясно, что быстрее и дешевле путешествовать хоть как-нибудь, чем ждать, пока компьютеры выдадут оптимальное решение.

    Мы  занимались оптимизационным вариантом задачи о коммивояжере. Это задача минимизации, и нас интересовал путь минимальной стоимости. В варианте принятия решения мы могли бы спросить, существует ли путь коммивояжера со стоимостью, меньшей заданной константы С. Ясно, что ответ в задаче о принятии решения зависит от выбранной границы. Если эта граница очень велика (например, она превышает суммарную стоимость всех дорог), то ответ «да» получить несложно. Если эта граница чересчур мала (например, она меньше стоимости дороги между любыми двумя городами), то ответ «нет» также дается легко. В остальных промежуточных случаях время поиска ответа очень велико и сравнимо со временем решения оптимизационной задачи. Поэтому мы будем говорить вперемешку о задачах оптимизации и принятия решений, используя ту из них, которая точнее отвечает нашим текущим целям. 

2.2 Используемые процедуры 

PenaltyLess(list,N,limit)

list упорядоченный список работ

N общее число работ

limit предельная величина штрафа

currentTime=0

currentPenalty=0

currentJob=l

while (currentJob<=N) and (currentPenalty<=limit) do

currentTime=currentTime+list[currentJob.time

if (list[currentJob].deadline<currentTime( then

currentPenalty=currentPenalty+list[currentJob] .penalty

end if

current Job=current Job+1

end while

if currentPenalty<=limit then

return да

else

return нет

    end if 
 
 
 
 

3. Приближения в задаче о коммивояжере

    Для решения многих задач (в  том числе и  из класса Р) пригодны так называемые жадные алгоритмы. Эти алгоритмы пытаются сделать наилучший выбор на основе доступной информации. Напомним, что алгоритмы построения минимального остовного дерева и кратчайшего пути являются примерами жадных алгоритмов.

    Сначала кажется, что для  решения задачи о  коммивояжере можно просто воспользоваться алгоритмом поиска кратчайшего пути, однако ситуация не так проста. Алгоритм Дейкстры предназначен для поиска кратчайшего пути между двумя вершинами, но найденный путь не обязательно проходит через все вершины графа. Однако можно воспользоваться этим общим подходом для построения жадного приближенного алгоритма. Стоимость проезда между городами можно задать матрицей примыканий; пример такой матрицы приведен на рис. 2(данная матрица верхняя треугольная, поскольку стоимость проезда между городами i и j одинакова в обоих направлениях. Если бы мы выписали все стоимости, то нижний треугольник матрицы попросту совпал бы с верхним. Использование верхнетреугольной матрицы позволяет упростить трассировку алгоритмa).

Из/До  2 3 4 5 6 7

1 16 12 13 6 7 11

2  21 18 8 19 5

3   20 1 3 15

4    14 10 4

5     2 17

6      9

Рис. 2 Матрица примыканий для полного взвешенного графа 

    Наш алгоритм будет перебирать набор ребер в  порядке возрастания всех весов. Он не будет формировать путь; вместо этого он будет проверять, что добавляемые к пути ребра удовлетворяют двум условиям:

    1) При добавлении ребра не образуется цикл, если это не завершаю-

    щее ребро в пути.

    2) Добавленное ребро  не является третьим,  выходящим из какой-

    либо  одной вершины.

    В примере с рис. 2 мы выберем первым ребро (3,5), поскольку у него наименьший вес. Следующим выбранным ребром будет (5,6). Затем алгоритм рассмотрит ребро (3,6), однако оно будет отвергнуто, поскольку вместе с двумя уже выбранными ребрами образует цикл [3,5, 6, 3], не проходящий через все вершины. Следующие два ребра (4,7) и (2,7) будут добавлены к циклу. Затем будет рассмотрено ребро (1,5), но оно будет отвергнуто, поскольку это третье ребро, выходящее из :вершины 5. Затем будут добавлены ребра (1,6) и (1,4). Последним до-

бавленным ребром будет (2,3). В  результате мы получим  циклический путь [1, 4, 7, 2, 3, 5, 6, 1], полная длина которого 53. Это неплохое приближение, однако заведомо не оптимальное решение: есть по крайней мере один более короткий путь, [1, 4, 7, 2, 5, 3, 6, 1], полная длина которого 41.

4. ЭВРИСТИЧЕСКИЕ МЕТОДЫ

    Решить  задачу коммивояжера можно с помощью алгоритма Крускала. Также нам могут помочь алгоритмы Борувки и Прима, так называемые «жадные алгоритмы» Эти методы ускоряют разработку алгоритма по сравнению с методом полного перебора, однако не всегда дают оптимальное решение. Но немного расскажем о них.

    Итак, имеется n городов, которые нужно обойти. Для этого достаточно проложить (n-1) путей между городами. Как соединить города так, чтобы суммарная стоимость путешествия была минимальна?

    В общем случае, задачу можно сформулировать так. Пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V — множество вершин (городов), а E — множество их возможных попарных соединений (дороги). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или стоимость пути). W(u,v) называется весовой функцией. Задача состоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.

    Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом. Остовное дерево T, у которого суммарный вес его ребер w(T) = ∑_(u,v)∈T w(u,v) минимален, называется минимальным остовным или минимальным покрывающим деревом.

    Так как рассматриваются только деревья, можно считать все ребра положительными (достаточно добавить к весу всех ребер некоторую относительно большую положительную константу). В противном случае, если стоимость соединения между двумя вершинами равна отрицательному числу, можно несколько раз параллельно соединить их для уменьшения суммарного веса остовного подграфа.

    Также считаем, что для любой пары ребер  их весовые характеристики будут  различны. Это гарантирует уникальность построенного минимального остовного  дерева. Для примера, если все ребра имеют единичный вес, то любое остовное дерево будет минимальным (с суммарным весом v-1, где v – количество вершин в графе).

    Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e=(u,v) выбирается так, чтобы не нарушить этого свойства: A ∪ {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.

    По  определению A, он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит в том, как искать безопасное ребро. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A – одна компонента). Таким образом анализ графа выполняется (n-1) раз.

    Далее приводится общее правило отыскания  безопасных ребер. Для этого есть теорема, которая поможет находить безопасные ребра.