загрузка...
Пошук по сайту

Приклад рішення задачі комівояжера

Візьмемо як довільного маршруту:
X0 = (1,2);(2,3);(3,4);(4,1)
Тоді F(X0) = 2 + 2 + 0 + 8 = 12
Для визначення нижньої межі більшості скористаємося операцією редукції або приведення матриці по рядках, для чого необхідно в кожному рядку матриці D знайти мінімальний елемент.
di = min(j) dij
  i  j  1  2  3  4  di
 1  M  2  3  4  2
 2  2  M  2  3  2
 3  3  2  M  0  0
 4  8  5  3  M  3

Потім відняти його з елементів розглянутої рядка. У зв'язку з цим у знову отриманої матриці в кожному рядку буде як мінімум один нуль.
 i  j  1  2  3  4
 1  M  0  1  2
 2  0  M  0  1
 3  3  2  M  0
 4  5  2  0  M

Потім таку ж операцію редукції проводимо по стовпцях, для чого в кожному стовпці знаходимо мінімальний елемент:
d j = min(i) dij
  i  j  1  2  3  4
 1  M  0  1  2
 2  0  M  0  1
 3  3  2  M  0
 4  5  2  0  M
 dj  0  0  0  0

Після вирахування мінімальних елементів отримуємо повністю скороченої матрицю, де величини d i и dj називаються константами приведення.
 i  j  1  2  3  4
 1  M  0  1  2
 2  0  M  0  1
 3  3  2  M  0
 4  5  2  0  M

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

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

Причому кожен рядок і стовпець входять в маршрут тільки один раз з елементом d ij .
Визначаємо ребро розгалуження і розіб'ємо вся безліч маршрутів щодо цього ребра на дві підмножини (i,j) и (i*,j*).
З цією метою для всіх клітин матриці з нульовими елементами замінюємо по черзі нулі на М (нескінченність) і визначаємо для них суму утворилися констант приведення, вони наведені в дужках.
 i  j  1  2  3  4  di
 1  M  0(3)  1  2  1
 2  0(3)  M  0(0)  1  0
 3  3  2  M  0(3)  2
 4  5  2  0(2)  M  2
 dj  3  2  0  1  0

d(1,2) = 1 + 2 = 3; d(2,1) = 0 + 3 = 3; d(2,3) = 0 + 0 = 0; d(3,4) = 2 + 1 = 3; d(4,3) = 2 + 0 = 2;
Найбільша сума констант приведення дорівнює (1 + 2) = 3 для ребра (1,2), отже, безліч розбивається на дві підмножини (1,2) i (1*,2*).
Нижня межа гамільтонових циклів цього підмножини:
H(1*,2*) = 7 + 3 = 10
Виняток ребра (1,2) проводимо шляхом заміни елемента d12 = 0 на M, після чого здійснюємо чергове приведення матриці відстаней для утворився підмножини (1*,2*), в результаті отримаємо скороченої матрицю.
 i  j  1  2  3  4  di
 1  M  M  1  2  1
 2  0  M  0  1  0
 3  3  2  M  0  0
 4  5  2  0  M  0
 dj  0  2  0  0  3

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

Після операції приведення скорочена матриця буде мати вигляд:
 i  j  1  3  4  di
 2  M  0  1  0
 3  3  M  0  0
 4  5  0  M  0
 dj  3  0  0  3

Нижня межа підмножини (1,2) дорівнює:
H(1,2) = 7 + 3 = 10  <  10
Оскільки нижня межа цієї підмножини (1,2) менше, ніж підмножини (1*,2*), то ребро (1,2) включаємо в маршрут.
Визначаємо ребро розгалуження і розіб'ємо вся безліч маршрутів щодо цього ребра на дві підмножини (i,j) и (i*,j*).
З цією метою для всіх клітин матриці з нульовими елементами замінюємо по черзі нулі на М (нескінченність) і визначаємо для них суму утворилися констант приведення, вони наведені в дужках.
 i  j  1  3  4  di
 2  M  0(1)  1  1
 3  0(2)  M  0(1)  0
 4  2  0(2)  M  2
 dj  2  0  1  0

d(1,2) = 1 + 0 = 1; d(2,1) = 0 + 2 = 2; d(2,3) = 0 + 1 = 1; d(3,2) = 2 + 0 = 2;
Найбільша сума констант приведення дорівнює (0 + 2) = 2 для ребра (3,1), отже, безліч розбивається на дві підмножини (3,1) i (3*,1*).
Нижня межа гамільтонових циклів цього підмножини:
H(3*,1*) = 10 + 2 = 12
Виняток ребра (3,1) проводимо шляхом заміни елемента d31 = 0 на M, після чого здійснюємо чергове приведення матриці відстаней для утворився підмножини (3*,1*), в результаті отримаємо скороченої матрицю.
 i  j  1  3  4  di
 2  M  0  1  0
 3  M  M  0  0
 4  2  0  M  0
 dj  2  0  0  2

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

Після операції приведення скорочена матриця буде мати вигляд:
 i  j  3  4  di
 2  0  1  0
 4  0  M  0
 dj  0  1  1

Нижня межа підмножини (3,1) дорівнює:
H(3,1) = 10 + 1 = 11  <  12
Оскільки нижня межа цієї підмножини (3,1) менше, ніж підмножини (3*,1*), то ребро (3,1) включаємо в маршрут.
Згідно з цією матрицею включаємо в Гамільтон маршрут ребра (2,4) и (4,3).
В результаті по дереву розгалужень Гамільтоном цикл утворюють ребра:
(1,2), (2,4), (4,3), (3,1),
Довжина маршруту дорівнює F(Mk) = 11