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

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

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

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

; ;

; .

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

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

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

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

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

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

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

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

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

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

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

, .

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

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

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

Таблиця 1

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