给定一个马尔可夫模型，它有一个名为 S 的起始状态和一个名为 F 的退出状态，这个模型可以表示为一个有向图，有一些约束:
每条边都有一些权重落在范围 (0,1] 作为转移概率。
从每个节点出来的边的权重总和为 1。
问题是如何对起始状态和退出状态之间的路径进行排序？或者，更准确地说，如何找到概率最高的路径？
一方面，权重是概率，路径越长，乘积越小，因此一种启发式策略是选择路径较短、权重较大的候选；但是这个问题是否可以转换为最短路径问题或使用一些量身定制的维特比算法或一些DP算法来解决？
最佳答案
将概率转换为对数空间(对数底无关紧要)。现在路径的概率变成对数空间权重的总和(因为 log(ab) = log(a) + log(b) 。由于权重/概率 <1，log 中的权重空间将全部为负，路径具有最高权重。
为了将其更多地纳入常规问题，您可以对所有对数空间权重取反，以便它们都是正数，并且您正在寻找最低的总和。此时你可以运行标准算法(Dijkstra 会很简单而且非常快)来找到你正在寻找的路径。如果您有总和，则将其取反并计算指数以获得概率。
TL;DR:将所有权重 w 替换为 -log(w) 并使用新权重运行 Dijkstra。
关于algorithm - 在马尔可夫模型中找到两个顶点之间具有最大似然的路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38894477/