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

1. Метод ближайшего соседа.

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

Достоинство данного метода – простота и очевидность. Недостаток – большая величина ошибки.

Где LБС – длина цикла построенного методом ближайшего соседа.

LОП – длина действительно оптимального участка

n – количество вершин графа

2. Метод обхода наименьшего остового дерева.

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

Общие этапы алгоритма;

0) Заданный взвешенный ориентированный полный граф преобразуется в неориентированный взвешенный полный граф по принципу

Рис 4.14. Преобразование ориентированного графа в неориентированный.

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

1) Строится остовое дерево наименьшего веса для преобразованного неориентированного графа

Рис 4.15. Остовое дерево наименьшего веса.

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

Рис.4.16. Маршрут обхода наименьшего остового дерева.

3. Метод полного перебора.

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

Метод ветвей и границ.

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

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

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

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

При поиске методом ветвей и границ оптимального гамильтонова цикла исходный узел решений – это все возможные гамильтоновы циклы, даже ещё не сформированные.

Разбиение узла производится по дуге, которая включается в маршрут, т.е. все исходное множество маршрутов разбивается на две группы: группу которая включает некоторую дугу узел Х,У и группу маршрутов, которые не включают некоторую дугу . Затем производится разбиение узла Х,У относительно новой дуги и т.д. пока не будет сформирован конкретный маршрут.

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

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

Нижняя граница, при уточнении узла приближается к длине реального маршрута.

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

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

Пусть дан полный взвешенный граф G<V,U>,

Дана матрица смежности для данного графа Т(6,6)

	1	2	3	4	5	6
1	∞	26	43	16	30	26
2	7	∞	16	1	30	30
3	20	13	∞	35	5	6
4	21	16	25	∞	18	18
5	12	46	27	48	∞	5
6	23	5	5	9	5	∞

Этапы алгоритма метода ветвей и границ.

Этап 0.

Выбрать произвольный маршрут, подсчитать его длину. Принять вычисленную дугу в качестве верхней границы - ВГ. Вычисление верхней границы произвести методом «ближайшего соседа». В качестве текущей матрицы смежности D_T взять матрицу смежности Т, соответствующую исходному графу. Установить номер формируемого узла L=0.

М_БС=1-4-2-3-5-6-1

L_БС=16+16+16+5+5+23=81

Этап 1. Редуцирование текущей матрицы смежности. Расчет нижней границы.

Редуцировать строки матрицы D_T, то есть выявить в каждой i-ой строке наименьшее значение A_i, и вычесть его из всех значений строки.

Рис 4.17. Редуцирование матрицы смежности по строкам.

Редуцировать столбцы матрицы D_T, то есть выявить в каждом j-ом столбце наименьшее значение B_j, и вычесть его из значений всех элементов j-ого столбца.

	1	2	3	4	5	6
1	∞	10	27	0	14	10
2	6	∞	15	0	29	29
3	15	8	∞	30	0	1
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

	1	2	3	4	5	6
1	∞	10	27	0	14	10
2	1	∞	15	0	29	29
3	10	8	∞	30	0	1
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

Bj

5

0

0

0

0

0

Рис 4.18. Редуцирование матрицы смежности по столбцам.

Рассчитать нижнюю границу для текущего узла – НГ. Нижняя граница рассчитывается как сумма всех чисел, на которые редуцировалась ему соответствующая матрица:

Нг_i= Нг^ + ∑A_i + ∑B_j

где Нг^ - нижняя граница предшествующего узла на дереве решений.

∑A_i – суммарное значение на которое была проведено редуцирование по строкам.

∑B_j – суммарное значение на которое было проведено редуцирование по столбцам.

Для исходного узла решений Нг^=0., следовательно

Нг₀=0+48+5=53

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

Этап 2. Выбор очередной узловой дуги, то есть дуги включаемой в маршрут.

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

Оценка предполагаемого удлинения маршрута, при невключении в него какой либо дуги производится в виде расчета штрафов за невключение дуги. Для каждой нулевой дуги рассчитывается составляющая штрафа по строке E_i и по столбцу F_j.

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

	1	2	3	4	5	6
1	∞	10	27	0	14	10
2	1	∞	15	0	29	29
3	10	8	∞	30	0	1
4	0	0	9	∞	2	2
5	7	41	22	43	∞	0
6	13	0	0	4	0	∞

Ei

10

1 Дуга с наибольшим штрафом

1

0

2

0

Fj

1

0

9

0

0

1

Рис 4.19. Определение дуги с наибольшим штрафом

Дуга, имеющая максимальный штраф за не включение - <1,4>. Таким образом, в качестве узловой дуги выбираем дугу <1,4>

Этап 3. Формирование узлов решений.

Текущий узел решений разбивается на два узла. На узел с соответствующим маршрутом, включающим выбранную узловую дугу X,Y, (узел 14) и узел, который соответствует маршрутам невключающим выбранную узловую дугу (узел 14).

Рис 4.20. Формирование узлов решения.

Этап 4. Расчет характеристик узла (XY), то есть для узла не включающего выбранную дугу.

Рассчитывается нижняя граница для узла (XY),

Нг_(XY) =Нг^+Ш_(XY)     , Нг₍₁₄₎=53 +10=63;

Запоминается узел XY (не включающий дугу XY) и его характеристики:

L – номер узла, L=L+1;

D_l –матрица смежности узла решений. XY ,  D_l = D_T(XY), где D_T(XY) – текущая матрица смежности, в которой вес дуги XY установлен - ∞ (бесконечность).

Этап 5. Формирование текущей матрицы смежности для узла XY.

В рассматриваемом примере – узла 14. Матрица смежности D_{T (X,Y)} формируется из матрицы смежности D_T^ с помощью следующих преобразований:

• Матрица D_T вычеркивается строка X и столбец Y, т.к. необходимо исключить в дальнейшем выбор дуг начинающихся в вершине X и заканчивающихся в вершине Y.

• Для дуги обратной X,Y – Y,X устанавливается вес ∞

• Устанавливается вес ∞ для дуг, образующих замкнутые контуры (циклы) с ранее выбранными дугами.

В результате преобразований получены следующая матрица.

	1	2	3	5	6
2	1	∞	15	29	29
3	10	8	∞	0	1
4	∞	0	9	2	2
5	7	41	22	∞	0
6	13	0	0	0	∞

Этап 6. Проверка условий завершения.

Если в D_T дуг больше нет,

то: все дуги маршрута выявлены, рассчитать длину маршрута L:

L= Нг^ + D_T(XY), (в примере до этого пока далеко)

где D_T(XY) -  вес последней дуги текущей матрицы смежности.

Если L<Вг, то принять Вг=L.

Если нет узлов решений таких, что Нг<Вг, то сформированный маршрут является оптимальным - закончить алгоритм

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

иначе(то есть не все дуги маршрута выявлены): сформированный узел , (в данном случае узел 14) принимается за текущий, переход к этапу 1;

В рассматриваемом примере дуги в матрице ещё есть, следовательно переходим к Этапу 1.

Этап 1(повтор2) – Редуцирование матрицы D₁₄ и нахождение нижней границы для текущего узла.

	1	2	3	5	6
2	1	∞	15	29	29
3	10	8	∞	0	1
4	∞	0	9	2	2
5	2	41	22	∞	0
6	13	0	0	0	∞

Ai

1

0

0

0

0

	1	2	3	5	6
2	0	∞	14	28	28
3	10	8	∞	0	1
4	∞	0	9	2	2
5	2	41	22	∞	0
6	13	0	0	0	∞

Bj

0

0

0

0

0

Находим нижнюю границу для узла 14

Нг₁₄= Нг^ + ∑A_i + ∑B_j=53+1+0=54;

Этап 2 (повтор2) Выбор узловой дуги в текущем узле.

Рассчитываем составляющие штрафов по строкам E_i и столбцам F_j.

	1	2	3	5	6
2	0	∞	14	28	28
3	10	8	∞	0	1
4	∞	0	9	2	2
5	2	41	22	∞	0
6	13	0	0	0	∞

Ei

14

1

0

7

0

Fj

2

0

9

0

1

Рассчитываем штрафы для всех дуг с нулевым весом.

Ш₂₁=14+2=16 , Ш₃₅=0+1=1, Ш₄₂=0+0=0, Ш₅₆=1+7=8,

Ш₆₂=0+0=0 , Ш₆₃=0+9=9, Ш₆₅=0+0=0

Дуга с максимальным штрафом = 16 – дуга (2,1). – принимается в качестве узловой.

Этап 3(повтор2). Формируем узел решения – разбиваем текущий узел решения включающий дугу (1,4) на два узла: включающим и невключающим в маршрут дугу (2,1).

Этап 4(повтор2). Расчёт нижней границы для узла 21

Нг₍₂₁₎ =Нг^+Ш₂₁ = 54 +16=70;

Запоминается узел 21 (не включающий дугу 21) и его характеристики:

L – номер узла, L=3+1=4;

D_l –матрица смежности узла решений. 21 ,  D_l = D_T(21), где D_T(21) – текущая матрица смежности, то есть матрица узла 14, в которой вес дуги 21 установлен - ∞ (бесконечность).

Этап 5 (повтор 2) Формирование матрицы смежности для узла 21.

1. Вычеркиваем из матрицы строку 2 и столбец 1.

2. Для дуги обратной 21, то есть для дуги 12 устанавливаем вес ∞ (бесконечность). Но такой дуги нет.

3. Для дуги, которая образует цикл с ранее выбранными дугами устанавливаем вес ∞ (бесконечность). Выбраны дуги <14> <21>. Они образуют цепь. <21><14> . Дуги <42> замыкает данную цепь. Для данной дуги устанавливается вес ∞;

	2	3	5	6
3	8	∞	0	1
4	∞	9	2	2
5	41	22	∞	0
6	0	0	0	∞

Этап 6(повтор 2). Проверка условии завершения.

Дуги в матрице ещё остались, следовательно переходим к этапу 1.

Этап 1(повтор3) – Редуцирование матрицы D₂₁.

	2	3	5	6
3	8	∞	0	1
4	∞	9	2	2
5	41	22	∞	0
6	0	0	0	∞

Ai

0

2

0

0

	2	3	5	6
3	8	∞	0	1
4	∞	7	0	0
5	41	22	∞	0
6	0	0	0	∞

Bj

0

0

0

0

Находим нижнюю границу для узла (21)

Нг₂₁= Нг^ + ∑A_i + ∑B_j=54+2+0=56;

Этап 2 (повтор3) Выбор узловой дуги в текущем узле.

Рассчитываем составляющие штрафов по строкам E_i и столбцам F_j.

	2	3	5	6
3	8	∞	0	1
4	∞	7	0	0
5	41	22	∞	0
6	0	0	0	∞

Ei

1

0

22

0

Fj

8

7

0

0

Рассчитываем штрафы для всех дуг с нулевым весом.

Ш₃₅=1+0=1 , Ш₄₅=0+0=0, Ш₄₆=0+0=0,

Ш₅₆=0+22=0 , Ш₆₂=8+0=8, Ш₆₃=7+0=7, Ш₆₅=0+0=0

Определяем дугу с максимальным штрафом – дуга <6,2>. Выбираем её в качестве узловой.

Этап 3(повтор2)

Формируем узел решения – разбиваем текущий узел решения, включающий дугу <2,1> на два узла: включающий и не включающим в маршрут дугу <6,2>.

Этап 4(повтор2). Определение параметров узла 62

Нижняя граница для узла 62

Нг₍₆₂₎ =Нг^+Ш₍₆₂₎ =56 +8=70;

Запоминается узел 62 и его характеристики:

L – номер узла, L=5+1=6;

D_l –матрица смежности узла решений. 62 ,  D_l = D_T(62), где D_T(62) – текущая матрица смежности, то есть матрица узла 21, в которой вес дуги 62 установлен - ∞ (бесконечность).

Этап 5 (повтор 2) Формирование матрицы смежности для узла 62.

1. Вычеркиваем из матрицы строку 6 и столбец 2.

2. Для дуги обратной 62, то есть для дуги 26 устанавливаем вес ∞ (бесконечность). Но такой дуги нет.

3. Для дуги, которая образует цикл с ранее выбранными дугами устанавливаем вес ∞ (бесконечность). Выбраны дуги <14> <21><62> . Они образуют цепь - <62> <21><14> . Дугa <46> замыкает данную цепь. Для данной дуги устанавливается вес ∞;

	3	5	6
3	∞	0	1
4	7	0	∞
5	22	∞	0

Этап 6(повтор 2). Проверка условии завершения.

Дуги в матрице ещё остались, следовательно переходим к этапу 1.

Этап 1(повтор3) - Редуцируем матрицу D₆₂ по строкам и столбцам.

	3	5	6
3	∞	0	1
4	7	0	∞
5	22	∞	0

Ai

0

0

0

	3	5	6
3	∞	0	1
4	0	0	∞
5	15	∞	0

Bj

7

0

0

Находим нижнюю границу для узла (62)

Нг₆₂= Нг^ + ∑A_i + ∑B_j=56+0+7=63;

Этап 2 (повтор3) Выбор узловой дуги в текущем узле.

Рассчитываем составляющие штрафов по строкам E_i и столбцам F_j.

	3	5	6
3	∞	0	1
4	0	0	∞
5	15	∞	0

Ei

1

0

15

Fj

15

0

1

Рассчитываем штрафы для всех дуг с нулевым весом.

Ш₃₅=1+0=1 , Ш₄₃=15+0=15, Ш₄₅=0+0=0,

Ш₅₆=0+15=15

Выявлено две дуги с максимальным штрафом = 15, дуга <4,3> и дуга <5,6> . В качестве узловой выбираем первую выявленную дугу с штрафом 15, то есть дугу <4,3> .

Этап 3(повтор3)

Формируем узел решения – разбиваем текущий узел решения включающий дугу <6,2> на два узла: включающий и не включающий в маршрут дугу <4,3>.

Этап 4(повтор3)

Рассчитать нижнюю границу для узла для узла (43)

Нг₍₄₃₎ =Нг^+Ш₍₄₃₎ =63 +15=78;

Запоминается узел 43 (не включающий дугу 43) и его характеристики:

L – номер узла, L=7+1=9;

D_l –матрица смежности узла решений. 43 ,  D_l = D_T(43), где D_T(43) – текущая матрица смежности, то есть матрица узла 62, в которой вес дуги 43 установлен - ∞ (бесконечность).

Этап 5 (повтор 3) Формирование матрицы смежности для узла 43.

1. Вычеркиваем из матрицы строку 4 и столбец 3.

2. Для дуги обратной 43, то есть для дуги 34 устанавливаем вес ∞ (бесконечность). Но такой дуги нет.

3. Для дуги, которая образует цикл с ранее выбранными дугами устанавливаем вес ∞ (бесконечность). Выбраны дуги <14> <21><62> <43> . Они образуют цепь - <62> <21><14><43> . Дугa <36> замыкает данную цепь. Для данной дуги устанавливается вес ∞;

	5	6
3	0	∞
5	∞	0

Этап 6(повтор 3). Проверка условии завершения.

Дуги в матрице ещё остались, следовательно переходим к этапу 1.

этап 1(повтор3) - Редуцируем матрицу D₆₂ по строкам и столбцам.

	5	6
3	0	∞
5	∞	0

Ai

0

0

Bj

0

0

Находим нижнюю границу для узла (43)

Нг₄₃= Нг^ + ∑A_i + ∑B_j=63+0+0=63;

Этап 2 (повтор4) Выбор узловой дуги в текущем узле.

Рассчитываем составляющие штрафов по строкам E_i и столбцам F_j.

	5	6
3	0	∞
5	∞	0

Ei

∞

∞

Fj

∞

∞

Рассчитываем штрафы для всех дуг с нулевым весом.

Ш₃₅=∞+∞=∞ ,

Ш₅₆=∞+∞=∞

Выявлено две дуги с максимальным штрафом = ∞, дуга <3,5> и дуга <5,6> . В качестве узловой выбираем первую выявленную дугу с штрафом ∞, то есть дугу <3,5> .

Этап 3(повтор4)

Формируем узел решения – разбиваем текущий узел решения включающий дугу <4,3> на два узла: включающий и не включающий в маршрут дугу <3,5>.

Этап 4(повтор4)

Рассчитать нижнюю границу для узла для узла (35)

Нг₍₃₅₎ =Нг^+Ш₍₃₅₎ =63 +∞=∞;

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

Этап 5 (повтор 4) Формирование матрицы смежности для узла 35.

1. Вычеркиваем из матрицы строку 3 и столбец 5.

	6
5	0

Этап 6(повтор 4). Проверка условии завершения.

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

Формирование маршрута обхода вершин из дуг, выбранных в процессе работы алгоритма.

При работе алгоритма выбраны следующие множество дуг.

M={<1,4>, <2,1>, <6,2>, <4,3>, <3,5>, <6,2>,<5,6>}

Из данных дуг может быть сформирован цикл, включающий все вершины графа. То есть гамильтонов цикл.

G=< <1,4>, <4,3>,<3,5>, >,<5,6>, <6,2>, <2,1> >

Суммарный вес дуг данного цикла

L =16 + 25 + 5 + 5 + 5 + 7 =63, что совпадает с нижней границей последнего узла Нг₅₆=63.

Суммарный вес дуг найденного гамильтонова цикла принимается в качестве новой верхней границы Вг=63.

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