0

我一直在使用前向后向算法来找到从状态 1 到状态 N 的最有效（由成本函数确定，该成本函数取决于当前状态与下一个状态的不同）路径。在下图中，可以看到问题的简短版本，每个状态只有 3 个状态和 2 个节点。我对此进行了前后算法，并找到了正常的最佳路径。图片中的红色位是代码中前向传播位期间检查的路径。

现在有趣的是，我现在想找到最好的 3-State Length 路径（和以前一样），但现在只有第一个 State 中的节点是已知的。其他 4 个现在是自由浮动的，可以被视为处于任何状态（状态 2 或状态 3）。我想知道你们是否知道如何做到这一点。

图片：http: //i.imgur.com/JrQ2tul.jpg 在此处输入图像描述

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

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

更好地描述问题。

4

1 回答 1

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

如果计算标准很昂贵，您可能希望按需计算并将其存储在地图中。

于 2014-06-16T19:29:56.083 回答