图值传播算法
Graph value propagation 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): return 如果 v[i] < t[i]
最直接的实现将存储 v[i]、t[i] 和每个节点的传出箭头。在 increaseValue(i, x) 上，它会沿着所有传出箭头传播值（像许多其他图形算法一样使用一组 "open" 节点）。 v[i] 与每个节点一起存储，evaluate(i) 是微不足道的。
由于increaseValue比其他操作频繁得多，这种急于求成的做法似乎很浪费。所以我想知道，根据需要重新计算 v[i] 的某些惰性传播是否会更有效率。为此，我将 w[i] 保持为 increaseValue(i, x) 中所有 x 的最大值，并在 evaluate(j) 需要时即时计算 v[j] 。它可以计算为所有节点 n[i] 上 w[i] 的最大值，从这些节点有一条通往 n[j] 的路径。实际上，一旦我知道 v[j] >= t[j]，
确切的值 v[j] 无关紧要，我可以停止计算。
不幸的是，这种懒惰的算法效率很低，所以即使 increaseValue 比 evaluate 高出几个数量级，它也没有回报。
我想，某些 "partially lazy" 算法可能会更好，但这只是我的直觉，我无法取得任何进展。
这是一个众所周知的问题吗？还有其他想法吗？
在需要评估之前，如何阻止增量的传播？ increaseValue 只会更新值，将节点标记为脏并将其添加到一组脏节点中。
当您需要评估时，传播所有更改节点的增量，从最大的新值开始。这应该避免为同一节点和路径上的潜在节点传播多个增量（可能会在旅途中得到验证）？
我对 "partially lazy" 算法有一个简单的想法（没有解决方案，只是一个想法）。
让我们将我的问题中的 "most straightforward implementation" 称为 告诉 算法，因为每个节点都会告诉其后继者该做什么。让我们将 "lazy algorithm" 重命名为 asking 算法，因为每个节点都会询问其前任是否有事情要做。
箭头可以分为讲述和询问。所有指示箭头在 increase 后得到处理，而询问箭头等到 evaluate。我猜，这个划分不能是任意的：对于任意两个箭头(n[i], n[j])和(n[j], n[k])，我无法想象前者在询问而后者在告诉时如何处理，所以这种情况必须被禁止。
当有许多节点只有传入箭头很少 evaluated 时，这可能会有很大帮助，这似乎是这种情况。
大概可以和其他答案的思路结合起来。
我有一个有向图 (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): return 如果v[i] < t[i] 则为真
最直接的实现将存储 v[i]、t[i] 和每个节点的传出箭头。在 increaseValue(i, x) 上，它会沿着所有传出箭头传播值（像许多其他图形算法一样使用一组 "open" 节点）。 v[i] 与每个节点一起存储，evaluate(i) 是微不足道的。
由于increaseValue比其他操作频繁得多，这种急于求成的做法似乎很浪费。所以我想知道，根据需要重新计算 v[i] 的某些惰性传播是否会更有效率。为此，我将 w[i] 保持为 increaseValue(i, x) 中所有 x 的最大值，并在 evaluate(j) 需要时即时计算 v[j] 。它可以计算为所有节点 n[i] 上 w[i] 的最大值，从这些节点有一条通往 n[j] 的路径。实际上，一旦我知道 v[j] >= t[j]，
确切的值 v[j] 无关紧要，我可以停止计算。
不幸的是，这种懒惰的算法效率很低，所以即使 increaseValue 比 evaluate 高出几个数量级，它也没有回报。
我想，某些 "partially lazy" 算法可能会更好，但这只是我的直觉，我无法取得任何进展。
这是一个众所周知的问题吗？还有其他想法吗？
在需要评估之前，如何阻止增量的传播？ increaseValue 只会更新值，将节点标记为脏并将其添加到一组脏节点中。
当您需要评估时，传播所有更改节点的增量，从最大的新值开始。这应该避免为同一节点和路径上的潜在节点传播多个增量（可能会在旅途中得到验证）？
我对 "partially lazy" 算法有一个简单的想法（没有解决方案，只是一个想法）。
让我们将我的问题中的 "most straightforward implementation" 称为 告诉 算法，因为每个节点都会告诉其后继者该做什么。让我们将 "lazy algorithm" 重命名为 asking 算法，因为每个节点都会询问其前任是否有事情要做。
箭头可以分为讲述和询问。所有指示箭头在 increase 后得到处理，而询问箭头等到 evaluate。我猜，这个划分不能是任意的：对于任意两个箭头(n[i], n[j])和(n[j], n[k])，我无法想象前者在询问而后者在告诉时如何处理，所以这种情况必须被禁止。
当有许多节点只有传入箭头很少 evaluated 时，这可能会有很大帮助，这似乎是这种情况。
大概可以和其他答案的思路结合起来。