3.3 Завдання для самостійної роботи

1. Перетворити ациклічну мережу (рис. 11) до слоїстої. Розв’язати задачу, застосувавши алгоритм зворотної прогонки.

Рис. 11

Відповідь: найкоротший шлях 1-4-7-8, довжина 5

2. Застосувавши алгоритм зворотньої прогонки, знайти найкоротший шлях між вершинами 1 і 10 наступної мережі (рис. 12).

Рис. 12

Відповідь: найкоротші шляхи 1–2–3–6–8–9–10; 1–2–6–8–9–10, їх довжина дорівнює 10.

3. Застосувавши алгоритм зворотньої прогонки, знайти найкоротший шлях між однією з вершин першого слою (вершинами A, B або C) і вершиною K мережі, представленої на рис. 13.

Рис. 13

Відповідь: найкоротший шлях C–E–F–K; довжина шляху 4.

У розглянутих алгоритмах обчислення починалися з кінця мережі і рухалися в напрямку її початку, тобто в напрямку, зворотньому напрямку дуг. Звідси й термін “зворотня прогонка” у назві алгоритму.

Задача може бути розв’язана і в іншому напрямку, тобто при русі від початку мережі до її кінця. У цьому випадку говорять про “пряму прогонку”.

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

(2)

Співвідношення (2) справедливо і для , якщо прийняти, що . З урахуванням позначень наша мета – знайти .

Співвідношення (1) і (2) називаються (основними) рекурентними співвідношеннями.

3.4 Схема алгоритму прямої прогонки (апп) по дугах, що входять

1. Вважаємо .

2. Планування кроку

   1. Виділити всі можливі стани, які можуть мати місце наприкінці кроку , тобто визначити множину .

   2. Для кожного знайти найкоротший шлях з вершини 1 у вершину

Запам'ятати , для якого досягається мінімум цього виразу (умовний оптимальний розв’язок).

3. , якщо , те перейти до п. 4. Інакше - перейти до п. 2.

4. Формування оптимального розв’язку.

3.5 Приклад застосування алгоритму апп по дуга, що входять х

Алгоритмом прямої прогонки розв’яжемо ЗЗНШ для мережі, що представлена на рис. 10.

Оскільки при розв’язанні задачі застосовується пряма прогонка, то першим будемо планувати крок 1. Вважаємо, що .

Планування кроку 1.

Виділимо всі можливі стани, які можуть мати місце наприкінці кроку 1, тобто визначимо множину : . Для вершин знайдемо умовні оптимальні розв’язки , і відповідно. Тут – довжина найкоротшого шляху на кроці 1 (на кроках від 1-го до ( 1)-го включно), за умови, що наприкінці цього кроку система перебуває в стані (вершині) 2. Аналогічно визначаються й . Відповідно до виразу (2) отримаємо:

;

;

.

!	У цьому випадку, у кожну вершину, що аналізується, входить тільки по одній дузі. Тому мінімум не шукається. У кожному випадку умовний оптимальний розв’язок відповідає переходу з вершини 1 ( =1). Така ситуація завжди має місце, якщо в слої є тільки одна вершина (у нас – вершина 1).

Таблиця заповнюється таким чином:

Крок	Можливі стани наприкінці кроку (вершини )	Варіанти розв’язків (управлінь) (попередня вершина)		Вартість розв’язку	Умовний оптимальний розв’язок
		Вхідна дуга	Попередня вершина
1	2	a	1	0+2=2	1	2
	3	b	1	0+5=5	1	5
	4	c	1	0+3=3	1	3

У стовпчику вказується вершина , перехід з якої у вершину забезпечує мінімум виразу (2). У стовпчику f^* вказується значення цього мінімуму – довжина найкоротшого шляху від вершини 1 до вершини .

Планування кроку 2.

Наприкінці цього кроку система може перебувати в одному з трьох станів (вершин): 5, 6 й 7. У стан 5 можна потрапити по дугах і (зі станів 2 й 3 відповідно). Тоді для стану 5 умовний оптимальний розв’язок знаходиться так:

,

– тобто, у вершину 5 найбільш вигідно можна потрапити з вершини 3.

У таблиці ці розрахунки відображаються таким чином:

2	5	d	2	2+10=12	3	10
		f	3	5+5=10

Для станів 6 і 7 співвідношення (2) мають вигляд:

,

– тобто, у вершину 6 найбільш вигідно можна потрапити з вершини 2.

, .

Отже, частина таблиці, що відповідає етапу 2:

2	5	d	2	2+10=12	3	10
		f	3	5+5=10
	6	e	2	2+12=14	2	14
		g	3	5+10=15
		i	4	3+15=18
	7	h	3	5+7=12	3	12
		j	4	3+13=16

Аналогічні дії виконуємо на кроках 3 і 4 .

Повний процес розв’язання задачі наведений у таблиці 2:

Таблиця 2

Крок	Можливі стани наприкінці кроку (вершини )	Варіанти розв’язків (управлінь) (попередня вершина)		Вартість розв’язку	Умовний оптимальний розв’язок
		Вхідна дуга	Попередня вершина
1	2	a	1	0+2=2	1	2
	3	b	1	0+5=5	1	5
	4	c	1	0+3=3	1	3
2	5	d	2	2+10=12	3	10
		f	3	5+5=10
	6	e	2	2+12=14	2	14
		g	3	5+10=15
		i	4	3+15=18
	7	h	3	5+7=12	3	12
		j	4	3+13=16
3	8	k	5	10+7=17	5,6	17
		m	6	14+3=17
		p	7	12+7=19
	9	l	5	10+5=15	7	13
		n	6	14+4=18
		q	7	12+1=13
4	1 0	r	8	17+1=18	9	17
		s	9	13+4=17

Порядок формування відповіді показано стрілками:

9→10

7→9→10

3→7→9→10

1→3→7→9→10

Відповідь: найкоротший шлях 1-3-7-9-10, довжина шляху 17.