Методы динамического программирования

Динамическое программирование представляет собой метод нахождения оптимальных решений в задачах, где процесс решения может быть разбит на шаги или подзадачи. Большой вклад в разработку теории динамического программирования внес американский ученый Р. Беллман. Он сформулировал важнейший принцип динамического программирования – принцип оптимальности. Этот принцип состоит в следующем: оптимальное поведение обладает тем свойством, что каково бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения.

Условно принцип Беллмана можно записать в следующем виде:

где f_k – множество решений на k (текущем) шаге;

Z * k +1– оптимальные решения на k +1 шагах;

Z * k – оптимальное решение на k (текущем) шаге.

Дата добавления: 2014-01-07