Динамическое программирование (

Если учесть, что решение  подзадачи размером не более трех не требует вообще никаких действий, то рассматривая описанные варианты 1–3, следует предпочесть вариант 3, где нужно выбрать некоторое k из диапазона от 1 до s−2 и решить подзадачи S_i,k+1 S_i+k,s−k. Если для решения задачи размером более четыре и более воспользоваться очевидным рекурсивным алгоритмом, непосредственно вытекающим из перечисленных выше вариантов, то можно показать что общее число рекурсивных вызовов составляет 3^s−4, если подсчитать лишь обращения к подзадачам размером четыре и более. Таким образом количество подзадач, которые необходимо решить, возрастает по экспоненциальному закону в зависимости от s. А следовательно общее количество шагов экспоненциально зависит и от n.

Но известно, что, помимо исходной задачи существует лишь n(n−4) различных подзадач, которые в любом случае необходимо решить. Значит в приведенном анализе что-то явно не совсем верно. Очевидно, что совсем не все подзадачи отличаются между собой, если действовать рекурсивно, как приведено выше, то у нас возникают ситуации, когда одни и те же ситуации приходится решать несколько раз. Именно это подсказывает нам эффективный способ вычисления триангуляции. Прежде всего, вычисления удобно организовать в виде таблицы. Назначим стоимость C_is триангуляции S_is для всех i и s. Поскольку решение любой данной задачи зависит от решения задач меньшего размера, то логичным порядком заполнения такой таблицы является порядок, основанный на размерах подзадач, т. е. для размеров s = 4, 5, …, n−1 мы указываем минимальную стоимость задач S_is для всех вершин i. Удобно включить и задачи размеров 0 ≤ s < 4, но при этом нужно помнить, что S_is имеет стоимость 0, если s < 4.

В соответствии с перечисленными выше вариантами действий 1–3 при определении  подзадач формула вычисления C_is при s ≥ 4 должна иметь следующий вид:

C_is = min_{1≤k≤s−2} {C_i,k+1 + C_i+k,s−k + D(v_i, v_i+k) + D(v_i+k, v_i+s−1)},

где D(v_p, v_q) — это длина хорды между вершинами v_p и v_q, если v_p и v_q не являются смежными вершинами многоугольника; D(v_p, v_q) равняется 0, если являются смежными вершинами.

Отметим, что таким образом, мы вычислим всю таблицу, и определим  стоимость минимальной триангуляции, но не саму триангуляцию. Поэтому, как  и в задаче про наибольшую общую подпоследовательность для того, чтобы найти саму триангуляцию, мы должны еще также хранить информацию, о том, при каком значении k достигается минимум. И потом уже, по всем сохраненным значениям k мы можем легко восстановить минимальную триангуляцию.

Задача о загрузке

Задача о загрузке — это задача о рациональной загрузке судна (самолета, автомашины, и т. п.), которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в том, чтобы определении загрузки, такими грузами которые приносят наибольшую прибыль.

Отметим также, что данная задача известна как задача о рюкзаке, в который турист должен определить наиболее ценные предметы, подлежащие загрузке в рюкзак. Формализуем нашу задачу. Пусть W — грузоподъемность нашего судна и есть в наличии n наименований предметов, которые подлежат загрузке. Пусть m_i — количество предметов i-го наименования, r_i — прибыль, которую приносит один загруженный предмет i-го наименования, w_i — вес одного предмета i-го наименования. Тогда общая задача имеет вид следующей целочисленной задачи линейного программирования.

Максимизировать Z = r₁m₁ + r₂m₂ + … + r_nm_n при условии, что

w₁m₁ + w₂m₂ + … + w_nm_n ≤ W, 
m₁, m₂, …, m_n ≥ 0.

Рассмотрим подход, несколько  иной, чем был приведен выше. При  рассмотрении каждой конкретной задачи обратим внимание три основных элемента модели динамического программирования..

1. Определение этапов.
2. Определения на каждом этапе вариантов решения (альтернатив).
3. Определения состояний на каждом этапе.

Из перечисленных выше элементов понятие состояние, как правило, представляется весьма сложным для восприятия. Определение этого понятия может меняться в зависимости от конкретной ситуации. При рассмотрении каждого приложения полезно ответить на следующие вопросы.

1. Какие соотношения связывают этапы вместе?
2. Какая информация необходима для того, чтобы получить допустимые решения на текущем этапе без повторной проверки решений, принятых на предыдущих этапах.

В приведенной задаче о  загрузке три элемента модели динамического программирования определяются следующим образом.

1. Этап i ставится в соответствие предмету i-го наименования, i = 1, 2, …, n.
2. Варианты решения на этапе i описываются количеством предметов m_i предметов i-го наименования, подлежащих загрузке. Соответствующая прибыль равна r_im_i. Значение заключено m_i в пределах от 0 до [W⁄w_i], где [W⁄w_i] — целая часть числа W⁄w_i.
3. Состояние x_i на i выражает суммарный вес предметов, решения о погрузке которых приняты на этапах i, i+1, …, n. Это определение отражает тот факт, что ограничение по весу является единственным, которое связывает вместе все n этапов.

Пусть f_i(x_i) — максимальная суммарная прибыль от этапов i, i+1, …, n при заданном состоянии x_i. Определим рекуррентное уравнение с помощью следующей двухшаговой процедуры.

1. Выразим f_i(x_i) как функцию f_i+1(x_i+1) в виде

f_i(x_i) = max {r_im_i + f_i+1(x_i+1)}, i = 1, 2, …, n,

где max берется по всем

m_i = 0, 1, …, [W⁄w_i] и x_i = 0, 1, …, W,

где f_n+1(x_n+1) ≡ 0.

2. Выразим x_i+1 как функцию x_i для гарантии того, что левая часть последнего уравнения является функцией лишь x_i. По определению x_i+1 − x_i представляет собой вес, загруженный на этапе i, т. е. x_i+1 − x_i = w_im_i или x_i+1 = x_i − w_im_i. Тогда рекуррентное уравнение приобретает следующий вид.

f_i(x_i) = max {r_im_i + f_i+1(x_i−w_im_i)}, i = 1, 2, …, n,

где max берется по всем

m_i = 0, 1, …, [W⁄w_i] и x_i = 0, 1, …, W.

Задача о загрузке является типичным представителем задачи распределения  ресурсов, в которой ограниченный ресурс распределяется между конечным числом видов (экономической) деятельности. В таких моделях определения  состояния на каждом этапе будет  аналогично приведенному для задачи о загрузке : состоянием на этапе i является суммарное количество ресурса, распределяемого на этапах i, i+1, …, n.

Заключение

Здесь были рассмотрены некоторые  примеры детерминированных моделей  динамического программирования. Принцип  оптимальности является основой  поэтапного решения задачи динамического  программирования. Несмотря на то, что  этот принцип не содержит информации о способах решения подзадач на каждом этапе, его применение существенно  облегчает решение многих сложных  задач, которые нельзя решить другими  методами. Укажем два признака, характерных  для задач, решаемых методами динамического  программирования.

• Задача обладает свойством оптимальности для подзадач, т. е. оптимальное решение задачи содержит оптимальные решения ее подзадач.
• Задача имеет перекрывающиеся подзадачи, т. е. при рекурсивном решении мы многократно выходим на одни и те же подзадачи.

Литература

1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.
2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. — М.: Издательский дом «Вильямс», 2001.
3. Таха Х. Введение в исследование операций. — М.: Издательский дом «Вильямс», 2001.
4. Беров В.И., Лапунов А.В., Матюхин В.А., Пономарев А.Е. Особенности национальных задач по информатике. — Киров: Триада-С, 2000.

Камышан Андрей

 

Маша / 2009-05-27 21:27:59

Хочу сказать спасибо  автору за такую статью. Кучу сайтов, посвященных информатике, пересмотрела, но нигде такой доступной раскладки  алгоритма LCS не встретила. Да и к  тому же везде статьи повторяются. Еще  раз огромное спасибо!!!!

Виталий / 2010-07-08 12:21:22

Похоже, что в задаче о  загрузке есть ошибка:

"... По определению x(i+1) &#8722; x(i) представляет собой вес,  загруженный на этапе i, т. е. x(i+1) &#8722; x(i) = w(i)m(i) или x(i+1) = x(i) &#8722; w(i)m(i). Тогда рекуррентное уравнение  приобретает следующий вид.

fi(x(i)) = max {r(i)m(i) + f(i+1)(x(i)&#8722;w(i)m(i))}, i = 1, 2, ?, n,..."

Если x(i+1) &#8722; x(i) = w(i)m(i), то логично, чтобы x(i+1) = x(i) + w(i)m(i), а не x(i+1) = x(i) &#8722; w(i)m(i).

Миша / 2011-11-14 00:35:37

Автору спасибо за статью. Маша, ты не читала Окулова? Это очень  толковая книга и там про lcs хорошо написано