我一直在使用前向后向算法来找到从状态 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)开始。此外,在这种情况下,使用规范的成本函数没有意义,因为我们只有一个属性(节点大小),但在实际问题中,我期待更多的属性。