Клітка з максимальною ступеню нуля визначить дугу, згідно з якою буде виконуватись подальше гілкування

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

Визначаємо максимальний ступінь нуля. Вона рівна 316 і відповідає кліткам (1-8) і (8-1). Обираємо клітку (1-8). Таким чином, претендентом на включення в гамільтонов контур є дуга (1-8).

Розбиваємо безліч всіх гамільтонових контурів на дві підмножини: G1 і G2. Матрицю з дугою (1-8) одержуємо шляхом викреслювання рядка 1 і стовпця 8 (табл.4). Щоб не допускати утворення негамільтонового контуру (зациклювання), замінюємо елемент (8-1) на знак «».

Таблиця 4 Матриця G1 (включає дугу 1-8- исчезли 1-я строка и 8 столбец)

Підмножина G2, навпаки, виключає дугу (1-8). Для цього замінюємо елемент (1-8) в таблиці 3 на знак «». Матриця G2 відображена в таблиці 5.

Графічно це показано на рис.1.

Таблиця 5 Матриця G2 (виключає дугу 1-8)

Подальше гілкування почнемо з підмножини G1.

Виконуємо приведення матриці G1 за алгоритмом, який було приведено вище.

Результати приведення наведено в таблиці 6.

Таблиця 6 Приведена матриця G1 (з дугою 1-8)

								ai
	0-475
				0-113	0-113
			0-113
			0-113
							0-234
		0-57				0-234
							0-57
bj

Як видно з таблиці 6 приведена константа для підмножини G1 дорівнює 316. Тоді нижча границя гамільтонових контурів для цієї підмножини буде складати:

S(G1)=2842+316 = 3158

Зробимо приведення матриці G2. Результати наведено в таблиці 7.

Таблиця 7 Приведена матриця G2 (виключає дугу 1-8)

									ai
bj

Приведена константа для підмножини G2 також дорівнює 316. Тоді нижча границя гамільтонових контурів для цієї підмножини буде складати

S(G2)=2842+316 = 3158= S(G1)

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

Продовжимо гілкування множини G1. Оцінимо клітки з «0». Найвищу оцінку має дуга (2-1). Розглядаємо її як елемент майбутньої можливої оптимальної схеми. Таким чином ми маємо дві дуги, а саме: (1-8) і (2-1). Або схему руху (2-1-8). Виключаючи зациклювання заборонимо рух по дузі (8-2) значком «». Розіб’ємо множину G1 на підмножини G3 (включає дугу 2-1) і G4 (забороняє рух по дузі 2-1).

Таблиця 8 Матриця G3 (включає дугу 2,1)

				22

Підмножину G4 отримуємо з таблиці 6, заборонив рух по дузі (2,1) знаком «».

Таблиця 9 Матриця G4 (виключає дугу 2,1)

					22

Зробимо приведення матриць G3 і G4.

Таблиця 10 Приведена матриця G3

							ai
			0 -113	0-113
		0 - 113
		0 -113		22
						0-234
	0 -234				0-486
bj

Приведена константа для підмножини G3 дорівнює 0. Тоді нижча границя гамільтонових контурів для цієї підмножини буде складати

S(G3) = 3158 + 0 = 3158

Таблиця 11 Приведена матриця G4

								ai
					22
bj

Приведена константа для підмножини G4 дорівнює 475. Тоді нижча границя гамільтонових контурів для цієї підмножини буде складати

S(G4)=3158 + 475 = 3633

Для подальшого гілкування обираємо множину G3. Множина G4 з подальшого розгляду виключається. В приведеній матриці G3 (табл..10) оцінимо «0». Дуга (7-6) розглядається як елемент схеми. Розіб’ємо G3 на G5 (включає дугу 7-6) і G6 виключає дугу 7-6).

Виконаємо аналогічні попереднім операції.

Табл.12 Приведена матриця G5 (включає дугу 7-6)

						ai
			0-113	0-113
		0-113
		0-113		22
	0-600
	@				0-1321
bj

Матрицю G6 отримаємо з табл.10 шляхом виключення дуги (7-6) знаком «».

Порівняв приведені константи для множин G5 і G6 для подальшого гілкування обираємо множину G5, для якої S(G5) = 3158 + 0 = 31583. Розіб’ємо G5 на підмножини G7 і G8. З приведеної матриці G5, після оцінювання нульових кліток до включення в схему обираємо дугу (8-7). Таким чином отримуємо гамільтонов контур 2-1-8-7-6.

Табл.13 Матриця G6 (виключає дугу 7-6)

							ai
				22
bj

Матрицю G7 отримаємо з таблиці 12 шляхом вилучення строки 8 і стовбця 7. Для запобігання за циклювання заборонимо дугу (6-2).

Таблиця 14 Приведена матриця G7

					ai
		2	0-113	0-0
		0 -113	2
		0 - 113		222
	2			0 -181
bj

Таблиця 15 Приведена матриця G8

						ai
				22
	@
bj

S(G7)=3158 + 251 = 3409

S(G2)=3158 + 708 = 3866

Для подальшого розгляду обираємо підмножину G7. Оцінив нульові клітини до схеми залучаємо дугу (6-5). Розбиваємо G7 на G9 і G10 за тим ж самими правилами.

Таблиця 16 Приведена матриця G9

				ai
		2	0-475
		0 -715	2
	2	0 -113
bj

Таблиця 17 Приведена матриця G10

					ai
		2
			2
				2
				2
bj

Оцінюємо нульові клітки в таблиці 16 і, як наслідок, обираємо до включення в схему дугу (4-3).

Гілкуванню підлягає множина G9, яка має S(G9) =3409 + 362 = 3771.

Ми отримали матрицю розміром 2 х 2 (таблиця 18) і на цьому гілкування закінчується. До схеми включаються дуги (5-4) і (3-2).

Таблиця 18. Остання матриця

	2

Таким чином, отримано гамільтонов цикл: 1-8-7-6-5-4-3-2-1.

Круїзна лінія:

Дата добавления: 2015-06-27