Архив за день: Июнь 23, 2015

Rosalind.info — динамическое программирование

Несмотря на то, что кэширование может быть чрезвычайно полезным для ускорения вычисления рекуррентных отношений, оно не решает проблему переполнения стека вызовов. Например, в ходе вычисления n-го числа Фибоначчи по формуле

Формула чисел Фибоначчистек будет содержать n вызовов F(n - 1), F(n - 2), …, F(1), F(0). Это означает, что при значениях n около 1000 стек вызовов Python исчерпается, возбудив ошибку времени выполнения (RuntimeError).

Для того чтобы избежать переполнения стека, можно воспользоваться техникой динамического программирования. В широком смысле динамическое программирование означает, что решение задачи зависит от решения ограниченного числа подзадач меньшего размера; очевидно, это утверждение справедливо для рекуррентных отношений. Вместе с тем, зачастую под динамическим программированием подразумевается частный способ его реализации, при котором вычисления производятся «снизу вверх» (bottom-up approach). Это означает, что сначала вычисляются простые задачи, а затем на их основе агрегируются решения более сложных задач. Именно этот подход позволяет избавиться от рекурсии и, следовательно, переполнения стека.

Динамическое программирование широко используется в биоинформатике, прежде всего для выравнивания биополимеров (участков ДНК и белков). В системе Rosalind.info выравниванию посвящены задачи EDIT, EDTA, GLOB, LOCA, GAFF, LAFF, OSYM, KSIM и другие. Другое применение динамического программирования — распознавание с использованием скрытых марковских моделей (алгоритм Витерби).

Как и в случае кэширования, динамическое программирование может быть реализовано в Python с применением шаблонов императивного программирования, но больший интерес представляет использование функционального подхода, в частности, декораторов и генераторов.

Читать далее Rosalind.info — динамическое программирование