如何按成本排序最小费用流基本解并获取前n个最优基本解

如何对最小费用流问题的基本解按成本高低排序 #

最小费用流的基本解一一对应可行域凸多面体的顶点，也对应网络单纯形算法中的可行生成树结构，按成本排序的通用实现逻辑如下：

• 第一步先通过任意最小费用流算法（网络单纯形法效率最高，因为直接维护基结构）求出全局最优基本解，此时残量网络中不存在负费用增广圈。
• 核心是用**总费用为排序键的最小堆（优先队列）**维护待遍历的候选解，同时配一个哈希集合做去重，避免同一个基生成树对应的解被重复处理：
  1. 初始状态把全局最优解压入堆，标记为已访问。
  2. 循环弹出堆顶元素，这就是当前未访问解里成本最低的解，按弹出顺序排列就得到成本从低到高的序列。
  3. 对刚弹出的解，枚举残量网络中所有合法的进基边，做一次标准的网络单纯形基交换操作，得到所有相邻的可行基本解，计算新解的总费用，若该解未被访问过就压入堆、标记已访问。
• 注意：最小费用流的基本解总数随网络节点、边的规模呈指数增长，全量排序仅适用于节点边数都极小的网络，不要在大规模网络上尝试全量排序。

求解n个最优基本解的可用方法与工具 #

数学方法层面 #

• 求前n优基本解的通用框架就是上面提到的基交换枚举法：本质是在基本解构成的顶点图上做类Dijkstra遍历，顶点之间的边对应一次基交换，边权是基变换带来的总费用增量，从全局最优点出发按顺序遍历到的前n个顶点，就是成本从低到高的前n个最优基本解。
• 如果不要求解必须是基本解（即不要求是凸多面体顶点，允许非顶点的可行流），可以用迭代切割法：每次求出当前最优解后，添加线性约束把当前解从可行域中排除，再重新求解最优，重复n次即可。但这个方法无法保证返回的是基本解，切割约束添加不当还可能引入数值误差，甚至漏掉成本更低的基本解，仅适合对解的结构无严格要求的场景。

实现与工具层面 #

• 没有现成的工具包可以直接传入参数n就返回前n优基本解，但是可以基于成熟的最小费用流求解器二次开发，优先选暴露了网络单纯形基结构操作接口的求解器，比如LEMON、OR-Tools的流计算模块，基于这类求解器实现基交换枚举的额外开发量很小，运行效率也高。
• 复杂度提示：当n的量级在几十到几百时，哪怕是节点数千、边数万的中等规模网络，基交换枚举的速度都能满足实用要求；如果n达到上万量级，枚举开销会快速上升——本质上前k优基本解枚举不存在通用多项式时间算法，n大时问题本身就是NP难的，没有通用高效解法。

工程实操提示：如果你的场景不需要严格的数学意义上的基本解，只是需要若干个成本低、结构有差异的流方案，可以在每次求出最优解后，给当前解中用到的关键边加一个极小的费用惩罚，再重新求解，这种方法实现成本极低，拿到的方案也能满足大多数业务场景的差异化要求。

内容的提问来源于stack exchange，提问作者Giacomo