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

gn="justify">    Теорема: Пусть G(V;E) – связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А – некоторый подграф G, являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E(K) ребер графа G, только один конец которых лежит в К. Тогда ребро минимального веса из E(K) будет безопасным.

    В связи с приведенной теоремой введем следующее: безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.  
 

1. АЛГОРИТМ  БОРУВКИ

 

    На  первом шаге A состоит из всех вершин G и пустого множества ребер. В начале очередной фазы алгоритма Борувки, для каждой компоненты связности промежуточного остовного леса выбирается лидер или корень – вершина, сопоставляемая каждой компоненте. Сделать это можно в простейшем случае с помощью обхода A в глубину: вершина, с которой начинается обход очередной компоненты, и будет ее лидером.

    После того, как лидеры выбраны, для каждой компоненты связности находится  безопасное для нее ребро, по существу методом грубой силы. Как только все такие ребра отобраны, они  добавляются к A. Процесс продолжается до тех пор, пока в A присутствует больше одной компоненты связности. 
 

2. АЛГОРИТМ  КРУСКАЛА

 

    Алгоритм  Крускала объединяет вершины графа  в несколько связных компонент, каждая из которых является деревом. На каждом шаге из всех ребер, соединяющих  вершины из различных компонент связности, выбирается ребро с наименьшим весом. Необходимо проверить, что оно является безопасным. Безопасность ребра гарантируется ранее показанной теоремой о безопасных ребрах. Так как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным.

    Остается  понять, как реализовать выбор  безопасного ребра на каждом шаге. Для этого в алгоритме Крускала все ребра графа G перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы  ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются.

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

3. АЛГОРИТМ  ПРИМА

 

    Как и алгоритм Крускала, алгоритм Прима  следует общей схеме алгоритма построения минимального остовного дерева: на каждом шаге мы добавляем к строящемуся остову безопасное ребро. Алгоритм Прима относится к группе алгоритмов наращивания минимального остова: на каждом шаге существует не более одной нетривиальной (не состоящей из одной вершины) компоненты связности, и каждый к ней добавляется ребро наименьшего веса, соединяющее вершины компоненты с остальными вершинами. По теореме такое ребро является безопасным.

    При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получает на вход граф G и его корень r – вершина, на которой будет наращиваться минимальный остов. Все вершины G, еще не попавшие в дерево, хранятся в очереди с приоритетом Ω. Приоритет вершины v определяется значением key[v], которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле p[v] для вершин дерева указывает на родителя, а для вершин из очереди, указывает на остов дерева, в которою ведет ребро с весом key[v] (одно из таких ребер, если их несколько).  

5. Генетический  алгоритм

 

    Генетический  алгоритм — это алгоритм, который  позволяет найти удовлетворительное решение к аналитически неразрешимым проблемам через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «кроссовера», который производит операцию, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд, книга которого «Адаптация в естественных и искусственных системах» является основополагающим трудом в этой области исследований.

    Задача  кодируется таким образом, чтобы  её решение могло быть представлено в виде вектора («хромосома»). Случайным  образом создаётся некоторое  количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), допущенные к «скрещиванию». К этим векторам применяются «генетические операторы» (в большинстве случаев «скрещивание» - crossover и «мутация» - mutation), создавая таким образом следующее «поколение». Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. Д. Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий останова алгоритма. Таким критерием может быть: нахождение глобального, либо субоптимального решения; исчерпание числа поколений, отпущенных на эволюцию; исчерпание времени, отпущенного на эволюцию. Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска.

Таким образом, можно выделить следующие  этапы генетического алгоритма:

• создание начальной популяции;
• вычисление функций полезности для особей популяции (оценивание);
• выбор индивидов из текущей популяции (селекция);
• скрещивание и\или мутация;
• вычисление функций полезности для всех особей;
• формирование нового поколения;
• если условия совпали, то решение найдено (конец цикла), если нет, то цикл повторяется.

    Применяются генетические алгоритмы для решения следующих задач:

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

6. Сложность недетерминированного алгоритма в задаче о комивояжере

 

    Принадлежность  задачи классу NP требует, чтобы мы могли проверить предложенное решение за полиномиальное время. Видно, что описанный алгоритм действительно подсчитывает суммарный штраф. Анализ временной сложности показывает, что цикл while совершает не более N проходов; максимум достигается, если значение переменной currentPenalty не превышает предельное. Учет всех операций позволяет заключить, что общее число сравнений равно 3N + 1, а число сложений равно 3N. Это означает, что сложность алгоритма равна O(N), и значит он полиномиален и удовлетворяет определению класса NP. 

7. Практическое применение задачи коммивояжера

 

    Задача  коммивояжера имеет ряд практических применений. Как следует из самого названия задачи, ее можно использовать для составления маршрута человека, который должен посетить ряд пунктов  и, в конце концов, вернуться в исходный пункт. Например, задача коммивояжера использовалась для составления маршрутов лиц, занимающихся выемкой монет из таксофонов. В этом случае вершинами являются места установки таксофонов и "базовый пункт". Стоимостью каждого ребра (отрезка маршрута) является время в пути между двумя точками (вершинами) на маршруте.

    Задача  о производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором.. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке. Поскольку производство циклическое, то краски надо производить в циклическом порядке (j₁,j₂,..,j_n,j₁). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время C[i,j]. Очевидно, что C[i,j] зависит как от i, так и от j, и что, вообще говоря,C[i,j] ≠ C[j,i]. При некотором выбранном порядке придется на цикл производства красок потратить время, где t_k - чистое время производства k-ой краски (не считая переналадок). Однако вторая сумма в правой части постоянна, поэтому полное время на цикл производства минимизируется вместе с общим временем на переналадку.

    Таким образом, задачи коммивояжера и задача о минимизации времени переналадки  – это просто одна задача, только варианты ее описаны разными словами.

    Задача  о дыропробивном прессе. Дыропробивной  пресс производит большое число одинаковых панелей – металлических листов, в которых последовательно по одному пробиваются отверстия разной формы и величины. Схематически пресс можно представить в виде стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по периметру которого расположены дыропробивные инструменты разной формы и величины. Каждый инструмент присутствует в одном экземпляре. Диск может вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на подвешенный под него инструмент тогда, когда под инструмент подведена нужная точка листа. Операция пробивки j-того отверстия характеризуется четверкой чисел (x_j,y_j,z_j,t_j),, где x_j,y_j- координаты нужного положения стола, z_j - координата нужного положения диска и t_j -время пробивки j-того отверстия.

    Производство  панелей носит циклический характер: в начале и конце обработки  каждого листа стол должен находиться в положениях (x₀, y₀) диск положении z₀ причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x₀,y₀,z₀,0). Чтобы пробить j-тое отверстие непосредственно после i-того необходимо произвести следующие действия:

    1. Переместить стол по оси x из положения x_i в положение x_j, затрачивая при этом время t(x)(|x_i-x_j|)=t_i,j(x);

    2. Проделать то же самое по  оси y, затратив время t_i,j(y);

    3. Повернуть головку по кратчайшей  из двух дуг из положения  z_i в положение z_j, затратив время t_i,j(z);

    4. Пробить j-тое отверстие, затратив время t_j.

    Конкретный  вид функций t(x), t(y), t(z) зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости. Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому С[i,j] = max(t(x), t(y), t(z)). Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к задачи коммивояжера (здесь - симметричной).

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

 

ГЛАВА 3 ЗАДАЧА О РАСКРАСКЕ 

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

    Граф  G — (V, Е) представляет собой набор вершин, или узлов, V и набор ребер Е, соединяющих вершины попарно. Здесь мы будем заниматься только неориентированными графами. Вершины графа можно раскрасить в разные цвета, которые обычно обозначаются целыми числами. Нас интересуют такие раскраски, в которых концы каждого ребра окрашены разными цветами. Очевидно, что в графе с N вершинами можно покрасить вершины в N различных цветов, но можно ли обойтись меньшим количеством цветов? В задаче оптимизации нас интересует минимальное число цветов, необходимых для раскраски вершин графа. В задаче принятия решения нас интересует, можно ли раскрасить вершины в С или менее цветов.