1827

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

Контрольная

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

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

Украинкский

2013-01-06

140 KB

15 чел.

Зміст

  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.


 

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

3014. Бридж - карточная игра 174.5 KB
  Бридж – сравнительно молодая игра. Она сформировалась в несколько этапов (бридж-вист, бридж-аукцион, бридж-плафон, контракт-бридж) в конце XIX – начале XX века на основе русской карточной игры винт и английской карточной...
3015. Искользование песка для строительных работ 60.5 KB
  Характеристики песка. Песок для строительных работ. Назначение и применение. Песок - это природный нерудный материал, который представляет собой рыхлую, сыпучую обломочную горную породу. Песок образуется при разрушении горных пород, переносится водо...
3016. Особенности спортивной игры Волейбол 64 KB
  ВОЛЕЙБОЛ: ВОЗНИКНОВЕНИЕ И СТАНОВЛЕНИЕ ИГРЫ (1895-1920) При обучении будущих специалистов физического воспитания и спорта важно конкретизировать и дополнить историю эволюции волейбола в её хронологической последовательности...
3017. Філософські основи сучасного туризму 223 KB
  Зростання місця і ролі сфери туризму у сучасному світі є привабливим предметом дослідження з кількох причин. По-перше, глобалізація сучасного світу є наслідком зміни змісту і характеру праці, що викликає значне підвищення мобільності людини не...
3018. Цех по производству изделий бытового назначения методом литья под давлением мощностью 7000 тонн в год 179 KB
  Описание технологической схемы производства: Из полувагона или цистерны полимер в виде гранулятя выгружается краном в контейнерах и перевозится к установке растаривания и передается пневмотранспортом 12 в силосы. Затем...
3019. Определение концентрации серной и соляной кислот 39.5 KB
  Растворы Цель работы: Определить концентрацию серной и соляной кислот. Теория: Титрование – постепенное преливание раствора известной концентрации к раствору с неизвестной концентрацией, но точного объёма. Молярная концентрация – число мол...
3020. Анализ управленческой деятельности открытого акционерного общества Вологодский машиностроительный завод 185 KB
  Организационно - правовая деятельность предприятия. Местом прохождения практики является Открытое акционерное общество Вологодский машиностроительный завод (далее ОАО ВМЗ). Свою деятельность в соответствии с действующим Законодатель...
3021. Анализ рынка банковских векселей 372.73 KB
  Сектор банковских векселей После краха рынка ГКО и потери практически всех средств, инвестированных в госбумаги, многие операторы перенесли свои операции в сектор векселей банков и компаний, своевременно погашающих свои об...
3022. Особенности создания бренда 90 KB
  Общая теория бренда Давайте сначала выясним для себя что есть бренд? Все его видели – немногие знают в лицо. Бренд – американизированный (а значит, сокращенный) вариант английского сложносочиненного brand-name (значение brand: 1.3.: кл...