algorithm - 如何用简单的前向后向算法解决这个问题？

Question

我一直在研究 forward-backward algorithm找到从状态 1 到状态 N 的最有效(由取决于当前状态与下一个状态的差异的成本函数确定)路径。在下图中，可以看到问题的简短版本只有 3状态和每个状态 2 个节点。我对此进行了前向后向算法，并找到了正常的最佳路径。图中红色位为代码中前向传播位检查的路径。

现在有趣的是，我现在想找到最佳的 3 状态长度路径(和以前一样)，但现在只有第一个状态中的节点是已知的。其他 4 个现在是自由 float 的，可以被认为是在任何状态(状态 2 或状态 3)。我想知道你们是否知道如何做到这一点。

图片:http://i.imgur.com/JrQ2tul.jpg

注意:请记住，原始问题由大约 25 个状态和每个状态 100 个节点组成。因此，您将知道状态 1 中大约 100 个节点的状态，但其他 24*100 个节点是无状态的。在这种情况下，我想找到一条 25 个州长度的路径(成本最低)。

附录:有人指出更好的算法是维特比算法。所以这里有一个问题，更多的变量被抛出。你们能解释一下如何实现吗？适用相同的规则，路径应从状态 1 中的节点之一(节点 a 或节点 b)开始。此外，在这种情况下，使用范数的成本函数没有意义，因为我们只有一个属性(节点大小)，但在实际问题中我期望有更多属性。

Answer 1

对于您的问题，Dijkstra 算法的变体可能比前向-后向算法更快，因为它不会同时分析所有节点。 Dijkstra毕竟是DP算法。

让一个节点由

指定

Node:
   Predecessor : Node
   Total cost : Number      
   Visited nodes : Set of nodes  (e.g. a hash set or other performant set)

初始化算法

open set : ordered (by total cost) set of nodes = set of possible start nodes (set visitedNodes to the one-element set with the current node)
           ( = {a, b} in your example)

然后执行算法:

do
    n := pop element from open set
    if(n.visitedNodes.count == stepTarget)
        we're done, backtrace the path from this node
    else
        for each n2 in available nodes
            if not n2 in n.visitedNodes
                push copy of n2 to open set (the same node might appear multiple times in the set):
                    .cost := n.totalCost + norm(n2 - n)
                    .visitedNodes := n.visitedNodes u { n2 }  //u = set union
                    .predecessor := n                    
        next
loop

如果计算范数的成本很高，您可能希望按需计算并将其存储在 map 中。