Завдання для самостійного опрацювання

1. Задано граф за допомогою матриці суміжності ваг . Конкретизуйте тип заданого графу та знайдіть найкоротші відстані між двома довільними вершинами графа.

2. Задано граф у вигляді матриці суміжності ваг . Конкретизуйте тип заданого графу та знайдіть найкоротші відстані між двома довільними вершинами графа.

3. Задано граф матрицею суміжності ваг. Знайдіть найкоротші відстані між будь якими двома вершинами, враховуючи, що любий найкоротший шлях між вершинами створено не більше ніж з двох дуг або ребер.

Тестові питання для самоперевірки

1. Метод Шимбела дозволяє знайти 1) Найкоротший гамільтонів контур 2) Найкоротшу відстань між фіксованою вершиною та названою. 3) Найкоротший шлях між вершинами графа. 4) Найкоротші відстані між будь-якими двома вершинами графа.

2. Ступінь матриці найкоротших відстаней показує 1) довжину найкоротшого шляху у матриці.

2) максимальне число вершин у любому з найкоротших шляхів.

3) максимальне число дуг між двома довільними вершинами графа.

4)максимальне число дуг у довільному з найкоротших шляхів.

3. Граф задано у вигляді матриці суміжності ваг . Знайдено матрицю найкоротших відстаней по двох дугах. Серед наведених матриць виберіть матрицю найкоротших відстаней по трьох дугах С

1) 2)3)4)

Практичне заняття № 7. Тестові завдання до першого модулю Практичне заняття № 8. Пошук найкоротшого гамільтонового контура за методом гілок та меж

Короткі теоретичні відомості.

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

Постановка задачі у термінах теорії графів : задано орієнтовний мультиграф. Необхідно знайти гамільтонів контур мінімальної довжини.

Обчислювальна складність задач Гамільтона і комівояжера має порядок (n-1)!. Внаслідок такої значної обчислювальної складності для розв’язку задачі комівояжера створено багато алгоритмів, як автономних, так і таких, що базуються на інших оптимізаційних алгоритмах, - потокових, що будують мінімальний остів тощо.

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

Основна ідея методу Літла досить проста. Спочатку будується деяка оцінка знизу (НГ- нижня оцінка) довжин усіх гамільтонових контурів. Після цього множина всіх гамільтонових контурів розбивається на дві підмножини. Перша підмножина складається з гамільтонових контурів, що включають деяку дугу (i,j) , а інша підмножина складається з контурів, що не включають цю дугу . Для кожної з підмножини за тим самим правилом, що і для початкової множини гамільтонових маршрутів, визначається нижня межа. Кожна нова нижня межа виявляється не менше нижньої межі, визначеної для всієї множини. Порівнюючи нижні межі, можна визначити підмножину гамільтонових контурів, усередині якої з більшою ймовірністю міститься оптимальний маршрут. Ця підмножина за анологічним правилом розбивається ще на два, і знову знаходяться нижні межі, і так доти, поки не залишається єдиний цикл. Процес розбивки підмножин супроводжується побудовою деякого бінарного дерева.

Розглянемо розв'язок цієї задачі на прикладі 2.5.1. Нехай необхідно розв'язати задачу комівояжера з матрицею витрат .

Розв`язок.

1. Занесемо до рядків та стовпців матриці нульові елементи шляхом віднімання найменших елементів з відповідних рядка та стовпця.

	1	2	3	4	5	hi			1	2	3	4	5
1		10	5	8	1	1		1		9	4	7	0
2	8		15	2	14	2		2	6		13	0	12
3	5	14		1		1		3	4	13		0	
4	4	16	10		2	2		4	2	14	8		0
5	1	4	1	1		1		5	0	3	0	0	
						7		hj	0	3	0	0	0	3

Початкове значення нижньої межі (сума всіх констант приведення матриці) НМ=7+3=10.

2. Оцінимо отримані нулі матриці вагою (штраф за невикористання проїзду), яка складається із суми найменших елементів із стовпця та рядка, на перетині яких знаходиться нуль (нуль, що оцінюється, у виборі мінімального не фіґурує).

	1	2	3	4	5
1		6	4	7	04
2	6		13	06	12
3	4	10		04	
4	2	11	8		02
5	02	06	04	00	

Обираємо нуль з найбільшою вагою. Якщо таких нулів декілька, вибираємо будь-який. Наприклад, нуль (2,4).

3. Оцінимо нижню межу множини усіх гамільтонових контурів, які виключають обрану дугу (2,4). Для аналізу такого варіанту немає потреби виписувати матрицю витрат, достатньо врахувати при підрахунку нижньої межі вагу обраного нуля матриці: НМ=НМ+вага нуля=10+6=16.

	1	2	3	4	5	hi			1	2	3	4	5
1		6	4	7	0	0		1		6	4	7	0
2	6		13		12	6		2	0		7		6
3	4	10		0		0		3	4	10		0	
4	2	11	8		0	0		4	2	11	8		0
5	0	0	0	0		0		5	0	0	0	0	
						6		hj	0	0	0	0	0	0

Для побудови матриці (виключення дуги (2,4) з гамільтонового контуру), необхідно елемент матриці (2,4) замінити на нескінченність, що призведе до повторного приведення рядка матриці на 6 одиниць (вага нуля).

4. Оцінимо нижню межу множини усіх гамільтонових контурів, які включають обрану дугу (2,4). Для аналізу такого варіанту необхідно виконати наступні перетворення вихідної матриці:

1) викреслити рядок (2-й) та стовпець(4-й) на перетині яких міститься обраний нуль;

2) заборонити до вибору елемент матриці(4,2), який відповідає замкненню шляху в один елементарний цикл;

3)над перетвореною матрицею виконаємо крок приведення матриці 1(якщо це необхідно).

Тоді нижня межа цього вибору буде дорівнювати сумі констант приведення перетвореної матриці та попереднього значення нижньої межі.

	1	2	3	5	hi		(2,4)	1	2	3	5
1		6	4	0	0		1		6	4	0
3	4	10			4		3	0	6		
4		11	8	0	0		4	2	11	8	0
5	0	0	0		0		5	0	0	0	
					4		hj	0	0	0	0	0

НМ=10+4=14.

На цьому етапі маємо дерево пошуку наступного вигляду

5. Серед листків дерева розв’язків обираємо лист з найменшою нижньою межею. У нашому випадку це лист (2,4), який відповідає варіанту включення дуги (2,4) у очікуваний гамільтонів контур. Подальші дослідження слід виконувати у матриці (2,4), починаючи з пункту 2.

(2,4)	1	2	3	5	hi			(5,2)	1	3	5	hi	(5,2)	1	3	5
1		6	4	04	0			1		4	0	0	1		4	0
3	06	6			0			3	0			0	3	0		
4	2	11	8	02	0			4	2	8		2	4	0	6	
5	00	06	04		0							2	hj	0	4	0
hj	0	0	0	0	0

НМ(5,2)=14+6=20

НМ()=14+6=20

Порівнюючи НМ листків отриманого дерева розв’язків, знову обираємо лист з найменшою нижньою межею і виконуємо кроки 2-5 з відповідною обраному листку матрицею.

Виконавши незначну кількість подібних кроків до розглянутого отримуємо наступне дерево розв’язків

Як бачимо, на дереві існує два «кінцевих» листка з найменшою вагою 20. Їм відповідають наступні матриці

(4,5)	2	3		(3,1)	2	5
1		0		1	0	
5	0			4		0

Матриця (4,5) потребує автоматичного включення до результуючого гамільтонового контура дуг (1,3) та (5,2). У результаті маємо найкоротший гамільтонів контур 134521 завдовжки( ціною) НМ=20 ум. од.

Матриця (3,1) потребує автоматичного включення до результуючого гамільтонового контура дуг (1,2) та (4,5). У результаті маємо ще один найкоротший гамільтонів контур 124531 завдовжки( ціною) НМ=20 ум. од.

Відповідь: існує два найкоротших гамільтонових контура довжиною 20 ум. од. та.