图值传播算法

Question

我有一个有向图(N, A),每个节点n[i]都有一个值v[i]和一个阈值t[i].对于每个箭头(n[i], n[j]),不变量v[i] <= v[j]成立.我需要有效地实现以下操作:

• increaseThreshold(i, x):设置t[i] = max(t[i], x).这是微不足道的,只是为了完整性.
• increaseValue(i, x):v[i] = max(v[i], x)根据需要设置和增加其他值,以便保持上述不变量.
• evaluate(i):如果返回true v[i] < t[i]

最简单的实现将存储v[i],t[i]以及每个节点的传出箭头.在increaseValue(i, x),它会沿着所有传出箭头传播值(使用一组"开放"节点,就像许多其他图形算法一样).v[i]与每个节点一起存储,evaluate(i)是微不足道的.

由于increaseValue比其他操作更频繁,这种急切的方法似乎是浪费.所以我想知道,如果v[i]根据需要重新计算一些惰性传播可能会更有效.对于这一点,我想保持w[i]作为最大的是x来自increaseValue(i, x)和计算v[j]时的飞行evaluate(j)需要它.它可以计算为有路径的w[i]所有节点的最大值.实际上,一旦我知道,确切的值无关紧要,我可以停止计算.n[i]n[j]v[j] >= t[j]v[j]

不幸的是,这种惰性算法的效率非常低,因此即使increaseValue频率高于数量级,它也不会得到回报evaluate.

我想,一些"部分懒惰"的算法可能会更好,但这只是我的直觉,我无法用它取得任何进展.

这在某种程度上是一个众所周知的问题吗？还有其他想法吗？

Answer 1

在需要评估之前阻止增量的传播怎么样？increaseValue只会更新值，将节点标记为脏节点并将其添加到脏节点集合中。

当您需要评估时，从最大的新值开始传播所有更改节点的增量。这应该可以节省传播同一节点和路径上潜在节点的多个增量（这可能会在运行中得到验证）？