Задача 5

Умова:

Комівояжер повинен об’їздити 5 міст. Для того щоб скоротити витрати, він хоче побудувати такий маршрут, щоб об’їздити всі міста точно по одному разу і повернутися у вихідний з мінімумом витрат. Вихідне є місто A. Витрати на переміщення між містами задачі наступної матрицею:

Місто	A	B	C	D	E
A	∞	9	15	10	4
B	3	∞	10	6	2
C	6	3	∞	14	2
D	5	23	10	∞	7
E	16	3	4	7	∞

Розв’язання:

Візьмемо як довільного маршруту:

X₀ = (1,2);(2,3);(3,4);(4,5);(5,1)

Тоді F(X₀) = 9 + 10 + 14 + 7 + 16 = 56

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

d_i = min(j) d_ij

i j	1	2	3	4	5	di
1	∞	9	15	10	4	4
2	3	∞	10	6	2	2
3	6	5	∞	14	2	2
4	5	23	10	∞	7	5
5	16	3	4	7	∞	3

Потім відняти його з елементів розглянутої рядка. У зв'язку з цим у знову отриманої матриці в кожному рядку буде як мінімум один нуль.

i j	1	2	3	4	5
1	M	5	11	6	0
2	1	M	8	4	0
3	4	3	M	12	0
4	0	18	5	M	2
5	13	0	1	4	M

Потім таку ж операцію редукції проводимо по стовпцях, для чого в кожному стовпці знаходимо мінімальний елемент:

d_j=min(i) d_ij

i j	1	2	3	4	5
1	∞	5	11	6	0
2	1	∞	8	4	0
3	4	3	∞	12	0
4	0	18	5	∞	2
5	13	0	1	4	∞
dj	0	0	1	4	0

Після вирахування мінімальних елементів отримуємо повністю скороченої матрицю, де величини d_i i d_j називаються константами приведення.

i j	1	2	3	4	5
1	∞	5	10	2	0
2	1	∞	7	0	0
3	4	3	∞	8	0
4	0	18	4	∞	2
5	13	0	0	0	∞

Сума констант приведення визначає нижню межу H:

H = 4+2+2+5+3+0+0+1+4+0 = 21

Елементи матриці d_ij відповідають відстані від пункту i до пункту j. Оскільки в матриці n міст, то D є матрицею nxn з невід'ємними елементами d_ij >=0. Кожен допустимий маршрут являє собою цикл, за яким комівояжер відвідує місто тільки один раз і повертається у вихідний місто.

Довжина маршруту визначається виразом:

Причому кожен рядок і стовпець входять в маршрут тільки один раз з елементом d_ij. Визначаємо ребро розгалуження і розіб'ємо вся безліч маршрутів щодо цього ребра на дві підмножини (i,j) и (i*,j*).

З цією метою для всіх клітин матриці з нульовими елементами замінюємо по черзі нулі на М (нескінченність) і визначаємо для них суму утворилися констант приведення, вони наведені в дужках.

i j	1	2	3	4	5	di
1	M	5	10	2	0(2)	2
2	1	M	7	0(0)	0(0)	0
3	4	3	M	8	0(3)	3
4	0(3)	18	4	M	2	2
5	13	0(3)	0(4)	0(0)	M	0
dj	1	3	4	0	0	0

d(1,5) = 2 + 0 = 2; d(2,4) = 0 + 0 = 0; d(2,5) = 0 + 0 = 0; d(3,5) = 3 + 0 = 3; d(4,1) = 2 + 1 = 3; d(5,2) = 0 + 3 = 3; d(5,3) = 0 + 4 = 4; d(5,4) = 0 + 0 = 0;

Найбільша сума констант приведення дорівнює (0 + 4) = 4 для ребра (5,3), отже, безліч розбивається на дві підмножини (5,3) i (5*,3*).

Нижня межа гамільтонових циклів цього підмножини:

H(5*,3*) = 21 + 4 = 25

Виняток ребра (5,3) проводимо шляхом заміни елемента d₅₃ = 0 на M, після чого здійснюємо чергове приведення матриці відстаней для утворився підмножини (5*,3*), в результаті отримаємо скороченої матрицю.

i j	1	2	3	4	5	di
1	M	5	10	2	0	0
2	1	M	7	0	0	0
3	4	3	M	8	0	0
4	0	18	4	M	2	0
5	13	0	M	0	M	0
dj	0	0	4	0	0	4

Включення ребра (5,3) проводиться шляхом виключення всіх елементів 5-ої строки і 3-го стовпця, в якій елемент d₃₅ замінюємо на М, для запобігання утворенню негамільтонового циклу. В результаті отримаємо іншу скорочену матрицю (4 x 4), яка підлягає операції приведення.

Сума констант приведення скороченою матриці:

Після операції приведення скорочена матриця буде мати вигляд:

i j	1	2	4	5	di
1	M	5	2	0	0
2	1	M	0	0	0
3	4	3	8	M	3
4	0	18	M	2	0
dj	0	3	0	0	6

Нижня межа підмножини (5,3) дорівнює:

H(5,3) = 21 + 6 = 27 > 25

Оскільки нижня межа цієї підмножини (5*,3*) більше, ніж підмножини (5,3), то ребро (5*,3*) включаємо в маршрут. Визначаємо ребро розгалуження і розіб'ємо вся безліч маршрутів щодо цього ребра на дві підмножини (i,j) и (i*,j*). З цією метою для всіх клітин матриці з нульовими елементами замінюємо по черзі нулі на М (нескінченність) і визначаємо для них суму утворилися констант приведення, вони наведені в дужках.

i j	1	2	3	4	5	di
1	M	5	10	2	0(2)	2
2	1	M	7	0(0)	0(0)	0
3	1	0(1)	M	5	M	1
4	0(3)	18	4	M	2	2
5	13	0(0)	0(4)	0(0)	M	0
dj	1	0	4	0	0	0

d(1,5) = 2 + 0 = 2; d(2,4) = 0 + 0 = 0; d(2,5) = 0 + 0 = 0; d(3,2) = 1 + 0 = 1; d(4,1) = 2 + 1 = 3; d(5,2) = 0 + 0 = 0; d(5,3) = 0 + 4 = 4; d(5,4) = 0 + 0 = 0;

Найбільша сума констант приведення дорівнює (0 + 4) = 4 для ребра (5,3), отже, безліч розбивається на дві підмножини (5,3) i (5*,3*).

Нижня межа гамільтонових циклів цього підмножини:

H(5*,3*) = 25 + 4 = 29

Виняток ребра (5,3) проводимо шляхом заміни елемента d₅₃ = 0 на M, після чого здійснюємо чергове приведення матриці відстаней для утворився підмножини (5*,3*), в результаті отримаємо скороченої матрицю.

i j	1	2	3	4	5	di
1	M	5	10	2	0	0
2	1	M	7	0	0	0
3	1	0	M	5	M	0
4	0	18	4	M	2	0
5	13	0	M	0	M	0
dj	0	0	4	0	0	4

Включення ребра (5,3) проводиться шляхом виключення всіх елементів 5-ої строки і 3-го стовпця, в якій елемент d₃₅ замінюємо на М, для запобігання утворенню негамільтонова циклу. В результаті отримаємо іншу скорочену матрицю (4 x 4), яка підлягає операції приведення.

Сума констант приведення скороченою матриці:

Після операції приведення скорочена матриця буде мати вигляд:

i j	1	2	4	5	di
1	M	5	2	0	0
2	1	M	0	0	0
3	1	0	5	M	0
4	0	18	M	2	0
dj	0	0	0	0	0

Нижня межа підмножини (5,3) дорівнює:

H(5,3) = 25 + 0 = 25 < 29

Оскільки нижня границя цього підмножника (5,3) менша, ніж підмножників (5*,3*), то ребро (5,3) включаємо в маршрут. Визначаємо ребро розгалуження і розіб'ємо вся безліч маршрутів щодо цього ребра на дві підмножини (i,j) и (i*,j*). З цією метою для всіх клітин матриці з нульовими елементами замінюємо по черзі нулі на М (нескінченність) і визначаємо для них суму утворилися констант приведення, вони наведені в дужках.

i j	1	2	4	5	di
1	M	5	2	0(2)	2
2	1	M	0(2)	0(0)	0
3	1	0(6)	5	M	1
4	0(3)	18	M	2	2
dj	1	5	2	0	0

d(1,4) = 2 + 0 = 2; d(2,3) = 0 + 2 = 2; d(2,4) = 0 + 0 = 0; d(3,2) = 1 + 5 = 6; d(4,1) = 2 + 1 = 3;

Найбільша сума констант приведення дорівнює (1 + 5) = 6 для ребра (3,2), отже, безліч розбивається на дві підмножини (3,2) i (3*,2*).

Нижня межа гамільтонових циклів цього підмножини:

H(3*,2*) = 25 + 6 = 31

Виняток ребра (3,2) проводимо шляхом заміни елемента d₃₂ = 0 на M, після чого здійснюємо чергове приведення матриці відстаней для утворився підмножини (3*,2*), в результаті отримаємо скороченої матрицю.

i j	1	2	4	5	di
1	M	5	2	0	0
2	1	M	0	0	0
3	1	M	5	M	1
4	0	18	M	2	0
dj	0	5	0	0	6

Включення ребра (3,2) проводиться шляхом виключення всіх елементів 3-ої строки і 2-го стовпця, в якій елемент d₂₃ замінюємо на М, для запобігання утворенню негамільтонова циклу. В результаті отримаємо іншу скорочену матрицю (3 x 3), яка підлягає операції приведення.

Сума констант приведення скороченою матриці:

Після операції приведення скорочена матриця буде мати вигляд:

i j	1	4	5	di
1	M	2	0	0
2	1	0	0	0
4	0	M	2	0
dj	0	0	0	0

Нижня межа підмножини (3,2) дорівнює:

H(3,2) = 25 + 0 = 25 < 31

Щоб виключити підцикли, заборонимо наступні переходи: (2,5),

Оскільки нижня межа цього підмножника (3,2) менша, ніж підмножника (3*,2*), то ребро (3,2) включаємо в маршрут. Визначаємо ребро розгалуження і розіб'ємо вся безліч маршрутів щодо цього ребра на дві підмножини (i,j) и (i*,j*). З цією метою для всіх клітин матриці з нульовими елементами замінюємо по черзі нулі на М (нескінченність) і визначаємо для них суму утворилися констант приведення, вони наведені в дужках.

i j	1	4	5	di
1	M	2	0(4)	2
2	1	0(3)	M	1
4	0(3)	M	2	2
dj	1	2	2	0

d(1,3) = 2 + 2 = 4; d(2,2) = 1 + 2 = 3; d(3,1) = 2 + 1 = 3;

Найбільша сума констант приведення дорівнює (2 + 2) = 4 для ребра (1,5), отже, безліч розбивається на дві підмножини (1,5) i (1*,5*).

Нижня межа гамільтонових циклів цього підмножини:

H(1*,5*) = 25 + 4 = 29

Виняток ребра (1,5) проводимо шляхом заміни елемента d₁₅ = 0 на M, після чого здійснюємо чергове приведення матриці відстаней для утворився підмножини (1*,5*), в результаті отримаємо скороченої матрицю.

i j	1	4	5	di
1	M	2	M	2
2	1	0	M	0
4	0	M	2	0
dj	0	0	2	4

Включення ребра (1,5) проводиться шляхом виключення всіх елементів 1-ої строки і 5-го стовпця, в якій елемент d₅₁ замінюємо на М, для запобігання утворенню негамільтонова циклу. В результаті отримаємо іншу скорочену матрицю (2 x 2), яка підлягає операції приведення.

Сума констант приведення скороченою матриці:

Після операції приведення скорочена матриця буде мати вигляд:

i j	1	4	di
2	1	0	0
4	0	M	0
dj	0	0	0

Нижня межа підмножини (1,5) дорівнює:

H(1,5) = 25 + 0 = 25 < 29

Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаємо в маршрут. Згідно з цією матрицею включаємо в Гамільтон маршрут ребра (2,4) i (4,1). В результаті по дереву розгалужень Гамільтоном цикл утворюють ребра:

(5,3), (3,2), (2,4), (4,1), (1,5).

Довжина маршруту дорівнює F(Mk) = 24