如何在此约束系统中有效地找到变量的最小值和最大值？

Question

我有一个系统,我需要计算每个变量的可能值范围(我不需要找到系统的解决方案).以下是示例系统的说明:

每条蓝线都是一个节点(由它上面的标签命名),灰线是节点之间的边缘.给出了初始约束:例如,边缘BC可以是0和1之间的任何实数,并且边缘BE可以是大于或等于9的任何数.节点不能跨越其他节点.将它们想象成可以伸展和缩回的金属条是有帮助的,推动蓝色板周围.

我的目标是为每条边计算它们的最小和最大长度.起始约束设置了系统,但最终结果可能比它们更受限制.例如,边缘DF的起始最小值/最大值为(2,∞),但是你可以看到它实际上不能短于3,因为收缩它将D拉入E,E拉向F,而EF有一个至少为3.最终的结果就是这个,我相信:

需要注意的是,我需要一种可以扩展到数十万个节点的算法,这个节点比这个例子更密集.它不能以指数方式增加运行时间,因为我还必须运行这个算法数十万次.

我尝试了一种方法,它给出了一些更多约束值,但不是最受约束的值.为了使方法可视化,我基本上尽可能地将所有板拉到左边,然后记录每个板的最大位置.然后我做了同样的事情,将它们拉到右边.然后,对于每个边,我只是找到每个板的值之间的差异.此方法非常有效地找到最大值,但问题是当您遇到类似于此示例的情况时,其中CD被BC和DE"锁定"到BE.它不能是6,因为系统只允许它比9短.我需要一种方法来找到真正的最小值7.我的方法不捕获"锁定"关系:当你拉C全部在左边的路上,BC是0,当你把D一直拉到右边时,DE是0,但如果CD是6,它们不能都是0.

在这个例子中,很容易看出CD受到BE的约束,但在实践中,系统会比例子更密集和更大,并且发现这种情况似乎并非易事.如果该方法涉及在本地搜索它,我担心它会扩展得很差,但这可能是唯一的方法.

如果将其建模为线性规划问题(AB + BC = AC,AB> 1等),则可能会利用该系统的某些属性:约束的所有系数均为1,并且约束中只有加法和减法.

有没有人对如何解决这个问题有任何建议？或者对我应该实际希望的运行时间复杂程度有任何见解？谢谢!

Answer 1

好吧，我想我已经弄清楚了。感谢所有回复的人，这让我进行了一些有用的研究。

我能够利用这样一个事实：我不是每次在不同的图上运行算法，而是在不断修改的同一个图上运行算法。我可以保留旧值并每次更新它，包含对本地更改区域的更新。如果新的变化不是太剧烈，传播不应该太远。

该算法相当直观。我走在正确的轨道上，但我错过了传播步骤。事情是这样的：

看看这张图片，把它想象成一个物理系统：有一些蓝色的板，它们之间有可以收缩和膨胀的条形条。为了找到特定条形的最短长度，我将所有板尽可能地向左拉。在杆的右板上保持向左的压力，我将其左板尽可能地拉向它。该运动将位置变化传播到与其连接的所有条形。它可能会将右板向后移动一点，这很好。运动的能量被周围杆的额外松弛所消耗。一旦能量在系统中波动并稳定下来，我就会记录板之间的最终距离。

找到最长的条是相同的：我将板一直向左移动，然后将右侧板尽可能远离左侧。

如果我缓存将所有内容向左移动和向右移动所有内容的位置，这些值有助于快速计算结果。当图表更改时，我可以以类似的方式更新这些位置，从而使大部分工作保持本地化。

从技术上讲，这不是线性的，但根据我的数据，大多数情况下都是线性的。