algorithm - 图值传播算法

我有一个有向图(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):如果v[i] < t[i]

返回true

最简单的实现是将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的频率高几个数量级，也无法奏效。

我想，有些“部分惰性”算法可能会更好，但这只是我的直觉，我无法在此方面取得任何进展。

这是一个众所周知的问题吗？还有其他想法吗？

最佳答案

在您需要评估之前，阻止增量的传播怎么样？ gainValue仅会更新该值，将节点标记为脏节点并将其添加到一组脏节点中。

当您需要评估时，请传播所有已更改节点的增量，从最大的新值开始。这应该为同一节点以及路径上的潜在节点(可能在旅途中得到验证)节省传播多个增量的时间吗？

关于algorithm - 图值传播算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46145641/