Математические основы решение задачи коммивояжера

Теперь приступим  к ветвлению. Для этого проделаем  шаг оценки нулей. Рассмотрим нуль в  клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все  равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены правее и выше нуля (оценки нуля, равные нулю, не ставились).

Выберем максимальную из этих оценок (в примере есть несколько  оценок, равных единице, выберем первую из них, в клетке (1,2)).

Итак, выбрано  нулевое ребро (1,2). Разобьем все туры на два класса — включающие ребро (1,2) и не включающие ребро (1,2). Про  второй класс можно сказать, что  придется приплатить еще 1, так что  туры этого класса стоят 35 или больше.

Что касается первого класса, то в нем надо рассмотреть матрицу с вычеркнутой  первой строкой и вторым столбцом.

Дополнительно в уменьшенной матрице поставлен  запрет в клетке (2,1), т. к. выбрано  ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицу можно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий, стоит не меньше 35

Кружки представляют классы: верхний кружок — класс  всех туров; нижний левый — класс  всех туров, включающих ребро (1,2); нижний правый — класс всех туров, не включающих ребро (1,2). Числа над кружками — оценки снизу.

Продолжим ветвление  в положительную сторону: влево - вниз. Для этого оценим нули в  уменьшенной матрице C[1,2]. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины есть 35+3=38. Для оценки левой нижней вершины нужно вычеркнуть из матрицы C[1,2] еще строку 3 и столбец 1, получив матрицу C[(1,2),(3,1)] В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. [3,1,2], и нужно запретить преждевременное замыкание (2,3).

Оцениваем теперь нули в приведенной матрице C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится  в клетке (6,5). Отрицательный вариант  имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6). Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается.

Оценивая  нули в матрице, получаем ветвление  по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу.

В матрицу  надо добавить запрет в клетку (5,3), ибо  уже построен фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1→2→6→5→4→3→1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

Итак, все  классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому  соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

Для получения  оценки положительного варианта исключаем  из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием.

2 РАЗРАБОТКА И ОПИСАНИЕ  АЛГОРИТМА РЕШЕНИЯ  ЗАДАЧИ

2.1 Описание работы  программы

Программа реализована  в среде Borland Delphi 7.0. Она включает несколько процедур и функций:

1)    Procedure Tkomi.Alg2 - процедура алгоритма нахождения кратчайшего пути

2)    Function min - функция нахождения минимума

3)    Function provall - функция провала

Интерфейс программы  реализован в виде окна, в котором  расположено несколько объектов:

1)    Информация о программе и разработчиках

2)    Поле для ввода количества городов (вершин)

3)    Таблица для ввода стоимостей проезда из города в город

4)    Поле для вывода конечного результата

2.3 Текст программы

Unit prog;

Interface

Uses

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

StdCtrls, ExtCtrls, Grids,ComCtrls;

Type

Tkomi = class (TForm)

Matr1: TStringGrid;

Memo1: TMemo;

Edit1: TEdit;

Label1: TLabel;

Button2: TButton;

Button3: TButton;

Button4: TButton;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

Private

Public

kol:integer;

procedure Alg2;

End;

const n=10;

var komi: Tkomi;

implementation {$R *.dfm}

{-------------Процедура Алгоритма нахождения кратчайшего пути------------------}

Procedure Tkomi.Alg2;

var

d,i:integer;

prov:array[1..10]of boolean;

s:string;

sum1:integer;

{---Функция минимума---}

Function min(i:integer):integer;

var min1,j:integer;

g:integer;

begin

min1:=60000;

for j:=1 to 10 do

if j<>i then

if prov[j]then

if matr1.Cells[j,i]<>'X' then

if min1>strtoint(matr1.Cells[j,i])then

begin

min1:=strtoint(matr1.Cells[j,i]);

g:=j;

end;

min:=g;

end;

{---Функция провала---}

Function provall:boolean;

var i:integer;f:boolean;

begin

f:=false;

for i:=1 to 10 do f:=(f)or(prov[i]);

provall:=not(f);

end;

begin

for i:=1 to kol do prov[i]:=true;

d:=1;s:=matr1.Cells[0,1]+'->';

sum1:=0; prov[1]:=false;

repeat

s:=s+matr1.Cells[0,min(d)]+'->';

if matr1.Cells[d,min(d)]='X' then sum1:=sum1+0

else sum1:=sum1+strtoint(matr1.Cells[d,min(d)]);

d:=min(d);

prov[d]:=false;

until provall;

sum1:=sum1+strtoint(matr1.Cells[d,1]);

s:=s+matr1.Cells[0,1];

memo1.clear;

memo1.Lines.Add(' ');

memo1.Lines.add(' Найденный путь: '+s);

memo1.lines.add(' Длина пути = '+inttostr(sum1));

end;

//Кнопка "Ввод"

Procedure Tkomi.Button2Click(Sender: TObject);

var i,n:integer;

begin

n:=strtoint(edit1.Text);

matr1.ColCount:=n+1;

matr1.RowCount:=n+1;

kol:=n;

for i:=1 to n do

begin

matr1.Cells[0,i]:=inttostr(i);

matr1.Cells[i,0]:=inttostr(i);

matr1.Cells[i,i]:='%';

end;

end;

//Кнопка "Найти  кротчайший путь"

Procedure Tkomi.Button3Click(Sender: TObject);

begin Alg2 end;

//Кнопка "Закрыть  приложение

Procedure Tkomi.Button4Click(Sender: TObject); 
 
 
 
 
 
 
 

Литература.  

• Пайерлс  Р., Построение физических моделей, УФН, 1983, № 6

• Самарский  А. А., Михайлов А. П. Математическое моделирование. Идеи. Методы. Примеры.. — 2-е изд., испр.. — М.: Физматлит, 2001.

• Горбань  А. Н., Хлебопрос Р. Г., Демон Дарвина: Идея оптимальности и естественный отбор. — М: Наука. Гл ред. физ.-мат. лит., 1988

• Арнольд  В. И. Жёсткие и мягкие математические модели. — М.: МЦНМО, 2004