使用动态规划时，捕获整个路径以获得最小和？
When using dynamic programming, capturing the entire path for a min-sum?
我正在尝试使用 Viterbi min-sum 算法，该算法试图找到通过一堆节点的路径，该路径最小化针对某些固定输入的整体汉明距离（"xor two numbers and count the resulting bits" 的花哨术语）。
我了解如何使用 DP 来计算整体的最小距离，但我无法使用它来也捕获对应于最小距离的相应路径。
在每个节点记忆路径似乎真的很耗费内存。有没有标准的方法来处理这类问题？
编辑：
http://i.imgur.com/EugiEWG.jpg
这是我正在谈论的示例网格。一般的想法是找到最接近模拟输入位串的网格路径，误差最小（通过最小化整体汉明距离或不匹配位的数量来衡量）。
如您所见，我输入字符串的第一个块是 01，我可以在网格的第 1 列中遍历那里。下一个块是 10，我可以移动到第 2 列。下一个块是 11。到目前为止还不错。下一个块是 10，这是一个问题，因为我无法从现在的位置达到那个状态，所以我必须转到下一个最好的东西 (00)，其余的可以很好地填充。
但这可能会变得更加复杂。我需要能够以某种方式获得最小汉明距离的相应路径。
（这个练习的重点是格子表示什么是实际有效的转换，而输入字符串是你通过电信接收的东西，可能会出现乱码，并且到处都有不正确的位。这个程序试图弄清楚通过最小化错误，输入字符串应该是什么）。
有常用的 "follow path backwards" 技术，只需要 table 个值（但是整个 table 个值，没有 "keep only the most recent part" 作弊）。算法很简单：从最后开始，决定你来自哪条路。你可以做出那个决定，因为要么只有一种方法，如果你来自它，你会计算出与存储的值匹配的值，或者几个结果相同的值，你选择哪个都无关紧要。
同时存储 "back-pointers" 的 table 并不需要太多 space（大约与权重 table 一样多，但实际上您可以省略大部分table 的权重，如果你这样做的话），这样做可以让你有一个更简单的向后阶段：只需跟随指针。那确实是路径，只是倒着存储而已。
你说得对，直接计算路径的方法 space 很昂贵。
这个问题经常出现在 DNA sequencing, where the cost is prohibitive. There are a number of ways to overcome it (see more here):
如果您愿意将执行时间加倍，则最多可以减少 space 的平方根（参见上面 link 中的 2.1.1）。
使用压缩树，可以对数减少其中一个维度（见上文link中的2.1.2）。
我正在尝试使用 Viterbi min-sum 算法，该算法试图找到通过一堆节点的路径，该路径最小化针对某些固定输入的整体汉明距离（"xor two numbers and count the resulting bits" 的花哨术语）。
我了解如何使用 DP 来计算整体的最小距离，但我无法使用它来也捕获对应于最小距离的相应路径。
在每个节点记忆路径似乎真的很耗费内存。有没有标准的方法来处理这类问题？
编辑：
http://i.imgur.com/EugiEWG.jpg
这是我正在谈论的示例网格。一般的想法是找到最接近模拟输入位串的网格路径，误差最小（通过最小化整体汉明距离或不匹配位的数量来衡量）。
如您所见，我输入字符串的第一个块是 01，我可以在网格的第 1 列中遍历那里。下一个块是 10，我可以移动到第 2 列。下一个块是 11。到目前为止还不错。下一个块是 10，这是一个问题，因为我无法从现在的位置达到那个状态，所以我必须转到下一个最好的东西 (00)，其余的可以很好地填充。
但这可能会变得更加复杂。我需要能够以某种方式获得最小汉明距离的相应路径。
（这个练习的重点是格子表示什么是实际有效的转换，而输入字符串是你通过电信接收的东西，可能会出现乱码，并且到处都有不正确的位。这个程序试图弄清楚通过最小化错误，输入字符串应该是什么）。
有常用的 "follow path backwards" 技术，只需要 table 个值（但是整个 table 个值，没有 "keep only the most recent part" 作弊）。算法很简单：从最后开始，决定你来自哪条路。你可以做出那个决定，因为要么只有一种方法，如果你来自它，你会计算出与存储的值匹配的值，或者几个结果相同的值，你选择哪个都无关紧要。
同时存储 "back-pointers" 的 table 并不需要太多 space（大约与权重 table 一样多，但实际上您可以省略大部分table 的权重，如果你这样做的话），这样做可以让你有一个更简单的向后阶段：只需跟随指针。那确实是路径，只是倒着存储而已。
你说得对，直接计算路径的方法 space 很昂贵。
这个问题经常出现在 DNA sequencing, where the cost is prohibitive. There are a number of ways to overcome it (see more here):
如果您愿意将执行时间加倍，则最多可以减少 space 的平方根（参见上面 link 中的 2.1.1）。
使用压缩树，可以对数减少其中一个维度（见上文link中的2.1.2）。