Рекуррентная формула

Другими словами, имеет место следующая рекуррентная формула. Пусть m[i,j] —вес оптимальной триангуляции многоугольника (v_i-1v_i,...,v_j), где 1≤i<j≤n. Вес оптимальной триангуляции всего многоугольника равен m[1,n]. Будем считать, что «двуугольники» (v_i-1v_i) имеют вес 0. Тогда m[i,i] = 0 для i = 1, 2,...,п. Если j-i≥ 1, то у многоугольника (v_i-1v_i,...,v_j) имеется не менее трёх вершин, и нам необходимо найти минимум (по всем k из промежутка i≤k≤j-1) такой суммы: вес плюс вес оптимальной триангуляции (v_i-1v_i,...,v_k) плюс вес оптимальной триангуляции (v_k,v_k+1,...,v_j). Поэтому

Единственное отличие этой формулы от формулы (2)—более общий вид весовой функции. Стало быть, алгоритм matrix-chain-order с указанными выше изменениями вычисляет вес оптимальной триангуляции; время работы 0(n³), объём используемой памяти 0(n²).

Замечания

Систематическое изучение динамического программирования было начато Р.Беллманом в 1955 году [21], хотя некоторые приёмы такого рода были известны и ранее. Кстати, слово «программирование» (programming) в словосочетаниях «динамическое программирование» (dynamic programming), а также «линейное программирование» (linear programming) не означает составление программ для компьютера.

Ху и Шинг [106] придумали работающий за время 0(n log n) алгоритм для задачи о порядке перемножения матриц; они же указали соответствие между этой задачей и задачей об оптимальной триангуляции.

Алгоритм для нахождения наибольшей общей подпоследовательности за время 0(тп) относится, видимо, к фольклору. В работе [43] Кнут поставил вопрос, возможен ли для этой задачи субквадратичный алгоритм. Масек и Патерсон [143] показали, что возможен, найдя алгоритм, работающий за время 0(mn / logn) при п ≤ т и фиксированном размере множества, из которого берутся члены последовательностей. Для случая, когда в последовательностях нет повторений, алгоритм с оценкой 0((п + т) log(n + т)) построен в статье Шимански [184]. Многие из этих результатов обобщаются на задачу о стоимости редактирования.

ЗАКЛЮЧЕНИЕ

В результате проделанной работы была изложена теория динамического программирования в пояснительной записке. По тексту размещены алгоритмы процедур, переведённых с языка Pascal в язык программирования Си, который является предметом изучения данного курса. Приведённые алгоритмы иллюстрируют методику динамического программирования и возможности составления оптимальных алгоритмов, которые дают возможность экономить память и время выполнения программ.

Дата добавления: 2015-12-08