1827

Теорія складності екстремальних задач. Задача Комівояжора.

Контрольная

Информатика, кибернетика и программирование

Зада́ча комівояже́ра (комівояжер — бродячий торговець, англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.

Украинкский

2013-01-06

140 KB

16 чел.

Зміст

  1.  Вступ.

  1.  Теоретичні відомості.

  1.  Інструкція програмісту.

  1.  Інструкція користувачу.

  1.  Висновок.

  1.  Список використаної літератури.

  1.  Вступ.

В Україні та інших країнах актуальною науково-прикладною задачею є забезпечення високонадійного та ефективного функціонування складних технічних, комп’ютерних, інформаційних, територіально-розподілених систем на стадіях їх життєвого циклу (ЖЦ). Серед систем, що мають стратегічне значення і є критичними складовими інфраструктури різних галузей, важливе місце займають системи з високою ціною відмови (ВЦВ): космічні апарати (КА) та їх угруповання, стартові комплекси (СК), АЕС, банківські платіжні системи (ПС) та інші системи, які суттєво впливають на життєдіяльність регіонів, підприємств та галузей народного господарства. Недостатній рівень надійності та безпеки, виникнення дефектів у таких системах може стати причиною їх відмови або непрацездатності, що призводить до значних економічних збитків, втрати інформації, екологічних катастроф, фатальних наслідків для населення тощо.

Існуючі математичні моделі та методи прикладної теорії надійності, оптимального резервування, теорії ризику, дискретної оптимізації та теорії прийняття рішень мають широке коло практичних застосувань і активно використовуються при дослідженні безпеки та оптимізації надійності складних систем з великою кількістю різнотипних складових (підсистем, елементів), але їх застосування не завжди гарантує комплексне забезпечення надійності систем з ВЦВ. Крім того, ліквідація помилок, що виникають на етапі проектування і пов’язані із складністю розробки систем з ВЦВ, їх унікальністю, різними за своєю природою дефектами технічних, апаратних та програмних компонентів, і можуть бути виявлені лише на стадії експлуатації, вимагає значних коштів і зусиль спеціалістів, а їх наслідки можуть бути катастрофічними.

  1.  Теоретичні відомості.

Зада́ча комівояже́ра (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.

Існує маса різновидів узагальненої постановки задачі, зокрема геометрична задача комівояжера (коли матриця відстаней відображає відстані між точками на площині), трикутна задача комівояжера (коли на матриці вартостей виконується нерівність трикутника), симетрична та асиметрична задачі комівояжера.

Прості методи розв'язання задачі комівояжера: повний лексичний перебір, жадібні алгоритми (метод найближчого сусіда), метод включення найближчого міста, метод найдешевшого включення), метод мінімального кістяка дерева. На практиці застосовують різні модифікації ефективніших методів: метод гілок і меж і метод генетичних алгоритмів, а так само алгоритм мурашиної колонії.

Всі ефективні (такі, що скорочують повний перебір) методи розв'язання задачі комівояжера — евристичні. У більшості евристичних методів знаходиться не найефективніший маршрут, а наближений розв'язок. Користуються популярністю так звані any-time алгоритми, тобто алгоритми, що поступово покращують деякий поточний наближений розв'язок.

Задача комівояжера — NP-повна. Часто на ній проводять випробування нових підходів до евристичного скорочення повного перебору.

Представлення у вигляді графу

Симетрична TSP для чотирьох міст.

Для можливості застосування математичного апарату для розв'язання проблеми, її слід представити у вигляді математичної моделі. Проблему комівояжера можна представити у вигляді моделі на графі, тобто, використовуючи вершини та ребра між ними. Таким чином, вершини графу (на мал.: від A до D) відповідають містам, а ребра  між вершинами i та j сполучення між цими містами. У відповідність кожному ребру  можна зіставити вагу , яку можна розуміти як, наприклад, відстань між містами, час або вартість подорожі. Маршрутом (також гамільтоновим маршрутом) називається маршрут на цьому графі до якого входить по одному разу кожна вершина графа. Задача полягає у відшуканні найкоротшого маршруту.

З метою спрощення задачі та гарантії існування маршруту, зазвичай вважається, що модельний граф задачі є повністю зв'язним, тобто, що між довільною парою вершин існує ребро. Це можна досягти тим, що в тих випадках, коли між окремими містами не існує сполучення, вводити ребра з максимальною вагою (довжиною, вартістю тощо). Через велику довжину таке ребро ніколи не потрапить до оптимального маршруту, якщо він існує.

В залежності від того, що зіставляється вазі ребер, розрізняють різні варіанти задачі, найважливішими з яких є симетрична та метрична задачі.

Асиметрична та симетрична задачі

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

У випадку симетричної задачі всі пари ребер між одними й тими самими вершинами мають однакову вагу, тобто, для ребра  ваги однакові cij = cji. Як наслідок, всі маршрути мають однакову довжину в обидва напрямки. В симетричному випадку кількість можливих маршрутів вдвічі менша за асиметричний випадок. Симетрична задача моделюється неорієнтовним графом (як показано на малюнку).

Насправді, задача комівояжера у випадку реальних міст може бути як симетричною, так і асиметричною в залежності від тривалості або довжини маршрутів в залежності від напряму руху.

Алгоритмічна складність

Оскільки комівояжер в кожному з міст постає перед вибором наступного міста з тих, що він ще не відвідав, існує (n − 1)! маршрутів для асиметричної та (n − 1)! / 2 маршрутів для симетричної задачі комівояжера. Таким чином, розмір простору пошуку залежить над-експоненційно від кількості міст.

Різні варіанти задачі комівояжера (метричний, симетричний та асиметричний) є NP-еквівалентними. Відповідно до поширеної але недоведеної гіпотези про нерівність класів складності P та NP не існує детермінованої машини Тюринга, здатної знаходити розв'язки екземплярів задачі за поліноміальний час в залежності від кількості міст.

Також відомо, що за умови  не існує алгоритму, що для деякого поліному p обчислював би такі розв'язки задачі комівояжера, що відрізнялись би від оптимального щонайбільше на коефіцієнт 2p(n).[Джерело?]

Однак, існують алгоритми пошуку наближених розв'язків для метричної задачі за поліноміальний час, і знайдений маршрут щонайбільше вдвічі (наприклад, 1.5 для алгоритму Христофіда, нім. Christofides) довший за оптимальний. Досі не відомий жоден алгоритм з поліноміальним часом, який би гарантував точність кращу за 1.5 від оптимального. За припущенням , існує (невідома) константа c > 0, така, що жоден алгоритм з поліноміальним часом не може гарантувати точність 1 + c. Як було показано Арора, для евклідової задачі комівояжера існує схема пошуку приблизних розв'язків задачі (PTAS).

  1.  Інструкція програмісту.

Обявлення глобальних змінних:

var

 Form1: TForm1;

 ParKonkur,GorodaIJ:Gorod;

 Ci,Cj:Dopolnit;

 GIndexKon:ConPrived;

 IsklStrok:Iskluch;

 IsklStolb:Iskluch;

 TreeList:TEdit;

 ListName:TLabel;

 Puti,NewPut:ItogPuti;

 N:byte;

 K:integer;

Основні процедури і функції

{Функция обращение к элементам Edit через их Name в строковом режиме}

function TForm1.ObjEdit(S: string; IndexX: byte; IndexY: byte): TEdit;

begin

 Result:=Form1.FindComponent(S + IntToStr(IndexX) + IntToStr(IndexY)) as TEdit;

end;

{****************************************************}

{Функция обращение к элементам Label через их Name в строковом режиме}

function TForm1.ObjLabel(S: string; IndexX: byte): TLabel;

begin

 Result:=Form1.FindComponent(S + IntToStr(IndexX)) as TLabel;

end;

{****************************************************}

{Процедура чтения матрицы из Edit`ов}

procedure TForm1.InputMatrix;

var

 i,j:integer;

begin

 for i:=1 to N do

 begin

   GorodaIJ[i,i]:=-1;

   for j:=1 to N do

   begin

     if i<>j then

     begin

       GorodaIJ[i,j]:=StrToInt(ObjEdit('Edit',i,j).Text);

     end;

   end;

 end;

end;

{****************************************************}

{Процедура нахождения перспективной пары из множества конкурирующих пар}

procedure TForm1.Konkurir(var r,m:byte);

var

 i,j,l:byte;

 xmin,ymin,max:integer;

begin

 for i:=1 to N do

   for j:=1 to N do

     ParKonkur[i,j]:=-1;

{Определяем множество конкурирующих пар городов и определяем для них оценку}

 for i:=1 to N do

   for j:=1 to N do

     if GorodaIJ[i,j]=0 then

     begin

       xmin:=9999; ymin:=9999;

       for l:=1 to N do

       begin

         if (GorodaIJ[i,l]<=xmin) and (GorodaIJ[i,l]<>-1) and (l<>j) then

           xmin:=GorodaIJ[i,l];

         if (GorodaIJ[l,j]<=ymin) and (GorodaIJ[l,j]<>-1) and (l<>i) then

           ymin:=GorodaIJ[l,j];

       end;

       if xmin=9999 then xmin:=0;

       if ymin=9999 then ymin:=0;

       ParKonkur[i,j]:=xmin+ymin;

     end;

{Находим перспективную пару (r,m)}

 max:=-1;

 for i:=1 to N do

   for j:=1 to N do

     if ParKonkur[i,j]>max then

     begin

       max:=ParKonkur[i,j];

       r:=i; m:=j;

     end;

end;

{***************************************************}

{Процедуры ПРИВЕДЕНИЯ матрицы.

А также для нахождения нижней оценки G}

procedure TForm1.Etap(var GInd:integer);

var

 i,j,min:integer;

begin

GInd:=0;

{Находим минимальный элемент матрицы по строкам}

 for i:=1 to N do

 begin

   min:=-1;

   for j:=1 to N do

   begin

     if GorodaIJ[i,j]<>-1 then

     begin

       if min=-1 then min:=GorodaIJ[i,j];

       if GorodaIJ[i,j]<=min then

       begin

         min:=GorodaIJ[i,j];

       end;

     end;

   end;

   if min=-1 then min:=0;

   Cj[i]:=min;

 end;

{отнимаем минимальные элементы из элементов соответствующих строк}

 for i:=1 to N do

 begin

   for j:=1 to N do

   begin

     if GorodaIJ[i,j]<>-1 then

       GorodaIJ[i,j]:=GorodaIJ[i,j]-Cj[i];

   end;

 end;

{Находим минимальный элемент полученной матрицы по столбцам}

for j:=1 to N do

 begin

   min:=-1;

   for i:=1 to N do

   begin

     if GorodaIJ[i,j]<>-1 then

     begin

       if min=-1 then min:=GorodaIJ[i,j];

       if GorodaIJ[i,j]<=min then

       begin

         min:=GorodaIJ[i,j];

       end;

     end;

   end;

   if min=-1 then min:=0;

   Ci[j]:=min;

 end;

{отнимаем минимальные элементы из элементов соответствующих столбцов

и находим оптимальное множество с оценкой}

 for i:=1 to N do

 begin

   GInd:=GInd+Cj[i]+Ci[i];

   for j:=1 to N do

   begin

     if GorodaIJ[i,j]<>-1 then

       GorodaIJ[i,j]:=GorodaIJ[i,j]-Ci[j];

   end;

 end;

end;

{****************************************************}

{Процедура вычеркивания из матрицы Stroka строки и Stolb столбца}

procedure TForm1.DelStrStolb(Stroka,Stolb:byte);

var

 i:byte;

begin

 if (Stroka<>0) and (Stolb<>0) then

   for i:=1 to N do

   begin

     GorodaIJ[Stroka,i]:=-1;

     GorodaIJ[i,Stolb]:=-1;

   end;

end;

{****************************************************}

{Процедура нахождения оптимального пути}

procedure TForm1.OpredilPuti;

var

 i,j,k,l:integer;

 Fl:boolean;

begin

{Поиск начального элемента}

 for i:=1 to n do

 begin

   Fl:=False;

   for j:=1 to N do

     if Puti[i*2-1]=Puti[j*2] then Fl:=true;

   if not Fl then

   begin

     NewPut[1]:=Puti[i*2-1];

     NewPut[2]:=Puti[i*2];

   end;

 end;

{Составления оптимального маршрута}

 for k:=1 to N+1 do

 begin

   for l:=1 to N+1 do

     if Puti[l*2-1]=Newput[k] then

     begin

       NewPut[k]:=Puti[l*2-1];

       NewPut[k+1]:=Puti[l*2];

     end;

   NewPut[N+1]:=newput[1];

 end;

{Вывод последовательности городов на экран}

 for i:=1 to N do

   Label3.Caption:=Label3.Caption+'A'+inttostr(newPut[i])+'->';

 Label3.Caption:=Label3.Caption+'A'+inttostr(newPut[N+1]);

end;

{****************************************************}

{Процедура проверки на замкнутость пути}

procedure ProverkaIskl;

var

 i,j,Stroka,Stolbec,x,y:byte;

begin

 x:=0;

 y:=0;

 for i:=1 to N do

 begin

   Stroka:=0;

   Stolbec:=0;

   for j:=1 to N do

   begin

     if (GorodaIJ[i,j]=-1) and (IsklStrok[i]<>1) then

       if (IsklStolb[j]<>1) then Stroka:=1;

     if (GorodaIJ[j,i]=-1) and (IsklStolb[i]<>1) then

       if (IsklStrok[j]<>1) then Stolbec:=1;

   end;

   if (Stroka=0) and (IsklStrok[i]<>1) then

   begin

     x:=i;

     Stroka:=1;

   end;

   if (Stolbec=0) and (IsklStolb[i]<>1) then y:=i;

 end;

 if x<>0 then

   if y<>0 then GorodaIJ[x,y]:=-1;

end;

{****************************************************}

{Процедура вывода дерева ветления на экран}

procedure TForm1.Tree(K,XPos,YPos,Index,RG,MG,Blok,GIn:byte);

begin

 with Image1.Picture.Bitmap.Canvas do

 begin

   Font.Name:='Arial';

   Font.Style:=[fsBold];

   Pen.Width:=2;

   Pen.Color:=clMaroon;

   if (XPos=0) and (YPos=0) then

   begin

     Font.Size:=7;

     Font.Color:=clBlue;

     Brush.Color:=clYellow;

     Ellipse(N*30-15,10,15+N*30,40);

     TextOut(N*30-10,18,'G[0]');

     Brush.Color:=clWhite;

     Font.Color := clBlue;

     TextOut(N*30-27,18,IntToStr(GIn));

   end

   else begin

     Font.Size:=7;

     Font.Color:=clBlue;

     Brush.Color:=clYellow;

     Ellipse(XPos*50+N*30-30-YPos*30+K*60,10+YPos*50,XPos*50+N*30-60-YPos*30+K*60,40+YPos*50);

     TextOut(XPos*50+N*30-58-YPos*30+K*60,18+YPos*50,('G['+IntToStr(Index+1)+','+IntToStr(XPos)+']'));

     Brush.Color:=clWhite;

     Font.Color := clGreen;

     if Blok=1 then

       Font.Style:=[fsStrikeOut,fsBold]

     else Font.Style:=[fsBold];

       TextOut(XPos*55+N*30-60-YPos*30+K*60,YPos*50-8,'('+IntToStr(RG)+','+IntToStr(MG)+')');

     Font.Color := clBlue;

     Font.Style:=[fsBold];

     TextOut(XPos*94+N*30-115-YPos*30+K*60,YPos*50+18,IntToStr(GIn));

     Pen.Color:=clRed;

     MoveTo(XPos*50+N*30-45-YPos*30+K*60,10+YPos*50);

     LineTo(Index+N*30-(YPos-1)*30+K*60,38+(Index)*50);

   end;

end;

end;

{****************************************************}

{Процедура создания главной формы}

procedure TForm1.FormCreate(Sender: TObject);

begin

 Image1.Picture.Bitmap:=nil;

 Image1.Picture.Bitmap := TBitmap.Create;

 Image1.Picture.Bitmap.Width := Image1.Width;

 Image1.Picture.Bitmap.Height := Image1.Height;

end;

{****************************************************}

{Процедура сброса всех значений}

procedure TForm1.Sbros;

var

 i,j:integer;

begin

 K:=-1;

 for i:=1 to NN do

 begin

   Ci[i]:=0;

   Cj[i]:=0;

   IsklStrok[i]:=0;

   IsklStolb[i]:=0;

   for j:=1 to NN do

     GorodaIJ[i,j]:=0;

 end;

 for i:=0 to NN do

   for j:=0 to 2 do

     GIndexKon[i,j]:=0;

 for i:= 1 to NN*2 do

 begin

   Puti[i]:=0;

   NewPut[i]:=0;

 end;

 Label3.Caption:='';

 Image1.Picture.Bitmap.canvas.fillrect(canvas.cliprect) ;

 if N>6 then

 begin

   Image1.Width:=550+(N-6)*30;

   Image1.Height:=510+(N-6)*50;

   Image1.Picture.Bitmap.Width := Image1.Width;

   Image1.Picture.Bitmap.Height := Image1.Height;

   Form1.Height:=500+(N-6)*50;

   Form1.Width:=740+(N-6)*30;

 end

 else

 begin

   Image1.Width:=500;

   Image1.Height:=520;

   Form1.Height:=540;

   Form1.Width:=740;

 end;

end;

{****************************************************}

{Процедура нажатия кнопки начала}

procedure TForm1.BitBtn1Click(Sender: TObject);

var

 i,RGor,MGor:byte;

 Flag:boolean;

begin

K:=-1;

{Получения количества городов}

 N:=StrToInt(ComboBox1.Text);

{Сброс всех значений на 0}

 Sbros;

 Flag:=true;

{Ввод матрицы длин путей между городами}

 InputMatrix;

{Предварительный этап. Определения исходного множества G0}

 Etap(GIndexKon[0,1]);

 GIndexKon[0,2]:=GIndexKon[0,1];

{Вывод G0 на экран в виде вершины дерева}

 Tree(0,0,0,0,0,0,0,GIndexKon[0,1]);

{Определение множества конкурирующих пар и выбор перспективной пары}

 Konkurir(RGor,MGor);

 Puti[1]:=RGor;

 Puti[2]:=MGor;

 GorodaIJ[RGor,MGor]:=-1;

{i-ые итерации.}

 for i:=1 to N-1 do

   if Flag then

   begin

{Определение множества G(i,2)}

     Etap(GIndexKon[i,2]);

     if GIndexKon[i-1,1]<GIndexKon[i-1,2] then

       GIndexKon[i,2]:=GIndexKon[i,2]+GIndexKon[i-1,1]

     else begin GIndexKon[i,2]:=GIndexKon[i,2]+GIndexKon[i-1,2];

       K:=K+1;

     End;

{Вывод подмножества G(i,2) на экран в виде листа дерева}

     Tree(K,2,i,i-1,RGor,MGor,1,GIndexKon[i,2]);

{Удаление RGor'ой строки и MGor'ого столбца}

     DelStrStolb(RGor,MGor);

     IsklStrok[RGor]:=1;

     IsklStolb[MGor]:=1;

{Вызов процедуры предотвращения образования коротких и длинных подциклов}

     ProverkaIskl;

{Определение множества G(i,1)}

     Etap(GIndexKon[i,1]);

     if GIndexKon[i-1,1]<GIndexKon[i-1,2] then

       GIndexKon[i,1]:=GIndexKon[i,1]+GIndexKon[i-1,1]

     else GIndexKon[i,1]:=GIndexKon[i,1]+GIndexKon[i-1,2];

     Label6.Caption:='Длина пути:  '+IntToStr(GIndexKon[i,1]);

{Вывод подмножества G(i,1) на экран в виде листа дерева}

     Tree(K,1,i,i-1,RGor,MGor,0,GIndexKon[i,1]);

{Определение множества конкурирующих пар и выбор перспективной пары}

     Konkurir(RGor,MGor);

     if ParKonkur[RGor,MGor]>=0 then

     begin

       Puti[i*2+1]:=RGor;

       Puti[i*2+2]:=MGor;

     end;

     if ParKonkur[RGor,MGor]<0 then Flag:=false;

     IsklStrok[RGor]:=1;

     IsklStolb[MGor]:=1;

     GorodaIJ[RGor,MGor]:=-1;

   end;

{Определение оптимального маршрута}

 OpredilPuti;

end;

procedure TForm1.ComboBox1Change(Sender: TObject);

var

 i,j:byte;

begin

 for i:=1 to NN do

 begin

   ObjLabel('Label1',i).Visible:=False;

   ObjLabel('Label2',i).Visible:=False;

   for j:=1 to NN do

     ObjEdit('Edit',i,j).Visible:=False;

 end;

 N:=StrToInt(ComboBox1.Text);

 for i:=1 to N do

 begin

   ObjLabel('Label1',i).Visible:=True;

   ObjLabel('Label2',i).Visible:=True;

   for j:=1 to N do

     ObjEdit('Edit',i,j).Visible:=True;

 end;

end;

procedure TForm1.N2Click(Sender: TObject);

var

 FInput:Integer;

 i,j:byte;

 s,num:integer;

begin

 Sbros;

 OpenDialog1.InitialDir:=Application.ExeName;

 OpenDialog1.Filter:='Файл Коммивояжера (*.kom)|*.kom';

 if not OpenDialog1.Execute then exit;

 FInput:=FileOpen(OpenDialog1.FileName,fmOpenRead);

 FileRead(FInput,num,sizeof(num));

 for i:=1 to num do

   for j:=1 to num do

   if i<>j then

   begin

     FileRead(FInput,s,sizeof(s));

     ObjEdit('Edit',i,j).Text:=IntToStr(s);

   end;

 ComboBox1.ItemIndex:=num-2;

 ComboBox1Change(ComboBox1);

 FileClose(FInput);

end;

procedure TForm1.N3Click(Sender: TObject);

var

 FOutput:Integer;

 i,j:byte;

 s,num:integer;

begin

 SaveDialog1.InitialDir:=Application.ExeName;

 SaveDialog1.Filter:='Файл Коммивояжера(*.kom)|*.kom';

 if not SaveDialog1.Execute then exit;

 FOutput:=FileOpen(SaveDialog1.FileName,fmOpenWrite);

 if FOutput=-1 then

   FOutput:=FileCreate(ChangeFileExt(SaveDialog1.FileName,'.kom'));

 num:=StrToInt(ComboBox1.Text);

 FileWrite(FOutput,num,sizeof(num));

 for i:=1 to num do

   for j:=1 to num do

   if i<>j then

   begin

     s:=StrToInt(ObjEdit('Edit',i,j).Text);

     FileWrite(FOutput,s,SizeOf(s));

   end;

 FileClose(FOutput);

 ChangeFileExt(SaveDialog1.FileName,'.kom');

end;

  1.  Інстркція користувачу.

Програма вирішує складність вибору оптимального шляху між містами. При цьому малює графік оптимального ходу.

Скриншот робочої програми.

Вибираємо кількість міст. Далі вводимо відстань між містами і нажимаємо кнопку «Найти путь», зправа на графіку отримуємо рішення задачі.

5. Висновок

Які висновки можна зробити в результаті? Чи можна вважати, що для задач з високою щільністю поліедрального графа не існують (тобто не можуть бути побудовані) поліноміальні алгоритми? Відразу ж зауважимо, що з нашої розповіді ствердну відповідь на останнє питання зовсім не слід. Більш того, описана інтерпретація традиційних алгоритмів свідчить про досить примітивному однаковості їх в геометричному сенсі, хоча в комбінаторному відношенні часто ці алгоритми зовсім не тривіальні. Тому немає сенсу перебільшувати значення багаторічних безуспішних спроб багатьох фахівців побудувати поліноміальні алгоритми для NP-повних задач. Такі спроби без залучення принципово нових геометричних ідей свідомо приречені на невдачу. Що ж до нових геометричних ідей, слід особливо відзначити що з'явилися відносно недавно поліноміальні алгоритми для задачі лінійного програмування; перший з них побудував Л. Г. Хачіян в 1979 році.

6. Список використаної літератури.

  1.  Ананий В. Левитин «Глава 3. Метод грубой силы: Задача коммивояжера», Алгоритмы: введение в разработку и анализ. — С. 159-160, М.: «Вильямс», 2006. ISBN 0-201-74395-7.
  2.  А. Ахо, Дж. Хопкрофт, Дж. Ульман Построение и анализ вычислительных алгоритмов, «Мир», 1979.
  3.  Bernhard Korte, Jens Vygen Combinatorial Optimization, вид. 3-тє, Springer, 2006. ISBN 3-540-25684-9.
  4.  Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988. - 480с.
  5.  Грэй П. Алгебра, логика и базы данных: Пер. с англ. - М.: Машиностроение, 1989. - 260 с.
  6.  Оре О. Теория графов: Пер. с англ. - М.: Наука, 1968. - 310 с.
  7.  Форд Л., Фалкерсон Д. Потоки в сетях: Пер. с англ. - М.: Мир, 1966.–288 с.
  8.  Марков А.А., Нагорный Н.И. Теория алгоритмов. - М.: Наука, 1984.–300 с.
  9.  Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 1975.- 240 c.
  10.  Кэррол Л. История с узелками: Пер. с англ. - М.: Мир, 1973. - 408 c.


 

А также другие работы, которые могут Вас заинтересовать

75618. ИЗМЕНЧИВОСТЬ МОРФОЛОГИЧЕСКИХ ПРИЗНАКОВ В ПРИРОДНЫХ ПОПУЛЯЦИЯХ СМОРОДИНЫ 291.5 KB
  Листья растений смородины Биберштейна значительно крупнее листьев смородины альпийской. У смородины Биберштейна среднее значение листа по признаку «длинна главной жилки» составляет – 5,2 см, а у смородины альпийской – 2,21 см.
75619. ИЗМЕНЕНИЕ БИОХИМИЧЕСКИХ ПОКАЗАТЕЛЕЙ ПРИ ВИРУСНЫХ ГЕПАТИТАХ 275.5 KB
  Клинические проявления хронического вирусного гепатита в типичных случаях выражены слабо, малоспецифичны и в следствие этого нередко остаются незамеченными. Наиболее главным симптомам является пожелтение кожи, то есть желтушное окрашивание кожи и склер, заметив которое, больные обычно и идут на прием к врачу.
75620. Евразийский Союз как политический проект: анализ эффективности PR-стратегий 376 KB
  Информационное сопровождение политического проекта Евразийского Союза: основные риски и стратегия. Предмет исследования составляют коммуникационные стратегии применяющиеся при реализации политического проекта Евразийского Союза. Цель исследования проанализировать эффективность PRстратегий применяющихся при реализации политического проекта Евразийского Союза. Достижение поставленной цели осуществляется путем решения следующих исследовательских задач: опередить понятие и основные этапы политического проектирования; выявить специфику...
75621. Документооборот в отделе персонала организации (на примере ОАО «Хладокомбинат») 471.5 KB
  Необходимо кардинально поменять организационные структуры управления по предприятию в целом. Ведь правильно подобранное руководство и рабочая группа являются основной составляющей частью успеха. Именно от людей, составляющих организацию, зависит, будет ли предприятие процветать или закроется, не просуществовав и года.
75622. ЖИЛИЩНАЯ ПОЛИТИКА РЕГИОНА (ПО МАТЕРИАЛАМ КРАСНОДАРСКОГО КРАЯ) 388 KB
  Поскольку жилье это самое дорогостоящее благо и достижение современных удобств предполагает высокий уровень развития соответствующей инфраструктуры и отраслей строительного комплекса принятие продуманной государственной программы строительства и общедоступной системы предложения жилья является обязательным условием достижения нормальной жилищной обеспеченности. Теоретической и методологической основой исследования являются фундаментальные положения классической неоклассической...
75623. Журналистская и публицистическая деятельность габриэля гарсиа маркеса: национальная специфика 1.8 MB
  Рассмотреть общественно-политические условия в Колумбии, в которых приходилось работать Габриэлю Гарсиа Маркесу; проанализировать журналистскую и публицистическую деятельность Габриэля Гарсиа Маркеса и ее влияние на становление художественного творчества автора...
75624. Ж.Ж. ДАНТОН, Ж.-П. МАРАТ, М. РОБЕСПЬЕР: ОБРАЗЫ В ИСТОРИИ И МАССОВОМ СОЗНАНИИ 1.32 MB
  Но на пути к демократии революции пришлось пройти через беззаконие террор и диктатуру общество насильственным путем уничтожало старые порядки на пути к светлому будущему. Нельзя не отметить влияние Великой французской революции на дальнейший ход истории. Разумные ценности Великой французской революции отраженные в Декларации прав человека и гражданина 1789 г. Интерес современного общества к истории Великой французской революции обострился еще и под влиянием социальных проблем.
75625. Сирийско-советские отношения в 1970 - 1991 годах 320 KB
  Практика двусторонних политических и экономических отношений Сирии с Советским Союзом, наличие в них определенных успехов, бесспорно, показывает целесообразность и необходимость дальнейшего развития этих отношений в различных областях. Но сотрудничество двух стран нуждается, на наш взгляд, в корректировке в определении своих целей и задач, а также налаживании его нового механизма.
75626. ИНСТРУМЕНТАРИЙ УПРАВЛЕНИЯ КАЧЕСТВОМ КАК ФАКТОР ИНВЕСТИЦИОННОЙ СТРАТЕГИИ БИЗНЕСА В УСЛОВИЯХ ГЛОБАЛЬНОЙ КОНКУРЕНЦИИ 585 KB
  Влияние системы менеджмента качества на выбор инвестиционной стратегии предприятия. Роль качества в условиях глобальной конкуренции в нефтегазовой Отрасли. Описание системы качества используемой Группой Газпром. Сравнительный анализ системы менеджмента качества используемой Группой компаний Газпром с системами менеджмента качества компаний конкурентов на мировом рынке...