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

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

,

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

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

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

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

,

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

, .

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

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

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

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

Таблиця 2

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

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

9→10

7→9→10

3→7→9→10

1→3→7→9→10

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

Дата добавления: 2014-11-29