我有一个系统,需要计算每个变量可能的值范围(不需要找到系统的解决方案)。这里是一个示例系统的说明:
每条蓝线都是一个节点(由上面的标签命名),灰色线是节点之间的边缘。有一个初始约束条件:例如,边缘BC可以是0到1之间的任何实数,边缘BE可以是大于或等于9的任何数字。节点不能穿过其他节点。将它们想象为可以伸展和收缩的金属棒,推动蓝色板子四处移动会很有帮助。我的目标是计算每个边缘的最小和最大长度。起始约束条件建立了系统,但最终结果可能比它们更受限制。例如,边缘DF具有(2,∞)的起始最小/最大值,但您可以看到它实际上不能短于3,因为收缩它会将D拉向E,将E向F,EF的最小值为3。我认为最终结果将是这样的: 注意:我需要一个算法,可以扩展到数十万个节点,这些节点将比此示例更密集地连接。它的运行时间不能呈指数级增长,因为我还必须运行此算法数十万次。
我尝试了一种方法,给出了一些更受限制的值,但不是最受限制的值。为了可视化该方法,我基本上将所有板子拉到左边尽可能远的位置,然后记录每个板子的最大位置。然后我做了同样的事情,把它们拉到右边。然后,对于每条边,我只需找到每个板子值之间的差异。这种方法非常有效地找到了最大值,但问题在于当您遇到像此示例中那样的情况时,CD被BC和DE所“锁定”。它不能是6,因为系统只允许它比9短2。我需要一种方式来找到真正的最小值7。我的方法没有捕捉到这种“锁定”关系:当您将C全部移到左侧时,BC为0,当您将D全部移到右侧时,DE为0,但如果CD为6,则它们不能都为0。
在这个例子中,很容易看出CD受BE限制,但实际上,系统会比例子更加密集和庞大,找到这样的情况似乎并不容易。如果该方法涉及在局部周围搜索,我担心它的可扩展性会很差,但那可能是唯一的方法。
如果将其建模为线性规划问题(AB + BC = AC,AB > 1等),也许可以利用该系统的某些属性:所有限制的系数都是1,且限制中只有加法和减法。
有人有什么建议来解决这个问题吗?或者对于我应该现实地希望的运行时间复杂度有任何见解吗?谢谢!