基于循环图中先前节点查找节点成本的算法
Algorithm for finding cost of a node based on preceding nodes in a cyclic graph
我有一个部分或全部循环图，我想根据前面节点成本的加权和来计算每个节点的成本。没有传入边的节点具有分配给它们的固定成本。
例如，下图的每个节点都标有其计算成本（节点 2 的成本是固定的），每条边都标有前一个节点的权重。这样，节点1.33的cost由1*0.33 + 0.5*2计算得到。
我目前使用迭代方法将每个节点的成本计算到某个 epsilon 以内，但我正在寻找一种可以准确计算成本的算法。上面的示例非常简单，实际问题涉及每个强连接组件约 100 个节点。对可以解决这个问题的算法有什么建议吗？
您可以构建线性方程组并求解它们。在您给出的示例中，节点 2 是固定的，因为它没有传入边。将值 x 赋值给右上角节点，y 赋值给左上角节点，z 赋值给下部节点，构建以下线性方程组
x = 0.5*2 + 1*y
y = 0.5*z
z = 0.5*x
x=1.33333, y=0.333333, z=0.666667
我有一个部分或全部循环图，我想根据前面节点成本的加权和来计算每个节点的成本。没有传入边的节点具有分配给它们的固定成本。
例如，下图的每个节点都标有其计算成本（节点 2 的成本是固定的），每条边都标有前一个节点的权重。这样，节点1.33的cost由1*0.33 + 0.5*2计算得到。
我目前使用迭代方法将每个节点的成本计算到某个 epsilon 以内，但我正在寻找一种可以准确计算成本的算法。上面的示例非常简单，实际问题涉及每个强连接组件约 100 个节点。对可以解决这个问题的算法有什么建议吗？
您可以构建线性方程组并求解它们。在您给出的示例中，节点 2 是固定的，因为它没有传入边。将值 x 赋值给右上角节点，y 赋值给左上角节点，z 赋值给下部节点，构建以下线性方程组
x = 0.5*2 + 1*y
y = 0.5*z
z = 0.5*x
x=1.33333, y=0.333333, z=0.666667