Различие в кейсе при динамическом программировании: пример необходим!

19

Я работал над динамическим программированием в течение некоторого времени. Канонический способ оценить рекурсию динамического программирования - создать таблицу всех необходимых значений и заполнять ее построчно. См., Например, Cormen, Leiserson и др .: «Введение в алгоритмы» для введения.

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

Я абстрагируюсь от фактической функции, которая вычисляется, и концентрируюсь на ее рекурсивной структуре. Формально, я считаю recurrrence быть динамическим программированием , если она имеет видd

d(i)=f(i,Γ~d(i))

с , ~ Г д ( я ) = { ( J , д ( J ) ) | JГ д ( я ) } и е некоторой (вычислимому) функция, не используйте d, кроме как через ˜ Γ d .i[0m]×[0n]Γ~d(i)={(j,d(j))jΓd(i)}fdΓ~d

При ограничении детальности на неровные области (слева, вверху слева, сверху, верхние правой, ... из текущей ячейки) один отмечает , что, по существу , три случая (до симметрий и вращения) Валиды рекурсии динамического программирования, которые информируют, как таблица может быть заполнена:Γd

Три случая динамического программирования клеточных зависимостей

Красные области обозначают (чрезмерное приближение) . Случаи один и два допускают подмножества, случай три - наихудший случай (с точностью до преобразования индекса). Обратите внимание, что строго не требуется, чтобы все красные области были покрыты Γ ; Некоторые ячейки в каждой красной части таблицы достаточны, чтобы нарисовать ее красной. Белые области явно необходимы, чтобы не содержать никаких обязательных ячеек.ΓΓ

Примерами для первого случая являются расстояние редактирования и самая длинная общая подпоследовательность , второй случай - для Bellman & Ford и CYK . Менее очевидные примеры включают в себя такие, что работают с диагоналями, а не с рядами (или столбцами), поскольку их можно поворачивать для соответствия предлагаемым случаям; см . ответ Джо для примера.

У меня нет (естественного) примера для случая три, хотя! Итак, мой вопрос: каковы примеры для случая три рекурсии / проблемы динамического программирования?

Рафаэль
источник
2
Случай 3 включает в себя случаи 1 и 2.
Джефф
Нет, это не так, несмотря на внешность. Например, экземпляр случая 1 не может иметь обязательную ячейку в верхней левой области, в то время как экземпляр случая 3 должен иметь обязательную ячейку в верхней левой области. Я отредактировал объяснение, чтобы уточнить.
Рафаэль

Ответы:

15

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

  • Самая длинная возрастающая проблема подпоследовательности требует только одномерной таблицы.

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

  • Но самое главное, динамическое программирование не связано с таблицами ; это о раскручивании рекурсии. Существует множество естественных алгоритмов динамического программирования, в которых структура данных, используемая для хранения промежуточных результатов, не является массивом, потому что повторяющееся повторение не входит в диапазон целых чисел. Два простых примера - найти самый большой независимый набор вершин в дереве и найти самое большое общее поддерево из двух деревьев. Более сложный пример - алгоритм аппроксимации для евклидовой задачи коммивояжера Ароры и Митчелла.(1+ϵ)

JeffE
источник
Спасибо за ваш ответ, но я явно ограничил вопрос двумерными задачами и канонической схемой вычислений на основе таблиц (отредактирован, чтобы сделать эту точку еще яснее). Я знаю о более общих рамках, но не заинтересован в этом на данный момент.
Рафаэль
9
Хорошо, но я действительно думаю, что вы упускаете суть.
Джефф
Поскольку есть много голосов, я подумал, что должен прояснить это: этот пост не отвечает на вопрос и даже не пытается.
Рафаэль
2
@ Рафаэль прав. Мой «ответ» - это не ответ, а критика вопроса, но это было слишком долго для комментария.
Джефф
3

A(m,n)A(m,n1)A(m1,k)k

Это не идеально соответствует требованиям, так как количество столбцов бесконечно, и вычисления обычно выполняются сверху вниз с запоминанием, но я думаю, что стоит упомянуть.

sdcvvc
источник
1
A(m1,A(m,n1))
1
Не уверен, почему этот ответ был отклонен, поскольку это хороший ответ. Функция Аккермана отлично подходит для динамического программирования. В общем, любая рекурсивно определенная функция, которая многократно вычисляется для одних и тех же аргументов, пригодна для динамического программирования. Чтобы увидеть это, нужно только реализовать это и сравнить время работы. То, что занимает годы, чтобы вычислить с помощью обычной функции Аккермана, может занять несколько секунд с функцией динамического программирования.
Жюль
@Jules: Проблема схемы канонических таблиц заключается в том, что вы не знаете (примитивно-рекурсивную) границу размера таблицы априори. Конечно, вы можете сделать запоминание, но не совсем обычным способом. Так что да, это может быть жизнеспособным для DP, но оно не соответствует классу проблем, с которыми связан мой вопрос.
Рафаэль
1
Я не думаю, что для DP требуется, чтобы у вас была априорная привязка к размеру таблицы? На самом деле, как упоминает Джефф, кеш вовсе не обязательно должен быть таблицей. Это может быть любая ассоциативная структура данных. DP на самом деле очень очень простая идея: вы хотите вычислить рекурсивно определенную функцию, но эта функция неоднократно вызывается с теми же аргументами. DP - это оптимизация, при которой вы вводите кеш, чтобы убедиться, что вы вычисляете каждый случай только один раз. Существует множество функций, которые не подходят ни в один из ваших случаев, даже если они являются функциями двух ограниченных целых чисел.
Жюль
2

Это не совсем подходит для случая 3, но я не знаю, отражает ли какой-либо из ваших случаев очень распространенную проблему, используемую для обучения динамическому программированию: матричное умножение цепей . Чтобы решить эту проблему (и многие другие, это только каноническая проблема), мы заполняем матрицу диагональю по диагонали вместо строки за строкой.

Итак, правило примерно такое:

diagMatrix

Джо
источник
1
Написано так, что это действительно не подходит ни для одного случая. Однако, если вы повернете по часовой стрелке на 45 градусов, вы получите вариант 2 (и все подразумеваемые свойства). Это верно и для других примеров, которые работают от диагонали до углов. Но спасибо за упоминание этого!
Рафаэль
@ Рафаэль, это не сразу очевидно, что они эквивалентны, вы можете упомянуть об этом в своем вопросе.
Джо
0

Я знаю, это глупый пример, но я думаю, что простая итерационная проблема, такая как

Найти сумму чисел в квадратной матрице

может претендовать Традиционный «для каждой строки для каждого столбца» вроде как ваш случай 3.

hugomg
источник
-1

Это не совсем то пространство поиска, которое вы ищете, но у меня есть представление о макушке, которое может помочь.

Проблема:

n×nMxM

Ответ

Это может быть решено следующим рекурсивным способом:

k=1+n2xmk,kx<mk,kmi,jkinkjn1/4x>mk,k1/434n2x(34)3n2

0x0
источник
1
Это не пример динамического программирования, не так ли?
Рафаэль