我尝试使用维特比最小和算法，该算法试图找到通过一组节点的路径，这些节点最小化了相对于某个固定输入的总体汉明距离（花式术语“异或两个数字并计算结果位”）。
我知道如何使用dp计算总的最小距离，但是我很难使用它来捕获对应于最小距离的相应路径。
似乎记住每个节点上的路径会占用大量内存有标准的方法来处理这些问题吗？
编辑：
http://i.imgur.com/EugiEWG.jpg
这是一个我所说的格子的样本一般的想法是在最小的误差（通过最小化总体汉明距离或不匹配比特的数量来测量）下，找到通过最接近模拟输入比特串的网格的路径。
如您所见，输入字符串的第一个块是01，我可以遍历网格的第1列。下一块是10，我可以在第2列中移动到那里。下一块是11。到目前为止还不错下一块是10，这是一个问题，因为我无法从现在的状态达到，所以我必须去下一个最好的东西（00），其余的可以填补罚款。
但这会变得更复杂我需要能够得到相应的路径到最小的汉明距离。
（本练习的重点是网格表示实际有效的转换，而输入字符串是通过远程通信接收到的，可能会被混淆，并且在这里和那里有不正确的位。这个程序试图通过最小化错误来确定输入字符串应该是什么。
最佳答案
有一种常见的“向后跟踪路径”技术，只需要值表（但整个值表，不欺骗“只保留最新的部分”）算法很简单：从结尾开始，决定你来自哪里你可以做出这样的决定，因为要么只有一种方法，如果你来自它，你会计算出与存储的值相匹配的值，要么有几种方法会得到相同的值，而你选择哪一种并不重要。
同时存储一个“back pointers”表不会占用太多空间（大约和权重表一样多，但是如果这样做的话，实际上可以省略大部分权重表），这样做可以让您有一个更简单的向后阶段：只需跟随指针这就是路径，只是向后存储。