{передаем Nab - номер набранной группы, OstW-вместимость, stoim-цена набранного (еще не набрали  нисколько)}

Procedure Search(Nab, OstW, Stoim:integer);

var i:integer;

begin

{здесь  OstW-вес который следует набрать  из оставшихся. Stoim-стоимость текущего  решения}

{Nab - набор  предметов если наполнили рюкзак и набрали стоимость больше чем имеется, то считаем это новым решением}

if (Nab > N) and (Stoim > Max) then begin

{найдено решение}

BestP:=NowP;

Max:=Stoim;

End

{иначе  если количество взятых <= обьема.

забиваем  рюкзак дальше}

else if Nab<=N then

{иначе  если набрано меньше чем влазит}

for i:=0 to OstW div W[Nab] do begin

{идем  от 0 до ост. места}

NowP[Nab]:=i;

{берем  предмет Nab пока есть место в ранце}

Search(Nab+1,OstW-i*W[Nab],Stoim+i*P[Nab]);

{после  каждого взятия предмета увеличиваем

стоимость набора и уменьшаем место в  рюкзаке

на вес  предмета, так же увеличиваем количество

раз взятия предмета}

end;

4.5 Метод ветвей и границ

 

     По  существу данный метод - это вариация полного перебора, с исключениями заведомо не оптимальных решений. Для  полного перебора можно построить  дерево решений. Если у нас есть какое  то оптимальное решение P, мы пытаемся улучшить его, но если на рассматриваемой в текущий момент ветви решение заведомо хуже чем P то следует остановить поиск и выбрать другую ветвь для рассмотрения. Например, на рис 4. есть ограничение на вес рюкзака W=5. Тогда используя метод ветвей и границ можно сократить дерево перебора до такого, рис 5. Видно сразу, что количество вариантов для перебора уменьшилось сразу. А именно осталось 8 вариантов исхода, вместо 24 ранее. Но не всегда получается отсеять достаточно много вариантов чтобы скорость работы была заметно увеличена, всегда можно подобрать такие входные данные, для которых метод ветвей и границ даст оценку по времени идентичную полному перебору.

Рис 5 
 

4.6 Сравнительный анализ методов

 

Минусы  Полного перебора

• Входные данные не велики, для N=7 программа укладывается в 1с. Уже для N=10 требуется примерно 40с.
• Временная сложность O(N!)

Плюсы Полного перебора

• Полный перебор дает точное решение.
• Простота реализации

Минусы  Метода ветвей и границ

• В худшем случае работает как полный перебор.

Плюсы Метода ветвей и границ

• Возможно значительное сокращение времени работы.
• Простота реализации.

Минусы  Жадного алгоритма

• Всегда можно предоставить такой набор, при котором решение будет не точным.

Плюсы Жадного алгоритма

• Высокое время работы, ограниченное только скоростью сортировки, в среднем O(NlogN).
• Может работать с большими значениями N.
• Не использует дополнительных ресурсов компьютера.
• Простота реализации.

На диаграмме 1. показано соотношение времени  работы алгоритмов. По вертикальной оси  в 1/10000 секунд. По горизонтальной оси в зависимости от количества предметов. Для ДП алгоритма для количества n предметов брался вес w=10*n, так как скорость работы ДП алгоритма зависит от произведения w *n.

Диаграмма 1 
 

 

ЗАКЛЮЧЕНИЕ 

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

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

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

     Задача  о коммивояжере имеет множество  обобщений и методы её решения  в различных проявлениях используются на практике.но достаточно хорошим приближением понятия «практической разрешимости задачи». 

?????????

     В ходе исследования задачи о рюкзаке  были выявлены три основных алгоритма  решения. Полный перебор, ДП – программирование, жадный алгоритм. Так же был рассмотрен Метод ветвей и границ, но как сокращение полного перебора. Все методы разделены на две группы. Первая группа – точные методы, сюда входят ДП – алгоритмы, Полный перебор и Метод ветвей и границ. Вторая группа – приближенные методы, к таким методам относится Жадный алгоритм. Выбор использования того или иного метода спорный вопрос, все зависит от постановки задачи, а так же от того, какие цели поставлены. Если требуется найти точное решение, то конечно нужно использовать точные методы, при небольшом наборе входных данных (предметов до 10-20), подойдет перебор или метод ветвей и границ в силу простоты реализации, при больших, следует использовать ДП – алгоритм. Если же точность решения не так важна, или входные данные таковы, что ни один из точных методов не работоспособен, остается применять только приближенные алгоритмы. Но остается возможность комбинирования различных методов для ускорения, или даже применение каких либо “уловок” для конкретного примера. Надеяться же на построение полиномиального алгоритма нет смысла, так как данная задача NP-полна. Безусловно, данная задача очень важна с точки зрения ее приложения в реальной жизни. Не смотря на свою “древность”, рюкзак не только не забывается, наоборот, интерес к нему задаче растет. Оптимальная загрузка транспорта помогает сокращать расходы, получать большую прибыль. Также задача применяется в криптографии и прикладной математике. 

 

СПИСОК  ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 

    

1. Иванов, Б. Н. Дискретная математика. Алгоритмы  и программы: Учеб. Пособие / Б. Н. Иванов. – М.: Лаборатория Базовых Знаний, 2003.  – 300 с.
2. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978. – 432 с.
3. Шапорев, С.Д. Дискретная математика. Курс лекций и практических занятий / С.Д. Шапорев – СПб.: БХВ-Петербург, 2007. – 142 с.

 

ПРИЛОЖЕНИЕ

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

type Lref = ^Leader; { Тип: указатель  на заголовочный  узел }

     Tref = ^Trailer; { Тип: указатель  на дуговой узел }

     { Описание типа  заголовочного узла }

     Leader=Record

        Key : Integer; { Имя заголовочного  узла }

        Color: Integer; { Цвет раскраски  }

        Count: Integer; { Количество  предшественников }

        Flag : Boolean; { Флаг посещения  узла при обходе }

        Trail: Tref; { Указатель на список смежности }

        Next : Lref { Указатель  на следующий узел  в }

                    { списке заголовочных  узлов }

     end;

     { Описание типа  дугового узла }

     Trailer = Record

        Id : Lref;

        Next: Tref

    end;

var Head: Lref; { Указатель на голову  списка }

                { заголовочных узлов  }

    Tail: Lref; { Указатель на  фиктивный элемент  }

                { в конце списка  заголовочных узлов  }

    t : Lref; { Рабочий указатель  для перемещения  }

              { по списку заголовочных звеньев }

    n : Integer; { Количество вершин  в графе }

    MSet: Set of 0..255;

    { Вспомогательное  множество, содер- }

    { жащее 0,1,2...,n }

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

{ ------------------------------------------------------------- }

FUNCTION S_e_a_r_c_h_G_r_a_p_h (w: Integer; Head: Lref): Lref;

{ Функция возвращает  указатель на заголовочный  узел с ключом }

{ w в графе, заданном  структурой Вирта  с указателем Head }

var h: Lref;

BEGIN

   h:=Head; Tail^.Key:=w;

   While h^.Key<>w do h:=h^.Next;

   If h=Tail

   { В списке заголовочных  узлов нет узла  с ключом w }

   then begin

      New (Tail); h^.Count:=0; h^.Trail:=Nil; h^.Next:=Tail

   end;

   S_e_a_r_c_h_G_r_a_p_h:=h

END;

{ -------------------------------------------- 1 0}

PROCEDURE M_a_k_e_G_r_a_p_h (var Head: Lref);

{ Процедура возвращает  указатель Head на  структуру }

{ Вирта, соответствующую  ориентированному  графу }

var x,y: Integer;

    p,q: Lref; { Рабочие указатели  }

    t,r: Tref; { Рабочие указатели  }

     Res: Boolean; { Флаг наличия дуги }

BEGIN

   Write ('Вводите  начальную вершину  дуги: '); Read (x);

   While x<>0 do

   begin

      Write ('Вводите конечную  вершину дуги: '); ReadLn (y);

      { Определим, существует  ли в графе дуга (x,y)? }

      p:=S_e_a_r_c_h_G_r_a_p_h (x,Head);

      q:=S_e_a_r_c_h_G_r_a_p_h (y,Head);

      r:=p^.Trail; Res:=FALSE;

      While (r<>Nil) AND (NOT Res) do

      If r^.Id=q then Res:=TRUE else r:=r^.Next;

      If (NOT Res)

      { Если дуга не  существует, то поместим  ее в граф }

      then begin

         New (t); t^.Id:=q; t^.Next:=p^.Trail;

         p^.Trail:=t; q^.Count:=q^.Count+1

      end;

      Write ('Вводите начальную  вершину дуги: '); Read (x)

   end

END;

{ ------------------------------------------ }

PROCEDURE P_r_i_n_t_G_r_a_p_h (Head: Lref);

{ Вывод структуры  Вирта, заданной  указателем Head }

{ и соответствующей  ориентированному  графу }

var p: Lref; { Рабочий указатель  }

    q: Tref; { Рабочий указатель  }

BEGIN

   p:=Head;

   While p<>Tail do

   begin