Tuesday, May 25, 2010

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

Динамическое программирование это подход к решению задач основанный на рекуррентной формуле решения и одном или нескольких стартовых значениях. Задача решается методами динамического программирования если решения подзадач меньшего размера может быть использовано для вычисления решения исходной задачи. Алгоритмы DP обладают полиномиальной сложностью, что намного превосходит другие способы решения задач такого рода.
Для примера, классическая DP-задача 'Размен монет':
Вам даны монеты определенного достоинства (V1, V2, V3…, VN) необходимо посчитать, какое минимальное количество монет потребуется чтобы набрать заданную сумму S. Количество монет каждого достоинства не ограничено.
Рекуррентная формула для решения этой задачи:
  
D(S) = 1 + MIN (D(S-Vi))

Где D(S) это минимальное количество монет которое потребуется чтобы набрать сумму S
Как мы это можем реализовать в императивном стиле?
  
public int change(int[] coins, int s) {
int[] dp = new int[s + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for ( int i = 1; i <= s; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
dp[i] = dp[i - coins[j]] + 1;
}
}
}
return dp[s];
}

В основе этого решения лежит запоминание предыдущих результатов.
Как это решить на Haskell? Ведь мы уже не можем использовать изменяемые массивы или хэш-таблицы. Зато Haskell нам дает в руки такой мощный инструмент как lazy-evaluation. Lazy-evaluation это тоже в своем роде 'запоминание’ только в обратную сторону. Итак решение:
  
import Array

change :: [Int] -> Int -> Int
change xs n = dp!n
where
dp = listArray (0,n) [ cell i | i<-[0..n]]
cell 0 = 0
cell i = succ$minl [dp!(i-x)| x<-xs, i>=x]


minl :: [Int] -> Int
minl [] = 0
minl xs = minimum xs

Что здесь происходит? Прежде всего, мы создаем массив с решениями
  
dp = listArray (0,n) [ cell i | i<-[0..n]]

Но в чем особенность? Особенность в том, что значения в этом массиве появляются по-требованию.
  
cell i = succ$minl [dp!(i-x)| x<-xs, i>x]

Здесь, справа налево, мы вычисляем i-ый элемент массива. Сначала выбираем все монеты достоинство которых меньше либо равно вычисляемой суммы, потом для каждого такого значения смотрим оптимальное решение в массиве. Заметьте, решения там может еще не быть, но оно будет вычислено для нас по-требованию, причем будет вычисленно лишь однажды и лишь для тех значений, которые нам на самом деле нужны! Находим минимальное решение и прибавляем к нему единицу (succ)
Маленькая утилитная функция, которую пришлось ввести minl нужна лишь потому, что стандартная функция minimum не работает с пустыми массивами.

Заключение


В статьях и литературе динамическое программирование как правило приводится с примерами в императивном стиле. Я попытался привести пример решения классической DP задачи в функциональном стиле, который, надеюсь, может оказаться для кого-то полезным.

1 comment:

  1. step-up your cholesterol, which carries the LDL cholesterol bad cholesterol to the liver to be reddened out of the dead body.
    Along with meter the share of issue forth out with a
    buggy, creamy smooothie that is levelheaded as can be. In France, red
    Wine-colored -- a meal, alternatively of relying on the fats in the animate being products to ply the
    taste of the food. This discipline launch an Association normal
    limits testament likewise upshot in a decreased viscosity
    of the roue.

    my homepage :: cholesterol treating niacin with high

    ReplyDelete