asyan.org
добавить свой файл
  1 ... 4 5 6 7

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

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

i j


1


7


8


9


di


6


3


M


0(0)


0(0)


0


8


1


0(0)


M


0(0)


0


9


0(1)


0(0)


0(0)


M


0


10


M


0(0)


0(0)


0(0)


0


dj


1


0


0


0


0


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

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

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

H(9*,1*) = 4 + 1 = 5

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

i j


1


7


8


9


di


6


3


M


0


0


0


8


1


0


M


0


0


9


M


0


0


M


0


10


M


0


0


0


0


dj


1


0


0


0


1


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

В результаті отримаємо іншу скорочену матрицю (3 x 3), яка підлягає операції приведення.

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

i j


7


8


9


di


6


M


0


0


0


8


0


M


0


0


10


0


0


0


0


dj


0


0


0


0


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

H(9,1) = 4 + 0 = 4 < 5

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

Оскільки нижня межа цієї підмножини (9,1) менше, ніж підмножини (9*,1*), то ребро (9,1) включаємо в маршрут.

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

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

i j


7


8


9


di


6


M


0(0)


0(0)


0


8


0(0)


M


0(0)


0


10


0(0)


0(0)


M


0


dj


0


0


0


0


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

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

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

H(6*,7*) = 4 + 0 = 4

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

i j


7


8


9


di


6


M


0


0


0


8


0


M


0


0


10


0


0


M


0


dj


0


0


0


0


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

В результаті отримаємо іншу скорочену матрицю (2 x 2), яка підлягає операції приведення.

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

i j


8


9


di


8


M


0


0


10


0


M


0


dj


0


0


0


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

H(6,7) = 4 + 0 = 4 < 4

Оскільки нижня межа цієї підмножини (6,7) менше, ніж підмножини (6*,7*), то ребро (6,7) включаємо в маршрут.

Згідно з цією матрицею включаємо в Гамільтон маршрут ребра (8,9) и (10,8).

В результаті по дереву розгалужень Гамільтоном цикл утворюють ребра:

(1,2), (2,3), (3,4), (4,10), (10,8), (8,9), (9,1),

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


<< предыдущая страница