Задача коммивояжера и её реализация

  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;

    2.3 Опис програмного  продукту

    В результаті була створенна програма для розв’язку задачі комівояжера  методом гілок та меж. Основним принципом роботи якої є зведення матриць, пошук нижніх меж, розбиття на підмножини.

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

    Відкриємо матрицю:

    

Рис. 2.1

         
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рис. 2.2 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       Рис.2.3 
 

       Отримаємо матрицю, яка зображена на рис. 2.3. Після роботи програми ми отримаємо такі результати Рис. 2.3 (які відповідають результатам розглянутого прикладку раніше). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    ВИСНОВКИ

     Задача комівояжера є частковим випадком гамільтоновой задачі про

мандрівника. Суть задачі комівояжера полягає в  знаходженні сумарною мінімальної характеристики (відстані, вартості проїзду т.д.), при цьому комівояжер повинен пройти всі n міст по одному разу, повернувшись в те місто, з якого почав.

     Існують багато методів розв’язання задачі комівояжера, в данній роботі були розглянуті методи гілок та меж (алгоритм Літтла), Мурашині алгоритми. Однак тільки метод гілок і меж дає нам в підсумку найоптимальніше рішення.

     Для практичної реалізації ідеї методу гілок та меж до задачі комівояжера потрібно знайти метод визначення нижніх меж підмножини і розбиття множини гамільтонових контурів на підмножини (розгалуження). Таке визначення нижніх меж базується на твердженні, що якщо до всіх елементів i-го рядка або j-го стовпця матриці C додати або відняти число, то задача залишиться еквівалентної до поставленої, тобто оптимальність маршруту комівояжера не зміниться, а довжина будь-якого гамільтонового циклу зміниться на дану величину.

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

    СПИСОК  ВИКОРИСТАНИХ ДЖЕРЕЛ

 

1. Бондарев В.М.,. Рублинецкий В.И, Качко Е.Г., Основы программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998
2. Бондаренко М. Ф., Білоус Н. В., Руткас А.Г., Ком’ютерна дискретна математика. – Харків, Компанія СМІТ, 2004. – 480 с.
3. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы. – Ростов-на-Дону: ООО «Ростиздат», 2004г.
4. Гладков Л.А., Курейчик В.М., Курейчик В.В. Основы теории алгоритмов: Учебное пособие по курсу «Математическая логика и теория алгоритмов». – Таганрог: изд-во ТРТУ, 2002г.
5. Кузнєцов Ю.Н.,. Кузубов В.И,. Волощенко А.Б., Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.
6. Липатов Е.П.. Теория графов и её применения. - М., Знание, 1986,32с.
7. Маркова Е.В., Лисенков А.Н.. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с.
8. Новиков Ф.А. Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.
9. Оре О., Графы и их применение.: Пер. с англ. под ред. И.М. Яглома. - М., “Мир”, 1965, -174 с.
10. Сигорский В.П.. Математический аппарат инженера. - К., “Техніка”, 1975, 768 с.
11. Штовба С. Д. Муравьиные алгоритмы. Математика в приложениях,                     2003, №4, стр. 70-75.
12. A. Lodi, A. P. Punnen “TSP software”, "The traveling salesman problem and its variations" edited by G. Gutin, A. Punnen - Dordrecht: Kluwer Academic Publishers, 2002, pp. 975
13. Marco Dorigo, Vittorio Maniezzo, Alberto Colorni. The Ant System: Optimization by a colony of cooperating agents [Електронний ресурс] / Википедия: свободная энциклопедия. – Режим доступу: ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.15-BIOSYS97.pdf 

    ДОДАТОК

 

unit Main; 

interface 

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, ExtCtrls, Buttons, Menus; 

const

  NN=10; 

type

  Gorod=array[1..NN,1..NN] of integer;

  Dopolnit=array[1..NN] of integer;

  ConPrived=array[0..NN,0..2] of integer;

  Iskluch=array[1..NN] of byte;

  ItogPuti=array[1..NN*2] of integer; 

type

  TForm1 = class(TForm)

    Image1: TImage;

    Label1: TLabel;

    Label4: TLabel;

    Label3: TLabel;

    BitBtn1: TBitBtn;

    Label6: TLabel;

    Label7: TLabel;

    ComboBox1: TComboBox;

    Label2: TLabel;

    Label13: TLabel;

    Label15: TLabel;

    Label18: TLabel;

    Label12: TLabel;

    Label19: TLabel;

    Label16: TLabel;

    Label110: TLabel;

    Label14: TLabel;

    Label17: TLabel;

    Label11: TLabel;

    Label23: TLabel;

    Label25: TLabel;

    Label28: TLabel;

    Label22: TLabel;

    Label29: TLabel;

    Label26: TLabel;

    Label210: TLabel;

    Label24: TLabel;

    Label27: TLabel;

    Label21: TLabel;

    Edit11: TEdit;

    Edit12: TEdit;

    Edit13: TEdit;

    Edit14: TEdit;

    Edit15: TEdit;

    Edit16: TEdit;

    Edit17: TEdit;

    Edit18: TEdit;

    Edit19: TEdit;

    Edit110: TEdit;

    Edit21: TEdit;

    Edit22: TEdit;

    Edit23: TEdit;

    Edit24: TEdit;

    Edit25: TEdit;

    Edit26: TEdit;

    Edit27: TEdit;

    Edit28: TEdit;

    Edit29: TEdit;

    Edit210: TEdit;

    Edit31: TEdit;

    Edit32: TEdit;

    Edit33: TEdit;

    Edit34: TEdit;

    Edit35: TEdit;

    Edit36: TEdit;

    Edit37: TEdit;

    Edit38: TEdit;

    Edit39: TEdit;

   Edit310: TEdit;

    Edit41: TEdit;

    Edit42: TEdit;

    Edit43: TEdit;

    Edit44: TEdit;

    Edit45: TEdit;

    Edit46: TEdit;

    Edit47: TEdit;

    Edit48: TEdit;

    Edit49: TEdit;

    Edit410: TEdit;

    Edit51: TEdit;

    Edit52: TEdit;

    Edit53: TEdit;

    Edit54: TEdit;

    Edit55: TEdit;

    Edit56: TEdit;

    Edit57: TEdit;

    Edit58: TEdit;

    Edit59: TEdit;

    Edit510: TEdit;

    Edit61: TEdit;

    Edit62: TEdit;

    Edit63: TEdit;

    Edit64: TEdit;

    Edit65: TEdit;

    Edit66: TEdit;

    Edit67: TEdit;

    Edit68: TEdit;

    Edit69: TEdit;

    Edit610: TEdit;

    Edit71: TEdit;

    Edit72: TEdit;

    Edit73: TEdit;

    Edit74: TEdit;

    Edit75: TEdit;

    Edit76: TEdit;

    Edit77: TEdit;

    Edit78: TEdit;

    Edit79: TEdit;

    Edit710: TEdit;

    Edit81: TEdit;

    Edit82: TEdit;

    Edit83: TEdit;

    Edit84: TEdit;

    Edit85: TEdit;

    Edit86: TEdit;

    Edit87: TEdit;

    Edit88: TEdit;

    Edit89: TEdit;

    Edit810: TEdit;

    Edit91: TEdit;

    Edit92: TEdit;

    Edit93: TEdit;

    Edit94: TEdit;

    Edit95: TEdit;

    Edit96: TEdit;

    Edit97: TEdit;

    Edit98: TEdit;

    Edit99: TEdit;

    Edit910: TEdit;

    Edit101: TEdit;

    Edit102: TEdit;

    Edit103: TEdit;

    Edit104: TEdit;

    Edit105: TEdit;

    Edit106: TEdit;

    Edit107: TEdit;

    Edit108: TEdit;

    Edit109: TEdit;

    Edit1010: TEdit;

    MainMenu1: TMainMenu;

    N1: TMenuItem;

    N2: TMenuItem;

    N3: TMenuItem;

    N4: TMenuItem;

    N5: TMenuItem;

    N6: TMenuItem;

    N7: TMenuItem;

    N8: TMenuItem;

    OpenDialog1: TOpenDialog;

    SaveDialog1: TSaveDialog;

    N9: TMenuItem;

    procedure FormCreate(Sender: TObject);

    procedure BitBtn1Click(Sender: TObject);

    procedure ComboBox1Change(Sender: TObject);

    procedure N2Click(Sender: TObject);

    procedure N3Click(Sender: TObject);

    procedure N4Click(Sender: TObject);

    procedure N9Click(Sender: TObject);

  private

    procedure InputMatrix;

    procedure Etap(var GInd:integer);

    procedure Konkurir(var r,m:byte);

    procedure OpredilPuti;

    procedure Sbros;

    procedure DelStrStolb(Stroka,Stolb:byte);

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

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

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

    { Private declarations }

  public

    { Public declarations }

  end; 

var

  Form1: TForm1;

  ParKonkur,GorodaIJ:Gorod;

  Ci,Cj:Dopolnit;

  GIndexKon:ConPrived;

  IsklStrok:Iskluch;

  IsklStolb:Iskluch;

  TreeList:TEdit;

  ListName:TLabel;

  Puti,NewPut:ItogPuti;

  N:byte;