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

Question

Может ли типичный диалект 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]);
    }
}

Можно ли сделать такую ​​вещь на различных диалектах Лисп?Если нет, то почему нет?

Answer 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)))

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

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

Answer 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 и убедить себя, что он работает (и, возможно, написать модульный тест). После этого, возможно, вы захотите начать более внимательно смотреть на 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, состоит в том, чтобы разбить задачу на простые (делает только одно) абстракции, а затем скомпоновать их для решения основной проблемы. Конечно, это всегда должно быть адаптировано к конкретной проблеме.

Answer 3

Простите, что сказал это, но страница википедии, на которую вы ссылаетесь, не очень хорошо написана. В частности, он более или менее фабрикует дихотомию между динамическим программированием сверху вниз и снизу вверх и продолжает описывать его как «более интересный». Единственное различие между ними заключается в порядке построения таблицы. Мемоизация приводит к обоим из них, в зависимости от порядка выполнения вызовов.

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

Answer 4

Вот хорошая восходящая версия Фибоначчи в Clojure (первоначально написанная Кристофом Грандом, я полагаю):

(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