Составители:
Рубрика:
11
Доказанное правило лежит в основе алгоритма реше-
ния задачи динамического программирования, состоящего
из двух этапов.
I этап (движение от конца к началу). Начиная с кон-
ца последовательно находим
);(),(;);(),();(),(
0
*
10
*
12
*
12
*
11
*
1
*
uSuSuS
nnnnnnnn
для всех возможных на соответствующих шагах состояний
с использованием на каждом шаге, начиная с n-1-го, фор-
мулы (6).
*
n
S
вычисляется непосредственно по формуле
).,(max)(
11
*
nnn
u
nn
ufS
n
(7)
II этап (движение от начала к концу). Двигаясь от
начала, существенно используя закрепленность начального
состояния, строим безусловную оптимальную траекторию
Здесь
)].(,[
*
1
**
1
*
kkkk
u
Далее рассмотрим примеры решения различных по
своей природе задач, которые можно вложить в схему ди-
намического программирования.
§4. Задача об оптимальном маршруте
Из всевозможных маршрутов, соединяющих точки
A
и
B
(рис. 3), выбрать тот, на котором сумма чисел («по-
терь»), стоящих на звеньях, была бы наименьшей. Пункты,
через которые может проходить маршрут, обозначены на
рис. кружочками.
0
*
1
*
2
.
*
n
)(
0
*
1
u
)(
*
1
*
2
u
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
