python - 尽可能快地找到图中任何可行的流

Question

我有一个带有下限和上限的流程图，我的任务是尽快找到任何可行的解决方案。我发现了许多最大/最小流量的算法和方法等(也很多时候使用可行的解决方案作为起点)，但没有任何具体的可行解决方案。有没有专门针对它且快速的算法/方法？

Answer 1

所以我终于有时间总结一下了。我使用的解决方案是获取初始图形并按以下步骤对其进行转换。

(权重按以下顺序排列:下限、电流、上限。)

<强>1。通过 (0, 0, 无穷大) 的边将 t 连接到 s。

<强>2。到每个节点 初始图添加余额值等于:(下限之和 传入边 - 传出边的下界之和)。

<强>3。设置上部 每条边的边界为(上限 - 下限)。设置下限 各边的电流为0。

<强>4。现在创建新的 s (s') 和新的 t (t')，这将是我们新的开始和结束(不要删除图中已有的 s 和 t，它们刚刚变成 正常节点)。

<强>5。创建从 s' 到每个顶点的边，并使用 (0, 0，vertex.balance)边界。

<强>6。从每个具有负平衡的顶点到 t' 创建边 (0, 0、abs(vertex.balance))。

<强>7。运行 Ford-Fulkerson(或您选择的其他最大流量算法) 在新图表上。

<强>8。对于初始图的每条边的总和值 边缘与转换前的初始旧下界，你有你的 初始图每条边的初始流量。

这个问题实际上比在提供可行流量时最大化流量要困难一些。