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) раз.

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