Алгоритмы динамического программирования и использования в реальном времени

Question

В прошлом я изучал классические задачи и алгоритмы DP (монеты, самая длинная возрастающая подпоследовательность, самая длинная общая подпоследовательность и т. Д.).

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

Я считаю, что эти алгоритмы довольно трудно распараллелить (то есть Parallel Dynamic Programming), а занятость памяти в большинстве формулировок квадратична, что затрудняет обработку входов, которые достаточно велики.

У кого-нибудь есть случаи использования в реальном мире?

Answer 1

Практическое применение: diff. Это важная утилита Linux, которая находит различия между двумя файлами, решая проблему longest common subsequence с использованием алгоритма DP.

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

Использование памяти: Часто для ускорения использования памяти часто используется скользящее окно. Фибоначчи, когда решается с использованием наивного восходящего DP, требует O (n) памяти. Скользящее окно улучшает это до O (1) памяти (я знаю magical constant time solution, но это не так).

Параллелизация: Сверхнизкие DP часто легко распараллеливаются. Снизу могут быть или не быть. Пример @ amit (распараллеливание самой длинной общей подпоследовательности) является хорошим, когда любые плиты каждой диагонали могут быть решены независимо, если известны предыдущие диагонали.

Answer 2

The longest common subsequence Проблема и Longest common substring problem иногда важны для анализа строк [например, анализ последовательности генов]. И они могут быть эффективно решены с использованием динамического программирования.

Примечание вы можете распараллелить алгоритм: вы делаете это в итерации по диагоналям [слева, вниз направо, вверх] - так всего 2n-1 итераций. И в каждой диагонали: каждая ячейка не зависит от других ячеек в этой диагонали - поэтому здесь можно распараллелить, каждый поток будет иметь блок ячеек в этой диагонали.

Обратите внимание, что синхронизация данных с использованием этого метода также минимальна: каждый поток должен только передавать данные в свои «соседние потоки», поэтому это можно сделать, даже если память не используется совместно.

Также обе проблемы, как упоминалось в @larsmans, могут использовать линейное пространство - в каждой точке вам нужно «запомнить» текущие + 2 последних диагоналя, а не всю матрицу.

Другая распространенная проблема, которая решается с помощью динамического программирования, - polynomial interpolation. Интерполяция может быть эффективно выполнена с использованием Newton Interpolation, который сначала должен вычислить divided differences, который построен с использованием динамического программирования.