Как решить задачу динамического программирования за 4 шага

Опасаюсь, что заметка будет похожа на "универсальную инструкцию по решению любых задач на компьютере", но я всё же попробую, 9-го утром не успел, а с тех пор уезжал и компьютера не видел :)

Главное, что можно сказать о методах динамического программирования (ДП) по существу - они могут решить некоторые задачи с полиномиальной сложностью по времени и при этом с меньшими вычислительными затратами, чем на полный перебор.

В принципе, в решении задачи ДП можно выделить такие же чётко последовательные шаги, как в решении классической задачи матпрога.

Шаги будут примерно такими:

1. Определить, является ли задача задачей ДП

Когда задача решается методами ДП? Пожалуй, всегда, если она:

• естественным образом "бьётся" на независимые (или перекрывающиеся) подзадачи;
• требует поиска условного экстремума некоторой функции или подсчёта количества расстановок некоторых объектов при определённых условиях.

2. Описать одно состояние системы с помощью наименьшего возможного количества параметров

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

Состояние должно быть описано набором параметров (аргументов), которые могут однозначно его идентифицировать, так, чтобы оно отличалось от всех других состояний.

При этом, чем меньше у нас параметров, тем меньше будет размерность пространства состояний и тем менее трудоёмким окажется поиск решения.

Например, в знаменитой задаче о ранце мы определяем состояние всего двумя параметрами - номер предмета i и его вес w[i] в текущем расположении весов в ранце.

Следующим шагом будет поиск связи между предыдущими состояниями для достижения текущего состояния.

3. Сформировать связь между отдельными состояниями системы

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

Дано 3 натуральных числа, скажем, 1, 3 и 5. Найти общее количество способов, которыми можно образовать натуральное число N, используя сумму данных трех чисел. Разрешены повторения и различные варианты комбинаций.

Скажем, для N=6 имеем 8 способов получения нужной суммы:

1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1

Подумаем о задаче с точки зрения ДП. Прежде всего, нужно описать одно состояние системы.

Примем параметр N для определения состояния, поскольку он может однозначно идентифицировать любую подзадачу.

Итак, наше состояние будет выглядеть как S(N). Здесь S(N) означает общее количество перестановок для n, использующих {1, 3, 5} в качестве переставляемых элементов.

Как его найти? Вот здесь и есть творческий этап решения задачи :)

Мы можем использовать только 1, 3 или 5, чтобы сформировать заданное число N.

Предположим, что мы знаем результат для n = 1, 2, ..., 6; будем говорить, что мы знаем результат для S(n = 1), S(n = 2), ... S(n = 6).

Теперь мы хотим знать результат состояния S(n = 7).

Так как добавляем только 1, 3 или 5, можно получить S(7) следующими тремя способами:

• добавляя 1 ко всем возможным комбинациям S(n = 6), например:

  [(1 + 1 + 1 + 1 + 1 + 1) + 1]
  [(1 + 1 + 1 + 3) + 1]
  [(1 + 1 + 3 + 1) + 1]
  [(1 + 3 + 1 + 1) + 1]
  [(3 + 1 + 1 + 1) + 1]
  [(3 + 3) + 1]
  [(1 + 5) + 1]
  [(5 + 1) + 1]

• добавляя 3 ко всем возможным комбинациям S(n = 4), например:

  [(1 + 1 + 1 + 1) + 3]
  [(1 + 3) + 3]
  [(3 + 1) + 3]

• добавляя 5 ко всем возможным комбинациям S(n = 2), а именно:

  [(1 + 1) + 5]

Эти три случая охватывают все возможные способы формирования S(7). Поэтому мы можем сказать, что результат для S(7) = S(6) + S(4) + S(2) или S(7) = S(7-1) + S(7-3) + S(7-5), что, в общем виде, даёт формулу S(n) = S(n-1) + S(n-3) + S(n-5)

Учтя недопустимые значения N, имеем код:

int solve(int n) { 
 if (n < 0) return 0;
 if (n == 0) return 1;  
 return solve(n-1) + solve(n-3) + solve(n-5);
}

4. Добавить запоминание состояний в некотором контейнере или таблице

Это самая простая часть решения.

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

Например, в нашем случае подойдёт

#define MAXN 100
int dp[MAXN]; //инициализировать этот массив значениями -1
//...
int solve(int n) { 
 if (n < 0) return 0;
 if (n == 0) return 1;  
 if (dp[n]!=-1) return dp[n];
 return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);
}

Другой способ - табулировать решения, вычисляя их итерационно.

ДП требует большого количества практики, всегда полезно порешать классические задачи ДП, например:

http://www.spoj.com/problems/COINS/

http://www.spoj.com/problems/ACODE/

Может позже ещё чего добавлю, сейчас некогда :)

11.06.2018, 22:02 [2664 просмотра]