Задача коммивояжера

 

 

 

 

 

6) Исходный текст программы на языке Turbo Pascal 7.2

 

 

Program  R_alg;

uses crt,dos;

var nm,e,sc,mm,nt,ch,i,j,n,sm,m,u,v:integer;

    aa,a,al    :array[1..20,1..20] of integer;

    bb,b,bl    :array[1..20,1..2] of integer;

    hh,c       :array[1..20] of integer;

    stj,st     :set of byte;

procedure poisk;

var ss,jj,ii:integer;

begin

    e:=0;    i:=nt;

   repeat

    ss:=aa[i,i];

    for j:=1 to  ch do

    if (ss>aa[i,j]) and  not(j in st) and  not(j in stj) then begin

    ss:=aa[i,j];

    jj:=j;

    end;

   include(st,i);

    include(stj,jj);

    inc(e);

    bl[e,1]:=i;

    bl[e,2]:=jj;

    i:=jj;

   until e=ch; end;

procedure choose;

var q,l,z,x,y:integer;

  begin

     for i:=1 to ch do

     for j:=1 to ch do

     if a[i,j]=0 then

    begin

     x:=i; y:=j;

     inc(n);

     b[n,1]:=x;

     b[n,2]:=y;

    

 

z:=100; l:=100;

     for q:=1 to ch do

     if (z>a[x,q]) and (q<>y) then z:=a[x,q];

     for q:=1 to ch do

     if (l>a[q,y])and (q<>x) then l:=a[q,y];

     c[n]:=z+l;

    end;

  end;

procedure podset;

var e,d:integer;

  begin

     u:=c[1];

     v:=1;

     for e:=1 to n do

     if u<c[e] then begin

     u:=c[e];

     v:=e;

     end;

     bb[mm,1]:=b[v,1];

     bb[mm,2]:=b[v,2];

     inc(mm);

     for e:=1 to ch do

     a[e,b[v,2]]:=100;

     for e:=1 to ch do

     a[b[v,1],e]:=100;

     a[b[v,2],b[v,1]]:=100;

  end;

procedure privid;

var s:array [1..20] of integer;

    w:integer;

  begin

     w:=100;

     for i:=1 to ch do   begin

     for j:=1 to  ch do

     if w>a[i,j] then w:=a[i,j];

     s[i]:=w;

     w:=100;

     end;

 

 

 

 

 

     for i:=1 to ch do

     for j:=1 to  ch do

if (s[i]<>0)and (s[i]<>100) and (a[i,j]<>100)  then a[i,j]:=a[i,j]-s[i];

     w:=100;

     for j:=1 to ch do   begin

     for i:=1 to  ch do

     if w>a[i,j] then w:=a[i,j];

     s[j]:=w;

     w:=100;

     end;

     for j:=1 to ch do

     for i:=1 to  ch do

     if (s[j]<>0) and(s[i]<>100)and (a[i,j]<>100)  then a[i,j]:=a[i,j]-s[j];

     choose;

     podset;   end;

   begin

      textbackground(1);

      textcolor(10);

      mm:=1;  m:=1;

      sm:=0;

      clrscr;

      writeln('Введите количество городов');

      readln(ch);

      writeln(' Введите матрицу стоимости');

      for i:=1 to ch do

      for j:=1 to  ch do

      read(a[i,j]);

      writeln('Введите начальную точку');

      readln(nt);

      nm:=nt;

      for i:=1 to ch do

      for j:=1 to  ch do

      aa[i,j]:=a[i,j];

    repeat

      n:=0;

      privid;

      inc(m);

    until m>ch;

      i:=1;

      writeln (' Минимальный путь по методу ветвей и границ');

    repeat

     

 

if (bb[i,1]=nt) and (sc<=ch) then begin

      inc(sc);

      write(' ',bb[i,1]);

      nt:=bb[i,2];

      if sc<=ch then i:=0;

      end;

      inc(i);

    until i>ch;

      writeln;

      for i:=1 to ch do

      sm:=sm+aa[bb[i,1],bb[i,2]];

      writeln(' Сумма весов:',sm);

      sm:=0;   sc:=0;

      st:=[];  nt:=nm;

      poisk;

      i:=1;

      writeln (' Минимальный путь по методу ближайшего соседа');

    repeat

      if bl[i,1]=nt then begin

      inc(sc);

      write(' ',bl[i,1]);

      nt:=bl[i,2];

      if sc<ch then i:=0;

      end;

      inc(i);

    until i>ch;

      writeln(' ',nm);

      for i:=1 to ch-1 do

      sm:=sm+aa[bl[i,1],bl[i,2]];

      sm:=sm+aa[bl[e,2],bl[1,1]];

      writeln(' Сумма весов:',sm);

      readkey;

end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7) Результаты  тестирования программы.

 

7.1) Тестовые  примеры для проверки правильности  работы программы.

 Тестовый пример №1

Пусть дана следующая  таблица стоимостей путей:

	A	B	C	D
A	--	1	12	1
B	1	--	3	2
C	12	3	--	6
D	1	2	6	--

 

 

 

 

 

 

Решение, полученное для задачи ЗК заданной данной таблицей  вручную:

Оптимальный маршрут: A-B-C-D-A

Стоимость маршрута: 11

 Тестовый пример  №2

Пусть дана следующая  таблица стоимостей путей:

	A	B	C	D	E	F	G
A	--	1	2	6	7	9	12
B	3	--	16	42	1	5	9
C	4	5	--	6	8	3	4
D	5	4	3	--	2	2	1
E	7	6	1	21	--	7	2
F	10	9	8	7	11	--	11
G	1	7	6	2	3	9	--

Решение, полученное для  задачи ЗК заданной данной таблицей  вручную:

Оптимальный маршрут: A-B-E-C-F-D-G-A

Стоимость маршрута: 15

 Тестовый пример №3

Пусть дана следующая  таблица стоимостей путей:

	A	B	C	D	E	F	G	H	I
A	--	1	8	9	6	7	5	4	3
B	6	--	4	3	1	4	2	7	4
C	7	3	--	3	6	3	1	6	5
D	1	5	6	--	8	7	7	9	6
E	2	5	6	7	--	1	8	7	8
F	3	6	1	7	5	--	5	8	9
G	2	3	3	3	4	7	--	4	1
H	2	3	4	1	7	8	7	--	4
I	3	2	3	4	5	6	7	1	--

 

Решение, полученное для задачи ЗК заданной данной таблицей  вручную:

Оптимальный маршрут: A-B-E-F-C-G-I-H-D-A

Стоимость маршрута: 9

 

7.2) Результаты, полученные в результате выполнение  программы для вышеописанных  тестовых примеров.

 

Результат №1

 

 

 

 

 

 

 

 

 

Результат №2

 

 

 

 

 

 

 

 

 

Результат №3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8) Сравнительный  анализ результатов.

 

Как видно из полученных результатов, решение задачи коммивояжера  методом динамического программирования является наиболее оптимальным из 2 представленных методов. Это выясняется из результатов, которые дает метод ближайшего соседа, погрешности, которого при определенных исходных данных очень велики. Однако не стоит забывать, что при большом количестве городов метод динамического программирования сталкивается с проблемой недостатка памяти и экспоненциальным увеличением времени работы, что ограничивает применение этого метода для большого количества городов. В этом случае применение метода ближайшего соседа является более целесообразным. Однако отметим, что в этом случае мы не можем гарантировать, что полученный результат не наихудший из возможных решений.

 

Память, требующаяся для  решения ЗК  методом  динамического программирования:

Общее число сложений и сравнений равно:

 

 

Память, требующаяся для  решения ЗК  методом  ближайшего соседа:

Общее число сложений и сравнений равно:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

  В данной курсовой  работе был изложены алгоритмы  решения задачи коммивояжера, составлены схемы алгоритмов решения этой задачи, а также составлены две программы на языке TURBO PASCAL, реализующие данные схемы.

  Как видно из  анализов курсовой работы ни  один из рассмотренных методов  нельзя назвать универсальным  методом решения задачи коммивояжера. Эти методы имеют недостатки, и для решения задачи с определенными параметрами неприменимы, однако в определенных случаях дают хорошие показатели.

  В ходе выполнения  работы были получены практические  навыки решения задач с использованием графов и представлении их на ЭВМ, закреплен теоретический курс лекций по данному предмету.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы

 

1. М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. Москва: Мир, 1984.

 

2. Ю. М. Коршунов. Математические основы кибернетики. Учебное пособие для вузов. - Москва: Энергия, 1980.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

Раздел                                                                                               стр.

 

Аннотация                                                                                                     2

 

Введение                                                                                                           3

 

Содержательная  постановка задачи                                                       4

 

Анализ  и пример решения задачи.                                                               4

 

Формальная  постановка задачи                                                                6  

 

Спецификация  программы                                                                           8

 

Разработка  структур данных и алгоритмов                                           9

 

Исходный  текст программы на языке Turbo Pascal 7.2                         11      

 

Результаты тестирования программы                                                   16  

 

Сравнительный анализ результатов.                                                       18

 

Заключение                                                                                                     19

 

Список  литературы                                                                                     20