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

    end;

    Задання матриці відстаней:  можна використати один з двох існуючих способів. Перший – введення даних безпосередньо до матриці. Другий – відкриття вже існуючої (раніше створенної матриці). Для цього викликається функція Sbros;(очищення всіх полів на результатів), використовується компонент OpenDialog за допомогою якого ми отримуємо ім’я файлу. Читаємо в циклі з файлу данні та заносимо у відповідні поля:

    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.BitBtn1Click(Sender: TObject); яка містить основні процедури програми:

• визначення кількості міст:

N:=StrToInt(ComboBox1.Text);

• очищення полів та результатів:

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:=250+(N-6)*30;

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

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

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

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

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

  end

  else

  begin

    Image1.Width:=250;

    Image1.Height:=310;

    Form1.Height:=445;

    Form1.Width:=640;

  end;

end;

• процедура читання с полів матриці

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.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;

• Викреслення RGor'ого рядка та MGor'ого стовпця здійснюється за допомогою функції

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;

• виведення результатів у вигляді дерева на компонент Image, виведення довжини туру та розрахунок оптимального шляху:

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.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;

• Після отримання потрібних результатів створенну матрицю можна

зберегти,  для  цього використовується  процедура procedureTForm1.N3Click(Sender: TObject); яка аналогічна по своїй структурі до функції відкриття – тільки замість читання з файлу, вона записує у нього

procedure TForm1.N3Click(Sender: TObject);

var

  FOutput:Integer;

  i,j:byte;

  s,num:integer;

begin

  SaveDialog1.InitialDir:=Application.ExeName;

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