Решение задачи коммивояжера методом ветвей и границ

Размещено на http://www.allbest.ru/

Введение

Комбинаторика - раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.

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

Повышение интереса к комбинаторному анализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам.

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

В 1859 г. У. Гамильтон придумал игру “Кругосветное путешествие”, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений - задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем.

В данной курсовой работе разрабатывается программа, позволяющая реализовать алгоритм коммивояжера с помощью языка программирования С++. Я выбрала именно этот язык, так как он поддерживает процедурное программирование, модульность, раздельную компиляцию, обработку исключений и сочетает свойства как высокоуровневых, так и низкоуровневых языков.

комбинаторика коммивояжер программирование



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

Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики.

Постановка задачи следующая.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введём некоторые термины. Итак, города перенумерованы числами jТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j₁,j₂,..,j_n,j₁), причём все j₁..j_n - разные номера; повторяющийся в начале и в конце j₁, показывает, что перестановка зациклена. Расстояния между парами вершин С_ij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

L=L(t)= (1)

Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания.

Во-первых, в постановке С_ij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jТ:

С_ij0; C_jj=?



(последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j:

Сij= Сji.

и удовлетворять неравенству треугольника, т.е. для всех:

Сij+ СjkіCik

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С_ij - не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно - другую). Поэтому различают два варианта задачи коммивояжера: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае (условия (2) и (4) по умолчанию считаются выполненными.) В терминах теории графов симметричную задачу коммивояжера можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i,j)= С_ij. Найти гамильтонов цикл минимальной длины.

В несимметричной задаче коммивояжера вместо “цикл” надо говорить “контур”, а вместо “ребра” - “дуги”.

2. Решение задачи коммивояжера методом ветвей и границ

Основная идея метода

На первом этапе строят нижнюю границу ц длин множества маршрутов Z. Затем множество маршрутов разбивается на два подмножества таким образом, чтобы первое подмножество состояло из маршрутов, содержащих некоторую дугу (i, j), а другое подмножество не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества маршрутов. Полученные нижние границы подмножеств и оказываются не меньше нижней границы множества всех маршрутов, т.е. ц(Z)? ц (), ц(Z) ? ц ().

Сравнивая нижние границы ц () и ц (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

Затем одно из подмножеств или по аналогичному правилу разбивается на два новых и . Для них снова отыскиваются нижние границы ц (), и ц () и т.д. Процесс ветвления продолжается до тех пор, пока не отыщется единственный маршрут. Его называют первым рекордом. Затем просматривают оборванные ветви. Если их нижние границы больше длины первого рекорда, то задача решена. Если же есть такие, для которых нижние границы меньше, чем длина первого рекорда, то подмножество с наименьшей нижней границей подвергается дальнейшему ветвлению, пока не убеждаются, что оно не содержит лучшего маршрута.

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

Для практической реализации метода ветвей и границ применительно к задаче коммивояжера укажем прием определения нижних границ подмножеств и разбиения множества маршрутов на подмножества (ветвление).

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

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

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

Разбиение множества маршрутов на подмножества

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени И_ij нулевых элементов этой матрицы. Степень нулевого элемента И_ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c_ij - не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

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

Множество маршрутов, не включающих дугу (i, j) получаем путем замены элемента c_ij на бесконечность.

Пример задачи

Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:

	A	B	C	D	E	F
A	?	15	54	4	11	17
B	9	?	23	5	6	10
C	19	18	?	37	2	8
D	34	13	25	?	12	18
E	5	56	39	22	?	6
F	14	7	2	10	16	?

Решение задачи

Итерация 1.

Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r₁=4, r₂=5, r₃=2, r₄=12, r₅=5, r₆=2.

После их вычитания по строкам получим:

	1	2	3	4	5	6
1	?	11	50	0	10	13
2	4	?	18	0	1	5
3	17	16	?	35	0	6
4	22	1	13	?	0	6
5	0	51	34	17	?	1
6	12	5	0	8	14	?

Минимумы по столбцам: h₁=0, h₂=1, h₃=h₄=h₅=0, h₆=1.

После их вычитания по столбцам получим приведенную матрицу:

	1	2	3	4	5	6
1	?	10	50	0	10	12
2	4	?	18	0	1	4
3	17	15	?	35	0	5
4	22	0	13	?	0	5
5	0	50	34	17	?	0
6	12	4	0	8	14	?

Найдем нижнюю границу

ц(Z) = 4+5+2+12+5+2+1+1=32.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени И_ij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу).

И₁₄ = 10 + 0, И₂₄ = 1 + 0, И₃₅ = 5+0, И₄₂ = 0 + 4, И₄₅ = 0 + 0, И₅₁ = 4 + 0, И₅₆ = 4 + 0, И₆₃ = 4+13.

Наибольшая степень И₆₃ = 17. Ветвление проводим по дуге (6,3).

Нижняя граница для множества Z₆₃⁽¹⁾остается равной 32. Для всех маршрутов множества Z_63'⁽¹⁾ из города 6 мы не перемещаемся в город 3,

ц (Z_63'⁽¹⁾) = 32 + 4.

В матрице, соответствующей Z₆₃⁽¹⁾, вычеркиваем шестую строку и третий столбец и положим c₃₆= ?, чтобы предотвратить появления цикла 6> 3 > 6. Получим новую платежную матрицу {c¹_ij}:



	1	2	4	5	6
1	?	10	0	10	12
2	4	?	0	1	4
3	17	15	35	0	?
4	22	0	?	0	5
5	0	50	17	?	0

Сравнивая нижние границы ц Z_63'⁽¹⁾=40 и ц Z₆₃⁽¹⁾=32 < 40, выделяем подмножество маршрутов Z₆₃⁽¹⁾, которое с большей вероятностью содержит маршрут минимальной длины.

Итерация 2.

Приведенная платежная матрица для Z₆₃⁽¹⁾ (в каждой сроке и в каждом столбце есть 0, после приведения матрица не меняется):

	1	2	4	5	6
1	?	10	0	10	12
2	4	?	0	1	4
3	17	15	35	0	?
4	22	0	?	0	5
5	0	50	17	?	0

Далее продолжаем процесс ветвления. Найдем степени И_ij нулевых элементов этой матрицы И₁₄ =10, И₂₄ = 1, И₃₅ = 15, И₄₂ = 10, И₄₅ = 0, И₅₁ =4, И₅₆ = 4. Наибольшая степень И₃₅=15. Затем множество Z₆₃⁽¹⁾ разбивается на дуге (3, 5) на два новых Z₃₅⁽²⁾ и Z_35'⁽²⁾.

В матрице для Z₃₅⁽²⁾ вычеркиваем строку 3 и столбец 5. Дуги (6, 3) и (3, 5) образуют связный путь (6, 3, 5); положим c₅₆= ?, чтобы предотвратить появления цикла 6>3> 5 > 6.

	1	2	4	6
1	?	10	0	12
2	4	?	0	4
4	22	0	?	5
	0	50	17	?

Для приведения надо вычесть минимум по столбцу 6: r₆=4. При этом нижняя граница станет равной 32+4=36.

Нижняя граница для Z_35'⁽²⁾, полученная как на предыдущем шаге ветвления, равна 32 + 15 = 47. Сравнивая нижние границы ц Z₃₅⁽²⁾=36 и Z_35'⁽²⁾=47>36 выбираем для дальнейшего разбиения подмножество маршрутов Z₃₅⁽²⁾.

Итерация 3.

Приведенная платежная матрица для Z₃₅⁽²⁾:

	1	2	4	6
1	?	10	0	8
2	4	?	0	0
4	22	0	?	1
5	0	50	17	?

Степени И_ij нулевых элементов этой матрицы И₁₄ = 8, И₂₄ = 0, И₂₆ = 1, И₄₂ = 10, И₅₁ =21. Наибольшая степень И₅₁=21_. Затем множество Z₃₅⁽²⁾ разбивается на два новых Z₅₁⁽³⁾ и Z_51'⁽³⁾.

Нижняя граница для Z_51'⁽³⁾ равна 36+21=57. В матрице для Z₅₁⁽³⁾ вычеркиваем строку 5 и столбец 1, положим с₁₆=?. Получим матрицу:

	2	4	6
1	10	0	?
2	?	0	0
4	0	?	1

Приведение не требуется. Выбираем для дальнейшего разбиения подмножество маршрутов Z₅₁⁽³⁾.

Итерация 4.

Приведенная платежная матрица для Z₅₁⁽³⁾:



	2	4	6
1	10	0	?
2	?	0	0
4	0	?	1

Степени И_ij нулевых элементов этой матрицы И₁₄ = 8, И₂₄ = 0, И₂₆ = 1, И₄₂ =11. Выбираем И₄₂ =11. Разбиваем Z₅₁⁽³⁾ на Z₄₂⁽⁴⁾ и Z_42'⁽⁴⁾.

Нижняя граница для Z_42'⁽⁴⁾ равна 36+11 = 47. В матрице для Z₄₂⁽⁴⁾ вычеркиваем строку 4 и столбец 2 и полагаем c₂₄= ?. Получим

	4	6
1	0	?
2	?	0

Приведение не требуется.

Из матрицы 22 получаем два перехода с нулевой длиной: (1, 4) и (2, 6).

Полученный маршрутом коммивояжера: Z₀ = (1, 4, 2, 6, 3, 5, 1) или (A-D-B-F-C-E-A).

Пройденный путь равен 36.

Руководство пользователя

1. Введите размерность матрицы.

2. Ведите поэлементно взвешенную матрицу смежности.

3. Результат работы программы:



4. Введите источник.

5. Результат работы программы:



Заключение

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

Задача коммивояжера является одной из самых важнейших задач в теории графов. Возможность представления (записи) различных производственных процессов на языке теории графов и умение решить сформулированную математическую задачу позволяют найти оптимальную стратегию ведения хозяйства, сэкономить ресурсы, выполнить поставленную задачу в более короткие сроки. Для решения оптимизационных и других задач строительства нередко прибегают к формулировке поставленной задачи в виде каких-то хорошо известных математических задач: транспортная задача, задача поиска оптимального пути (задача коммивояжера) и другие. Сформулированную таким образом задачу решают, используя такие математические методы, как метод ветвей и границ, симплексный метод, метод Фогеля (приближенного решения), метод дефектов и другие методы.



Приложение

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

1. Функция main

#include <iostream>

#include "matrixio.h"

#include "privedenie.h"

#include "trans.h"

#include <iomanip>

using namespace std;

int main()

{

const int inf=1000;

int Matrix[100][100],versh[2][100],versh1[2][100],temp[100][100];

int n=6,sum,Pt=0,f=0,t,st,d,s;

cout <<"Vvedite n"<<endl<<"n=";

cin >> n;

matrixio(n, Matrix, true);

cout<<endl;

cout<<"Ishodnaya matrica:"<<endl;

matrixio(n, Matrix, false);

for (int i=0; i<2; i++)

{

for (int j=0; j<n; j++)

{

versh[i][j]=0;

}

}

cout<<endl;//Ввод-вывод исходной матрицы

do {

sum=0;

for (int i=0; i<n; i++)

{

for (int j=0; j<n;j++)

{

sum=sum+Matrix[i][j];

}

}

if (sum%inf==0)

{

f=f+1;

break;

}

cout<<"Iteracia "<<f+1<<":"<<endl;

minstr (n, Pt, Matrix);

minst (n, Pt, Matrix);

cout<<endl;

int vblchstr,vblchst;//Присвоение меток

int mt[3][100];

d=0;

for (int i=0; i<n; i++)

{

for (int j=0; j<n; j++)

{

if (Matrix[i][j]==0)

{

int k=i;

int m=j;

int mini=Matrix[k][k];

for (int j=0; j<n; j++)

{

if ((Matrix[k][j]<=mini) && (j!=m))

{

if (Matrix[k][j]!=inf) mini=Matrix[k][j];

else mini=0;

}

}

trans(n, Matrix, temp);

int minj=temp[m][m];

for (int j=0; j<n; j++)

{

if ((temp[m][j]<=minj) && (j!=k))

{

if (temp[m][j]!=inf) minj=temp[m][j];

else minj=0;

}

}

s=mini+minj;

mt[0][d]=s;//метка

mt[1][d]=k;//строка, в которой она находится

mt[2][d]=m;//столбец, в котором она находится

d=d+1;

}

}

}

cout<<"Matrica metok:"<<endl;

for (int i=0; i<3; i++)

{

for (int j=0; j<d; j++)

{

cout<<mt[i][j]<<" ";

}

cout<<endl;

}

cout<<endl;

int maxel=mt[0][0];

for (int j=0; j<d; j++)//Поиск максимальной метки

{

if (mt[0][j]>=maxel)

{

maxel=mt[0][j];

st=j;//st-столбец, в котором обнаружена макc. метка

}

}

vblchstr=mt[1][st];

vblchst=mt[2][st];

trans( n, Matrix, temp);

for (int j=0; j<n; j++) temp[vblchst][j]=inf;//вычерки. столбца и строки, где была

snart( n, Matrix, temp);

for (int j=0; j<n; j++) Matrix[vblchstr][j]=inf;//обнаружена максимальная метка,и элемента,

Matrix[vblchst][vblchstr]=inf;

cout<<"Matrica:"<<endl;

matrixio(n, Matrix, false);

versh[0][f]=vblchstr;//симметр. найденному относ.гл. диагонали во избежание зацикливания

versh[1][f]=vblchst;//Занесение вычерк. координат в массив вершин

for (int i=0; i<2; i++)//Начало избавления от элемента,

{//который может вызвать зацикливание

for (int f=0; f<n; f++)

{

versh1[i][f]=versh[i][f];

}

}

for (int i=0; i<2; i++)

{

for (int q=0; q<n; q++)

{

for (int f=0; f<n; f++)

{

if ((versh1[0][f]==versh1[1][q]) && (versh1[0][f]!=inf))

{

versh1[0][f]=inf;

versh1[1][q]=inf;

}

}

}

}

cout<<endl;

int sv;

if (f!=n-3)

{

do

{

sv=0;

int v1=0, v2=0;

for (int f=0; f<n; f++)

{

if (versh1[0][f]!=inf)

{

v1=versh1[0][f];

versh1[0][f]=inf;

}

}

for (int f=0; f<n; f++)

{

if (versh1[1][f]!=inf)

{

v2=versh1[1][f];

versh1[1][f]=inf;

}

}

Matrix[v2][v1]=inf;

for (int i=0; i<2; i++)

{

for (int f=0; f<n;f++)

{

sv=sv+versh1[i][f];

}

}

}

while (sv!=2*n*inf);

}

f=f+1;//конец

}

while (f!=n-2);

for (int i=0; i<n; i++)

{

for (int j=0; j<n;j++)

{

if (Matrix[i][j]==0)

{

versh[0][f]=i;

versh[1][f]=j;

f=f+1;

}

}

}

cout.unsetf (ios::right);

cout.setf(ios::left);

for (int i=0; i<2; i++)

{

for (int j=0; j<n; j++)

{

cout<<versh[i][j]<<setw(4);

}

cout<<endl;

}

cout<<" - matrica metok."<<endl;

cout<<endl;

cout <<"Vvedite istochnic:"<<endl<<"t=";

cin >> t;//Вывод маршрута

cout<<endl;

if (t>n) cout <<"Necorrektnoe znachenie istochnika.";

else

{

cout<<"Marshrut:"<<endl;

for (int f=0; f<n; f++)

{

if (versh[0][f]==t-1)

{

cout<<versh[0][f]+1<<"-->"<<versh[1][f]+1<<"-->";

t=versh[1][f];

versh[0][f]=inf;

versh[1][f]=inf;break;

}

}

int l;

do

{

l=0;

for (int f=0; f<n; f++)

{

if (versh[0][f]==t)

{

cout<<versh[1][f]+1<<"-->";

t=versh[1][f];

versh[0][f]=inf;

versh[1][f]=inf;

}

}

for (int i=0; i<2; i++)

{

for (int j=0; j<n;j++)

{

l=l+versh[i][j];

}

}

}

while (l!=(2*n*inf));

cout<<" eto marshrut.";

cout<<endl;

cout<<"Proidennii put = "<< Pt<<endl;// Вывод пути*/

}

return 1;

}

2. Модуль matrixio

#include <iostream>

#include <matrixio.h>

#include <iomanip>

using namespace std;

void matrixio (int n, int M[][100], bool input)

{

cout.setf(ios::right);

const int inf=1000;

if (input==true)

{

for (int i=0; i<n; i++)

{

for (int j=0; j<n; j++)

{

cout <<"Vvedite element(elementi po diagonali ravnbl beskonechnosti) #"<<i+1<<" "<<j+1<<endl;

cin >>M[i][j];

}

}

}

else

{

for (int i=0; i<n; i++)

{

for (int j=0; j<n; j++)

{

if (M[i][j]==1000) cout<<" inf"<<setw(4);

else

{

cout <<M[i][j]<<setw(4);

}

}

cout << endl;

}

}

}

3. Модуль privedenie

#include <iostream>

#include "privedenie.h"

#include "trans.h"

using namespace std;

int minstr (int n, int &Pt,int M[100][100])

{

const int inf=1000;

int S[100];

for (int i=0; i<n; i++)

{

for (int j=0; j<n; j++)

{

S[j]=M[i][j];

}

int min=S[0];

for (int j=0; j<n; j++)

{

if ((S[j]!=inf)&& (S[j]<=min)) min=S[j];

}

if (min!=inf) Pt+=min;

if (min!=0)

{

for (int j=0; j<n;j++)

{

if (S[j]!=inf) S[j]=S[j]-min;

}

}

for (int j=0; j<n;j++) M[i][j]=S[j];

}

return Pt;

}

int minst (int n, int & Pt, int M[100][100])

{

int temp[100][100];

trans(n, M, temp);

minstr (n, Pt,temp);

snart(n, M, temp);

return Pt;

}

4. Модуль trans

#include <iostream>

#include "trans.h"

using namespace std;

float trans(int n, int M[100][100], int temp[100][100])

{

for (int i=0; i<n; i++)

{

for (int j=0; j<n; j++)

temp[i][j]=M[j][i];

}

}

float snart(int n, int M[100][100], int temp[100][100])

{

for (int i=0; i<n; i++)

{

for (int j=0; j<n; j++)

M[i][j]=temp[j][i];

}

}

Размещено на Allbest.ru

...