图值传播算法

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)：如果 v[i] < t[i]，则返回 true。

最直接的实现方法是在每个节点中存储 v[i]、t[i] 和所有出边。在执行 increaseValue(i, x) 操作时，它会沿着所有出边传播该值（使用类似许多其他图算法的“打开”节点集合）。由于每个节点都存储了 v[i]，因此 evaluate(i) 是简单的。

由于 increaseValue 操作比其他操作频繁得多，这种急切的方法似乎是浪费的。因此我想知道，是否可以采用一些懒惰的传播方式来重新计算需要的 v[i]，从而提高效率？为此，我会维护 w[i] 作为所有 increaseValue(i, x) 的 x 值的最大值，并在需要时直接计算出 v[j]。它可以计算为从所有路径上的节点 n[i] 中选择最大的 w[i] 来计算 v[j]。实际上，一旦我知道 v[j] >= t[j]，精确值 v[j] 就无关紧要了，我可以停止计算。

不幸的是，这种懒惰算法非常低效，即使 increaseValue 比 evaluate 频繁几个数量级，也不值得采用。

我想象中可能有一些“部分懒惰”的算法更好，但这只是我的直觉，我对此没有任何进展。

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

- maaartinus

---

@Rishav 是的，这些操作将一遍又一遍地重复执行。 - maaartinus

为什么increaseThreshold必须传播？它可能会更新t[i]，但为什么它会影响其他节点？ - algrid

@algrid 谢谢，已修复，这是一个“心理笔误”。 - maaartinus

你说边 n[i] -> n[j] 意味着 v[i] >= v[j]，难道不应该是 v[j] >= v[i] 吗？否则我就无法理解传播。 - Matt Timmermans

@StefanHaustein 我想不会。我可以根据需要将出站和/或入站箭头与每个节点一起存储。在懒惰的方法中，我会进行深度优先搜索，并跟踪已访问的节点。这很简单高效，除了节点太多的事实。 - maaartinus

Answer 1

将增量的传播推迟到需要评估之前如何？increaseValue仅更新值，标记节点为脏，并将其添加到脏节点集合中。

当您需要评估时，请按从最大新值开始，传播所有更改节点的增量。这应该可以减少对同一节点和潜在路径上的节点进行多次增量传播的情况（这可能会在过程中得到验证）。

- Stefan Haustein

---

不错！这肯定是一个好主意，而且实现也很简单。通过在值小于感兴趣的阈值时停止，可以稍微优化它。这样可以最小化总工作量。 +++ 它非常灵活：后台线程可以轮询优先队列，这样 evaluate 不会被所有工作减慢（恶化总工作量但提高延迟）。 - maaartinus

Answer 2

我有一个简单的想法来实现“部分懒惰”算法（没有解决方案，只是一个想法）。

让我们称我的问题中“最直接的实现”为告知算法，因为每个节点都会告诉它的后继节点该做什么。让我们将“懒惰算法”重命名为询问算法，因为每个节点都会询问它的前驱节点是否有事情要做。

箭头可以被分成告知和询问两种类型。所有的告知箭头在increase之后被处理，而询问箭头则等待evaluate。我猜这个分区不能是任意的：对于任何两个箭头(n[i], n[j])和(n[j], n[k])，我无法想象如何处理前者是询问而后者是告知的情况，所以这种情况必须被禁止。

当有许多节点只有入射箭头且很少被evaluate时，这可能会有很大帮助。

它可能可以与其他答案中的想法结合起来。

- maaartinus