Я изучал в прошлом классические задачи и алгоритмы DP (монеты, самая длинная возрастающая подпоследовательность, самая длинная общая подпоследовательность и т. Д.).
Я знаю, что эти алгоритмы имеют практические приложения (то есть генетические алгоритмы, просто чтобы назвать один). Однако я сомневаюсь, есть ли у этих алгоритмов практическое применение в современной информатике, где размер входных данных очень велик, а проблемы не могут быть решены только на одной машине.
Я хочу сказать, что эти алгоритмы довольно сложно распараллелить (например, Параллельное динамическое программирование ), а занятость памяти квадратична в большинстве формулировок, что затрудняет обработку достаточно больших входных данных.
У кого-нибудь есть примеры использования этого в реальном мире?