етс комивояжер

  • 10 апр. 2017 г.
  • 1892 Слова
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 21 + 12 + 31 + 17 + 6 + 6 = 93
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i j
1
2
3
4
5
6
di
1
M
21
37
20
14
42
14
2
15
M
12
3
25
9
3
3
22
12
M31
7
28
7
4
19
6
24
M
17
13
6
5
8
41
23
15
M
6
6
6
6
16
8
11
5
M
5

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j
1
2
3
4
5
6
1
M
7
23
6
0
28
2
12
M
9
0
22
6
3
15
5
M
24
0
21
4
13
0
18
M
11
7
5
2
35
17
9
M
0
6
1
11
3
6
0
M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбценаходим минимальный элемент:
dj = min(i) dij
i j
1
2
3
4
5
6
1
M
7
23
6
0
28
2
12
M
9
0
22
6
3
15
5
M
24
0
21
4
13
0
18
M
11
7
5
2
35
17
9
M
0
6
1
11
3
6
0
M
dj
1
0
3
0
0
0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i j
1
2
3
4
5
6
1
M
7
20
6
0
28
2
11
M
6
0
22
6
3
14
5
M
24
0
21
4
12
0
15
M
11
7
5
1
35
149
M
0
6
0
11
0
6
0
M

Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 14+3+7+6+6+5+1+0+3+0+0+0 = 45
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз ивозвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность)и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j
1
2
3
4
5
6
di
1
M
7
20
6
0(6)
28
6
2
11
M
6
0(12)
22
6
6
3
14
5
M
24
0(5)
21
5
4
12
0(12)
15
M
11
7
7
5
1
35
14
9
M
0(7)
1
6
0(1)
11
0(6)
6
0(0)
M
0
dj
1
5
6
6
0
6
0

d(1,5) = 6 + 0 = 6; d(2,4) = 6 + 6 = 12; d(3,5) = 5 + 0 = 5; d(4,2) = 7 + 5 = 12; d(5,6) = 1 + 6 = 7; d(6,1) = 0 + 1 = 1; d(6,3) = 0 + 6 = 6;d(6,5) = 0 + 0 = 0; 
Наибольшая сумма констант приведения равна (6 + 6) = 12 для ребра (2,4), следовательно, множество разбивается на два подмножества (2,4) и (2*,4*).
Исключение ребра (2,4) проводим путем замены элемента d24 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,4*), в результате получим редуцированную матрицу.
i j
1
2
3
45
6
di
1
M
7
20
6
0
28
0
2
11
M
6
M
22
6
6
3
14
5
M
24
0
21
0
4
12
0
15
M
11
7
0
5
1
35
14
9
M
0
0
6
0
11
0
6
0
M
0
dj
0
0
0
6
0
0
12

Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,4*) = 45 + 12 = 57
Включение ребра (2,4) проводится путем исключения всех элементов 2-ой строки и 4-го столбца, в которой элемент d42 заменяем на М, для исключения образования негамильтонова цикла.
Врезультате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j
1
2
3
5
6
di
1
M
7
20
0
28
0
3
14
5
M
0
21
0
4
12
M
15
11
7
7
5
1
35
14
M
0
0
6
0
11
0
0
M
0
dj
0
5
0
0
0
12

Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 12
Нижняя граница подмножества (2,4) равна:
H(2,4) = 45 + 12 = 57 ≤ 57
Посколькунижняя граница этого подмножества (2,4) меньше, чем подмножества (2*,4*), то ребро (2,4) включаем в маршрут с новой границей H = 57
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них...