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.


 

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

41804. Проверка выполнения внутренних соединений обмоток электрических машин 53.42 KB
  Укладку в пазы секций обмоток и соединение их а также изоляцию соединений производят по инструкции предприятия изготовителя. Проверку выполнения внутренних соединений обмоток приходится производить в следующих случаях: после капитального ремонта электрических машин если по каким-либо причинам отсутствует или перепутана маркировка выводов а также когда нарушен нормальный режим работы машины выявленный при пуске и испытаниях. Проверка правильно выполненных внутренних соединений обмоток и выводов машин Постоянного тока производится указанными...
41805. Настройка зубодолбёжного станка 5А12 на нарезание зубчатого колеса 531.85 KB
  Зацепление сопровождается следующими рабочими движениями: Возвратнопоступательных движением долбяка главное движение осуществляющим процесс резания. Вращением долбяка являющимся круговым движением подачи. Вращением заготовки согласованным с вращением долбяка движение обкатки. Радикальным врезанием долбяка в заготовку на полную высоту зуба если колесо обрабатывается за один проход или на часть высоты если колесо обрабатывается в несколько проходов.
41806. Система питания бензинового двигателя 231.95 KB
  Система питания автомобилей ВАЗ-21213 включает приборы подачи топлива и воздуха, приготовления горючей смеси и выпуска отработавших газов. Система питания состоит из топливного бака 34, топливного насоса 27, топливопроводов, воздушного фильтра, карбюратора 26, глушителей и трубопроводов. Система с обратным сливом части топлива от карбюратора 26 через калиброванное отверстие патрубка карбюратора в топливный бак. Ось рычага механической подкачки топлива; 2. Рычаг механической подкачки топлива; 3. Рычаг ручной подкачки топлива; 15. Фильтр тонкой очистки топлива; 29.
41808. Статистические функции MS Excel 2010. Построение рядов данных 495.52 KB
  Формат записи функции: МИН число1; число2; Количество допустимых аргументов среди которых находится минимальное значение равно 255. Формат записи функции: МАКС число1; число2; Количество допустимых аргументов среди которых находится максимальное значение равно 255. Формат записи функции: СРЗНАЧчисло1; число2; Количество допустимых аргументов среди которых находится среднее значение равно 255. Формат записи функции: СЧЕТчисло1; число2; Количество допустимых аргументов среди которых находится среднее значение равно 255.
41809. Команды черчения элементов конструкции в программе AutoCAD 69.08 KB
  После этого в командной строке появиться приглашение Specify strt point:.0000 Specify next point or [rc Close Hlfwidth Length Undo Width]: Программа сообщает что текущая толщина полилинии равна 0 и предлагает указать следующую точку линии. После ввода А rc в командной строке появляется подсказка с предложением выбрать метод построения дуги: Specify endpoint of rc or [ngle Center Close Direction Hlfwidth Line Rdius Second pt Undo Width]: В данном случае доступны следующие методы. В командной строке отобразится следующая подсказка: Specify...
41810. Продукт компании SkyBiz-2000 368.42 KB
  Компания предоставляет годовой абонемент на использование пакета InterNetуслуг стоимостью 100. Став членом клуба каждый получает доступ к постоянно обновляемым ресурсам InterNet. Это также ряд онлайновых учебных пособий возможность приобрести практические навыки ведения бизнеса в InterNet включая рекламу. Кроме того клуб предоставляет возможность обмена опытом с InterNetбизнесменами различных стран.
41811. Программная реализация несложного алгоритма 112.6 KB
  Листов 7 Лабораторная работа №7 Тема: Программная реализация несложного алгоритма Цель:изучить на основе готовой программы операторы циклической структуры языка QBsic и научиться составлять программы с использованием операторов цикла ДО и ПОКА. Теоретические сведения к лабораторной работе Определение циклической программы Если необходимо выполнить одинаковые действия в которых изменяется только какаялибо величина то применяются операторы цикла. Виды операторов цикла Оператор цикла ДО Общий вид оператора: FOR K=Kнач TO Kкон STEP...
41812. Определение коэффициента теплопередачи при установившемся тепловом процессе 48.88 KB
  темпра горячей воды т. темпра горячей воды Т2С Начальн. воды t1C Конечн. воды t2c Расход холодной воды.