Составители:
Рубрика:
256
расположения этого пункта в общей схеме (сети) дорог, соединяющих между собой все
пункты множества
N
. Таким образом, для данной задачи выполняется и это основное
свойство задач динамического программирования – свойство
независимости
оптимальной стратегии от предыстории.
Если в сформулированной задаче имеется конечное число путей, то задача может
быть решена посредством перебора возможных вариантов и выбора из них оптимального.
Однако метод перебора чрезвычайно громоздок и поэтому практически неприменим при
достаточно большом числе
N
.
Сравнительно быстро и просто оптимальным результат задачи может быть получен
посредством составления и решения
функциональных уравнений
, являющихся основой
метода динамического программирования.
Составим функционирование уравнения для сформулированной выше задачи
определения маршрута переезда из
i
-го в
N
-й пункт, обеспечивающего минимальные
затраты времени на переезд (или продвижение, например, деталей).
Для этого примем следующие обозначения. Через
f
iN
– обозначим время,
необходимое для переезда из
i
-го пункта в конечный пункт
N
при использовании
оптимальной стратегии.
I
=1,2,…,
N
-1.
Полагаем, что
f
NN
=0.
Используя принцип оптимальности Р.Беллмана, можно записать следующие
функциональные уравнения (рекуррентные соотношения), полностью описывающие
данный процесс (ситуацию):
[
]
=
−=+=
≠
0
,1,...,2,1,
min
NN
jNij
ij
kN
f
Niftf
(7.44)
Решение задачи производится поэтапно, в прямом и обратном по времени
направлении перемещения из пункта 1 в конечный пункт
N
. Это вызвано жестким
ограничением задачи, заключающимся в том, что должны быть пройдены все пункты и ни
на один из них движение не должно замыкаться.
На первом этапе (в обратном направлении) рассматриваются перемещения из
последнего пункта в конечный пункт
N
. На втором этапе перемещения из предпоследнего
через последний пункт в конечный пункт
N
и т.д. При прямом направлении перемещения
на первом этапе рассматривается перемещение из начального пункта в первый пункт, на
втором этапе – перемещение из начального во второй пункт через первый и т.д.
Общую схему решения задачи на
s
-м этапе математически можно изобразить так:
−=
−
+
≠
=
−==
1,...,3,2,
)1(
min
,1,...,3,2,
)(
)0(
Nj
s
f
ij
t
ji
f
Njtf
jN
s
kN
jNjN
(10.45)
при разворачивании процесса в обратном направлении и
−=
−
+=
−==
1,...,3,2,
)1(
1
min
,1,...,3,2,
)(
1
1
)0(
1
Nj
s
i
f
ij
tf
Nitf
s
k
ii
(7.46)
при разворачивании процесса в прямом направлении.
Страницы
- « первая
- ‹ предыдущая
- …
- 254
- 255
- 256
- 257
- 258
- …
- следующая ›
- последняя »
