algorithm - 在马尔可夫模型中找到两个顶点之间具有最大似然的路径

Question

给定一个马尔科夫模型，它有一个名为 的开始状态S和一个名为 的退出状态F，该模型可以表示为有向图，并带有一些约束：

1. 每条边都有一些权重落在 (0,1] 范围内作为转移概率。

2. 从每个节点出来的边的权重总和为 1。

问题是如何对开始状态和退出状态之间的路径进行排序？或者，更准确地说，如何找出概率最高的路径？

一方面，权重是概率，因此路径越长，产品越小，因此一种启发式策略是选择更短的路径和更大的权重候选；但是这个问题可以转化为最短路径问题还是使用一些量身定制的维特比算法或一些DP算法来解决？

Answer 1

将您的概率转换为日志空间（日志库无关紧要）。现在路径的概率变为对数空间权重的总和（因为log(ab) = log(a) + log(b)。由于权重/概率<1，对数空间中的权重都是负数，并且路径权重最高。

为了将其更多地引入常规问题，您可以否定所有日志空间权重，以便它们都是正数，并且您正在寻找最低的总和。此时，您可以运行标准算法（Dijkstra 将非常简单且非常快速）来找到您正在寻找的路径。如果你有总和然后否定它并计算指数以获得概率。

TL;DR：将所有权重 w 替换为 -log(w) 并使用新权重运行 Dijkstra。