我正在尝试使用 Viterbi min-sum 算法，该算法试图找到通过一堆节点的路径，以最小化针对某些固定输入的整体汉明距离(“xor two numbers and count the resulting bits”的奇特术语) .
我了解如何使用 DP 来计算总体上的最小距离，但我无法使用它来还捕获对应于最小距离的相应路径。
在每个节点内存路径似乎会占用大量内存。是否有处理此类问题的标准方法？
编辑:
http://i.imgur.com/EugiEWG.jpg
这是我正在谈论的格子示例。一般的想法是找到最接近模拟输入位串的网格路径，误差最小(通过最小化整体汉明距离或不匹配位的数量来衡量)。
如您所见，我输入字符串的第一个 block 是 01，我可以在网格的第 1 列中遍历那里。下一个 block 是 10，我可以移动到第 2 列。下一个 block 是 11。到目前为止还不错。下一个 block 是 10，这是一个问题，因为我无法从我现在所在的位置达到那个状态，所以我必须转到下一个最好的东西 (00)，其余的可以很好地填充。
但这可能会变得更加复杂。我需要能够以某种方式获得到最小汉明距离的相应路径。
(这个练习的重点是格子表示什么是实际有效的转换，而输入字符串是你通过电信接收到的东西，可能会出现乱码，并且到处都有不正确的位。这个程序试图弄清楚什么是输入字符串应该通过最小化错误)。
最佳答案
有通常的“向后跟踪路径”技术，只需要值表(但是整个值表，没有“只保留最近的部分”作弊)。算法很简单:从最后开始，决定你来自哪条路。你可以做出那个决定，因为要么只有一种方法，如果你来自它，你会计算出与存储的值匹配的值，或者几个结果相同的值，你选择哪个都无关紧要。
存储“反向指针”表也不会占用太多空间(大约与权重表一样多，但如果这样做，您实际上可以省略大部分权重表)，这样做让你有一个更简单的倒退阶段:只需按照指示。这确实是 路径，只是向后存储。
关于algorithm - 使用动态规划时，捕获整个路径以获得最小和？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31458340/