Читайте также:
|
|
Другими словами, имеет место следующая рекуррентная формула. Пусть m[i,j] —вес оптимальной триангуляции многоугольника (vi-1vi,...,vj), где 1≤i<j≤n. Вес оптимальной триангуляции всего многоугольника равен m[1,n]. Будем считать, что «двуугольники» (vi-1vi) имеют вес 0. Тогда m[i,i] = 0 для i = 1, 2,...,п. Если j-i≥ 1, то у многоугольника (vi-1vi,...,vj) имеется не менее трёх вершин, и нам необходимо найти минимум (по всем k из промежутка i≤k≤j-1) такой суммы: вес плюс вес оптимальной триангуляции (vi-1vi,...,vk) плюс вес оптимальной триангуляции (vk,vk+1,...,vj). Поэтому
Единственное отличие этой формулы от формулы (2)—более общий вид весовой функции. Стало быть, алгоритм matrix-chain-order с указанными выше изменениями вычисляет вес оптимальной триангуляции; время работы 0(n3), объём используемой памяти 0(n2).
Замечания
Систематическое изучение динамического программирования было начато Р.Беллманом в 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; просмотров: 56 | Нарушение авторских прав