Задача коммивояжера и её реализация
Дипломная работа, 26 Апреля 2012, автор: пользователь скрыл имя
Описание работы
Мета. Ознайомлення з постановкою задачі комівояжера на графах та детальне вивчення різних алгоритмів розв’язання задачі комівояжера.
Об’єкт. Задача комівояжера та алгоритми її розв’язку.
Предмет. Розробка середовища та програмна реалізація деяких алгоритмів розв’язку задачі комівояжера
Работа содержит 1 файл
Задача комівояжера та її варіації.doc
— 1.85 Мб (Скачать)end;
Задання матриці відстаней: можна використати один з двох існуючих способів. Перший – введення даних безпосередньо до матриці. Другий – відкриття вже існуючої (раніше створенної матриці). Для цього викликається функція Sbros;(очищення всіх полів на результатів), використовується компонент OpenDialog за допомогою якого ми отримуємо ім’я файлу. Читаємо в циклі з файлу данні та заносимо у відповідні поля:
procedure TForm1.N2Click(Sender: TObject);
var
FInput:Integer;
i,j:byte;
s,num:integer;
begin
Sbros;
OpenDialog1.InitialDir:=
OpenDialog1.Filter:='Файл
if not OpenDialog1.Execute then exit;
FInput:=FileOpen(OpenDialog1.
FileRead(FInput,num,sizeof(
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:=
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.
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(
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]-
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]-
end;
end;
end;
- Викреслення RGor'ого рядка та MGor'ого стовпця здійснюється за допомогою функції
procedure
TForm1.DelStrStolb(Stroka,
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,
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(
end
else begin
Font.Size:=7;
Font.Color:=clBlue;
Brush.Color:=clYellow;
Ellipse(XPos*50+N*30-30-YPos*
TextOut(XPos*50+N*30-58-YPos*
Brush.Color:=clWhite;
Font.Color := clGreen;
if Blok=1 then
Font.Style:=[fsStrikeOut,
else Font.Style:=[fsBold];
TextOut(XPos*55+N*30-60-YPos*
Font.Color := clBlue;
Font.Style:=[fsBold];
TextOut(XPos*94+N*30-115-YPos*
Pen.Color:=clRed;
MoveTo(XPos*50+N*30-45-YPos*
LineTo(Index+N*30-(YPos-1)*30+
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.
Label3.Caption:=Label3.
end;
- Після отримання потрібних результатів створенну матрицю можна
зберегти,
для цього використовується процедура
procedureTForm1.N3Click(
procedure TForm1.N3Click(Sender: TObject);
var
FOutput:Integer;
i,j:byte;
s,num:integer;
begin
SaveDialog1.InitialDir:=
SaveDialog1.Filter:='Файл