Можно ли выполнить динамическое программирование снизу вверх в Lisp?

Может ли типичный диалект Lisp решить проблемы, используя снизу вверх "динамическое программирование" ?

(Обратите внимание: я не говорю о "memoization", который, насколько я понимаю, тривиально, используя любой диалект Lisp. Я действительно говорю о восходящем динамическом программировании, где вы строите, для пример, ваш массив снизу вверх, а затем используйте только что введенные элементы для вычисления следующих.)

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

Необходимым (неполным) решением является:

for (int k = 1; k <= a.length; k++) {
    for (int y = 1; y <= b; y++) { 
        if (y < a[k-1]) {
            knap[k][y-1] = knap[k-1][y-1];
        } else {
            if (y > a[k-1]) {
                knap[k][y-1] = Math.max(knap[k-1][y-1], knap[k-1][y-1-a[k-1]] + c[k-1]);
            } else {
                knap[k][y-1] = Math.max(knap[k-1][y-1], c[k-1]);
    }
}

Можно ли это сделать в различных диалектах Lisp? Если нет, почему бы и нет?

Ответ 1

Конечно, это возможно. Единственное, что вам нужно, это массивы, целые числа и конструкция цикла. Например, на Схеме ваш алгоритм может быть транскрибирован с помощью векторов. Основная проблема заключается в том, что читать становится трудно, поскольку knap[k-1][y-1] становится (vector-ref (vector-ref knap (- k 1)) (- y 1)) и

knap[k][y-1] = knap[k-1][y-1];

становится

(vector-set! (vector-ref knap k) (- y 1)
             (vector-ref (vector-ref knap (- k 1)) (- y 1)))

(или волосатый трюк с модулями), в то время как memoized рекурсии просто остаются читаемыми.

Говоря по опыту, я рекомендую вам придерживаться memoization при программировании в Lisp и подобных языках. Если вы используете хеш-таблицы, ожидаемое асимптотическое время и пространственная сложность одинаковы для memoization и DP.

Ответ 2

короткий ответ - да, Clojure может работать непосредственно с массивами Java, поэтому прямой перевод очень скромен.

 (for [k (range 1 (count a)) 
       y (range 1 b)]
   (if (< y (aget a (dec k)))
     (aset knap k (dec y) (aget knap (dec k) (dec y))
           (if (> y (aget a (dec k)))
             (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                       (aget knap (dec k) (+ (- y 1 (aget a (dec k)))
                                                             (aget c (dec k))))
                                       (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                                                 (aget c (dec k))))))))))

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

Как тривиальный первый шаг, если мы отделим цикл от "работы", мы получим.

(defn edit-array [k y]
   (if (< y (aget a (dec k)))
     (aset knap k (dec y) (aget knap (dec k) (dec y))
           (if (> y (aget a (dec k)))
             (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                       (aget knap (dec k) (+ (- y 1 (aget a (dec k)))
                                                             (aget c (dec k))))
                                       (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                                             (aget c (dec k))))))))))
(for [k (range 1 (count a)) y (range 1 b)]
   (edit-array k y))

Затем мы можем протестировать массив редактирования из repl и убедить себя, что он работает (и, возможно, написать unit test). После этого, возможно, вы хотели бы более внимательно изучить edit-array и решить, можно ли это разбить на этапы, которые легче тестировать самостоятельно. Возможно, вы можете изменить это, чтобы использовать функциональный стиль вместо мутирования массива. Здесь я отхожу от вашей конкретной проблемы, потому что я должен признать, что я не понимаю исходную проблему, решение которой было разработано для решения.

 (defn finished? [row] ... determine if we have reached the final state ...)

 (defn next-row [current-row]
    (for [y (range 1 (count current-row)]
      ... code to produce a new vector based on the previous one ...))

(take-while #(not (finished? %) (iterate next-row (initial-state)))

Основным понятием того, что я вижу, выглядит код Idomatic Clojure - это разложить проблему на простые (только одно) абстракции, а затем составить их для решения основной проблемы. Конечно, это всегда должно быть адаптировано для решения этой проблемы.

Ответ 3

Извините меня за это, но страница с википедией, на которую вы ссылаетесь, (imnsho) не очень хорошо написана. В частности, он более или менее создает дихотомию между динамическим программированием "сверху вниз" и "снизу вверх" и далее описывает ее как "более интересную". Единственное различие между ними - порядок, в котором построена таблица. Запоминание приводит к обоим из них, в зависимости от порядка, в котором совершаются вызовы.

Извините заранее, кто бы ни писал этот раздел страницы; Я ценю ваши усилия, я просто думаю, что раздел нуждается в некоторой работе.

Ответ 4

Здесь хорошая восходящая версия Fibonacci в Clojure (изначально написанная Christophe Grand, я считаю):

(defn fib []
  (map first (iterate
              (fn [[a b]] [b (+ a b)])
              [0 1])))

Это создает бесконечную ленивую последовательность, поэтому вы можете запрашивать столько или меньше, сколько хотите:

(take 10 (fib))
=> (0 1 1 2 3 5 8 13 21 34)

(nth (fib) 1000)
=> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875