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

    В задаче о раскраске графа требуется  найти способ раскраски вершин графа  в несколько цветов (занумерованных целыми числами) таким образом, чтобы  любые две соседние вершины были покрашены в различные цвета. Принятие решения заключается в том, чтобы установить, можно ли покрасить вершины в С или меньше цветов с соблюдением указанного требования, а оптимизация — в том, чтобы найти минимально необходимое число цветов. На недетерминированном этапе генерируется возможное решение, представляющее собой список вершин и приписанных к ним цветов. Именно на этом этапе решается, сколько будет использовано цветов, поэтому этап проверки не несет ответственности за выбранное число цветов. При выборе решения недетерминированный этап попробует обойтись С цветами. В задаче оптимизации он может начать с большого числа цветов, последовательно уменьшая их количество, пока требуемая раскраска еще возможна. Обнаружив, что граф нельзя раскрасить в X цветов, мы заключим, что раскраска в X+1 цвет является минимально возможной.

             У задачи о раскраске графа есть практические приложения. Если каждая вершина графа обозначает читаемый в колледже курс, и вершины соединяются ребром, если есть студент, слушающий оба курса, то получается весьма сложный граф. Если предположить, что каждый студент слушает 5 курсов, то на студента приходится 10 ребер. Предположим, что на 3500 студентов приходится 500 курсов. Тогда у получившегося графа будет 500 вершин и 35 000 ребер. Если на экзамены отведено 20 дней, то это означает, что вершины графа нужно раскра-

сить  в 20 цветов, чтобы ни у одного студента не приходилось по два экзамена в день. Разработка бесконфликтного расписания экзаменов эквивалентна раскраске графов. Однако задача раскраски графов принадлежит к классу NP, поэтому разработка бесконфликтного расписания за разумное время невозможна. Кроме того при планировании экзаменов обычно требуется, чтобы у студента было не больше двух экзаменов в день, а экзамены по различным частям курсам назначаются в один день. Очевидно, что разработка «совершенного» плана экзаменов невозможна, и поэтому необходима другая техника для получения по крайней мере неплохих планов. 
 

    3.2 Приближения в задаче о раскраске графа 

    Раскраска графа — необычная задача: как  мы уже упоминали ранее, построение раскраски, достаточно близкой к оптимальной, дается столь же сложно, как и построение оптимальной раскраски. Число красок, даваемое наилучшим известным полиномиальным алгоритмом, более чем вдвое превышает оптимальное. Кроме того доказано, что если существует полиномиальный алгоритм, раскрашивающий вершины любого графа числом красок, превышающим оптимальное не более чем вдвое, то существует и полиномиальный алгоритм оптимальной раскраски любого графа. Существование такого алгоритма означало бы, что P=NP. На сложность графа можно наложить некоторые условия, облегчающие его раскраску. Например, известны полиномиальные алгоритмы раскраски планарных графов, т.е. таких графов, которые можно изобразить на плоскости в виде набора вершин и ребер, представленных попарно не пересекающимися дугами. Вот простой алгоритм последовательной раскраски произвольного графа с N вершинами. 
 

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

PROCEDURE C_o_l_o_r (r: Lref);

{ Последовательная  раскраска графа при помощи }

{ рекурсивного  обхода графа в глубину }

{ r - указатель на структуру Вирта }

{ MSet - глобальное  множество }

{ n - глобальная  переменная }

var t,t1: Tref;

    Set1: Set of 0..255; { Вспомогательное множество  }

    i : Integer; { Параметр цикла }

    Fl : Boolean;

BEGIN

   t:=r^.Trail; r^.Flag:=FALSE;

   { Сейчас мы находимся в вершине r^.Key }

   { Исключим цвета всех вершин, смежных  }

   { вершине r^.Key, из множества MSet }

   t1:=t;

   While t1<>Nil do

   begin MSet:=MSet-[t1^.Id^.Color]; t1:=t1^.Next end;

   {Выбор цвета вершины: это "первый" элемент множества MSet }

   Fl:=TRUE; i:=1;

   While Fl do

   If i IN MSet then Fl:=FALSE else i:=i+1;

   r^.Color:=i; { Цвет присвоен! }

   Write ('(',r^.Key,',',r^.Color,') ');

   { Восстановление вспомогательного множества MSet }

   MSet:=[]; For i:=0 to n do MSet:=MSet+[i];

   While t<>Nil do

   Begin

      If t^.Id^.Flag then C_o_l_o_r (t^.Id);

      t:=t^.Next

   end

END; 

    Видно, что этот алгоритм правильно проверяет  допустимость раскраски. Он проходит по всем вершинам, и если вершина непосредственно  связана с другой того же цвета, то алгоритм останавливается и возвращает отрицательный ответ. Если же все пары соседних вершин окрашены различными цветами, то ответ утвердительный. Что касается временной сложности этого алгоритма, то внешний цикл for осуществляет N проходов. Во внутреннем цикле просматривается каждое ребро, выходящее из данной вершины. Поэтому общее число сравнений будет равно числу ребер, т.е. сложность алгоритма равна O(edges) - очевидно полиномиальная оценка, поскольку число ребер в графе не превосходит N². Поэтому наши требования оказываются выполненными. 

    3.4 Правильные раскраски 

    Пусть G=(V,E) — неориентированный граф. Произвольная функция f: V→{1,2,…k}, где k принадлежит множеству натуральных чисел, называется вершинной fc-раскраской графа G. Раскраска называется правильной, если для любых смежных вершин f(u) и f(v). Граф, для которого существует прави-

    льная й-раскраска, называется fe-раскрашиваемым. Минимальное число к, при котором граф G является й-раскрашиваемым, называется хроматическим числом графа и обозначается

    Пример. Меньшим количеством цветов граф правильно раскрасить нельзя из-за наличия треугольников. Рядом с «кружками» — вершинами графа — указаны номера цветов. Метод получения правильной раскраски достаточно прост — закрашиваем очередную вершину в минимально возможный цвет. Введем следующие структуры данных.

    Const Nmax=100; {^Максимальное количество  вершин графа. *}

    Type V=0..Nmax;

    5s=Set Of V;

    MyArray=Array[1..Nmax] Of V;

    Var Gr: MyAr ray; {*Gr - каждой вершине графа определяется номер цвета. *} 

     Для примера, приведенного выше, массив Gr имеет вид:

    Gr[l]=Gr[3]=Gr[5]=l; Gr[2]=Gr[4]=Gr[7]=2; Gr[6]=3.

    Фрагмент  основной логики.

    <формирование  описания графа>;

    For i:=l То N Do Gr[i] : = [Color (i ,0) ] ;

    <вывод  решения>;

    Поиск цвета раскраски для одной вершины можно реализовать с помощью следующей функции:

    Function Color(i,t:V):Integer;{*i - номер

    окрашиваемой  вершины, t - номер цвета,

    с которого следует искать раскраску  данной

    вершины, А - матрица смежности, Gr -результирующий массив. *}

    Var Ws:Ss;

    j:Byte;

    Begin

    Ws:=[ ];

    For j:=l To i-1 Do If A[j,i]=l Then Ws:=Ws+[Gr[j]] ;

    {*Формируем  множество цветов, в которые окрашены  смежные вершины с меньшими  номерами. *}

    j:=t;

    Repeat {*Поиск минимального номера цвета,  в который можно окрасить данную вершину. *}

    Inc(j) ;

    Until Notlj In Ws) ;

    Color:=j;

    End; 

3.4 Сложность недетерминированного алгоритма в задаче 

    Видно, что этот алгоритм правильно проверяет  допустимость раскраски. Он проходит по всем вершинам, и если вершина непосредственно  связана с другой того же цвета, то алгоритм останавливается и возвращает отрицательный ответ. Если же все пары соседних вершин окрашены различными цветами, то ответ утвердительный. Что касается временной сложности этого алгоритма, то внешний цикл for осуществляет N проходов. Во внутреннем цикле просматривается каждое ребро, выходящее из данной вершины. Поэтому общее число сравнений будет равно числу ребер, т.е. сложность алгоритма равна O(edges) - очевидно полиномиальная оценка, поскольку число ребер в графе не превосходит N². Поэтому наши требования оказываются выполненными. 

 

ГЛАВА 4 ЗАДАЧА ОБ УПАКОВКЕ РЮКЗАКА 

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

 

    Задача  о ранце – одна из задач комбинаторной  оптимизации. Классическая задача о ранце  известна очень давно. Вот её постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W – вместимость ранца. Традиционно полагают что W_i , V_i , W, P – целые неотрицательные числа, но встречаются и другие постановки, условия в которых могут отличаться.

    В задаче принятия решения нас интересует, можно ли добиться, чтобы суммарная  стоимость упакованных объектов была по меньшей мере W. Эта задача возникает при выборе стратегии вложения денег: объемом здесь является объем различных вложений, стоимостью — пред полагаемая величина дохода, а объем рюкзака определяется размером планируемых капиталовложений.

      Алгоритмы решения можно разделить  на два типа: точные и приближенные. Точные: применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора). Приближенные алгоритмы: Жадный алгоритм. 
 

2. Приближения в задаче об упаковке рюкзака

 

    Приближенный  алгоритм упаковки рюкзака представляет собой простой жадный алгоритм, выбирающий наилучшее отношение стоимости к размеру. Сначала мы сортируем список объектов по отношению стоимости к размеру. Каждый объект представляется в виде пары [размер, стоимость]. Для списка объектов ([25, 50], [20, 80], [20, 50], [15, 45], [30,105], [35, 35], [20, 10], [10, 45]) удельные стоимости имеют значения (2,4, 2.5, 3, 3.5, 1, 0.5, 4.5). Сортировка удельных стоимостей приводит к списку ([10, 45], [20, 80], [30, 105], [15, 45], [20, 50], [25,50], [35, 35], [20,10]). После этого мы начинаем заполнять рюкзак последовательно идущими элементами отсортированного списка объектов. Если очередной объект не входит — мы отбрасываем его и переходим к следующему;так продолжается до тех пор пока рюкзак не заполнится или список

объектов  не будет исчерпан. Таким образом, если емкость рюкзака 80, то мы сможем поместить в него первые четыре предмета суммарного объема 75 и общей стоимостью 275. Это не оптимальное решение: первые три предмета с добавкой пятого дают суммарный объем 80 и стоимость 280.

4.3 Полный перебор

 

     Название  метода говорит само за себя. Чтобы  получить решение нужно перебрать  все возможные варианты загрузки. Здесь мы будем рассматривать  такую постановку задачи. В рюкзак загружаются предметы N различных типов (количество предметов каждого типа не ограничено), каждый предмет типа I имеет вес W_i и стоимость P_i , i=(1,2..N). Требуется определить максимальную стоимость груза вес, которого не превышает W. Очевидна простая рекурсивная реализация данного подхода Рис 1.4. Временная сложность данного алгоритма равна O(N!). Алгоритм имеет сложность факториал и может работать лишь с небольшими значениями N. С ростом N, число вариантов очень быстро растет, и задача становится практически неразрешимой методом полного перебора. На рис 1.5 показано дерево перебора, дерево имеет 4 уровня. В каждом кружочке показан вес предмета, корень дерева – нулевой вес, то есть когда рюкзак пуст. Первый предмет можно выбрать четырьмя способами, второй – тремя, третий – двумя, а дальше можем взять только один оставшийся предмет.

Рис 3 

Рис 4 

N - Количество предметов. Пусть MaxW - объем рюкзака, P_i – стоимость i-го предмета, W_i – вес i-го предмета.