Sav*_*era 5 algorithm dynamic-programming
我过去曾研究过经典的DP问题和算法(硬币,最长的后续子序列,最长的常见子序列等).
我知道这些算法具有实际应用(即遗传算法,仅举一例).我要问的是,如果这些算法在现代计算机科学中具有实际应用,其中输入的大小非常大并且问题不能仅在一台机器上解决.
我的观点是这些算法很难并行化(即并行动态编程),并且在大多数公式中存储器占用是二次的,这使得很难处理相当大的输入.
任何人都有这个真实世界的用例吗？
实际应用:diff.这是一个必不可少的Linux实用程序,它通过使用DP算法解决最长的常见子序列问题来查找两个文件之间的差异.
使用DP算法是因为在许多情况下它们是唯一实用的解决方案.此外,他们没有任何问题.
内存使用情况:通常,可以使用滑动窗口来显着降低内存使用量.Fibonacci,当使用天真的自下而上的DP解决时,需要O(n)内存.一个滑动窗口将其改进为O(1)内存(我知道神奇的恒定时间解决方案,但这不是重点).
并行化:自上而下的DP通常很容易并行化.自下而上可能会也可能不会.@ amit的例子(并行化最长的公共子序列)是一个很好的例子,只要先前的对角线已知,任何给定的对角线的瓦片都可以独立解决.