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

1. Вважаємо, що .

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

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

   2. Для кожного знайти умовне оптимальне управління:

(мінімум шукаємо по дугах, що виходять).

Запам'ятати вершину , при якій досягається мінімум у виразі .

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

4. Формування оптимального розв’язку. Для знаходження найкоротшого шляху пройти по мережі в напрямку, зворотньому до напрямку розрахунків, використовуючи знайдені умовні оптимальні розв’язки (вершини) .

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

Використовуючи алгоритм зворотньої прогонки по дугах, що виходять, знайти найкоротший шлях з вершини 1 у вершину 10 (рис. 10).

При застосуванні алгоритму зворотньої прогонки, першим планується крок 4 (останній крок). Вважаємо, що (довжина найкоротшого шляху від вершини 10 до самої себе).

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

; ;

; .

!	У цьому випадку, з кожної вершини виходить тільки по одній дузі (говоримо, що в кожному стані можливий тільки один варіант розв’язку). Тобто маємо “вибір без вибору”. Така ситуація завжди має місце, якщо в останньому слої є тільки одна вершина (у нас - вершина 10).

Заповнюємо таблицю таким чином:

Крок	Можливі стани на початку кроку (вершини )	Варіанти розв’язків		Вартість розв’язку	Умовний оптимальний розв’язок
		Вихідна дуга	Наступна вершина
4	8	r	10	1+0=1	1 0	1
	9	s	10	4+0=4	10	4

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

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

,

– тобто, якщо з вершини 5 перейти у вершину 8, то досягається мінімум виразу (1).

!	Згадаємо одне з основних положень ДП: „в процесі поетапного планування управління на кожному кроці повинно обиратися з урахуванням його майбутніх наслідків”. У нашому випадку це здійснюється через урахування величин і .

Для стану =5 таблицю заповнюємо таким чином:

3	5	k	8	7+1=8	8	8
		l	9	5+4=9

Отримали: = 8, =8.

Аналогічні дії виконуються і для випадків, коли на початку кроку 3 система перебуває в станах 6 або 7:

, .

, .

3	6	m	8	3+1=4	8	4
		n	9	4+4=8
	7	p	8	7+1=8	9	5
		q	9	1+4=5

Аналогічно плануються кроки 2 і 1.

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

Таблиця 1

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

Порядок формування відповіді (найкоротшого шляху) показаний стрілками.

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