KM 算法是一个解决最大最小权匹配的经典算法能解决的问题比如分配几个不同的工人完成不同的工作, 求解怎样使得工厂的经济效益最高, 建图就是每个工人完成每个工作对应的经济效益还有一些建图比较复杂的问题, 比如 poj3686: 有 n 个订单 m 个车间, 每个车间均可以单独完成任何一个订单; 每个车间完成不同订单的时间是不同的; 不会出现两个车间完成同一个订单的情况; 给出每个订单在某个车间完成所用的时间; 求解订单完成的最小平均时间是多少分析这个问题可以知道, 求订单完成的最小平均时间, 也就是求出订单完成的总的最小时间, 是一个最小权值问题; 另外, 由于每个车间可以完成多个订单, 那么假设在这个车间完成了 k 个订单, 则总的时间为
t1 + (t1 +t2) + (t1 + t2 + t3) +...+ (t1 + t2 +...+ tk)
, 也就是需要计算等待时间 -- 第 k 个完成的订单的时间等于它自己的加工时间加上它等待前面的 k-1 个订单加工完成需要的时间了解了这一点之后, 可以把每个车间拆分成 n 个点来建图, 从 1 到 n 分别代表这个车间在倒数第几个位置加工了相应的订单对于这一点, 可能有的同学开始的时候有些不理解: 要是每个车间得到的最后加工位置是不连续的怎么办? 比如某个车间最后得出在倒数第 135 个加工一个订单, 对于这个疑惑其实是不成立的, 因为如果本车间倒数第 2 个没有对应的订单, 那么把 3 移到 2 处所获得的权值必然要更小, 所以 KM 算法根本不会得出这样的答案好了, 下面给出一个求解最大权值问题的 Java 代码:
- public class KM {
- int[][] graph; // 假设 graph 的行是顶点 X 集合 (其中的顶点简称 X 顶点), 列是顶点 Y 集合 (其中的顶点简称 Y 顶点)
- boolean[] xUsed; // 在每次循环中每个 X 顶点是否访问过
- boolean[] yUsed; // 在每次循环中每个 Y 顶点是否访问过
- int[] match; // 每个 Y 顶点匹配的 X 顶点, 即第 i 个 Y 顶点匹配的是第 match[i] 个 X 顶点
- int len; // 图的大小为 len*len
- int[] less; // 与顶标变化相关
- private static final int INFINITE = 0x6fffffff;
- int[] X; // 每个 X 顶点的顶标
- int[] Y; // 每个 Y 顶点的顶标, 初始化为 0
- public KM(int[][] data) {
- this.graph = data;
- len = data.length;
- xUsed = new boolean[len];
- yUsed = new boolean[len];
- match = new int[len];
- less = new int[len];
- X = new int[len];
- Y = new int[len];
- for (int i = 0; i < len; i++) {
- match[i] = -1;
- }
- // 初始化每个 X 顶点的顶标为与之相连的边中最大的权
- for (int k = 0; k < len; k++) {
- X[k] = data[k][0];
- for (int l = 0; l < len; l++) {
- X[k] = X[k] >= data[k][l] ? X[k] : data[k][l];
- }
- }
- }
- void km() {
- // 遍历每个 X 顶点
- for (int i = 0; i < len; i++) {
- for (int j = 0; j < len; j++) {
- less[j] = INFINITE;
- }
- while (true) { // 寻找能与 X 顶点匹配的 Y 顶点, 如果找不到就降低 X 顶点的顶标继续寻找
- for (int j = 0; j < len; j++) {
- xUsed[j] = false;
- yUsed[j] = false;
- }
- if (hungaryDFS(i)) break; // 寻找到匹配的 Y 顶点, 退出
- // 如果没有找到能够匹配的 Y 顶点, 则降低 X 顶点的顶标, 提升 Y 顶点的顶标, 再次循环
- int diff = INFINITE; //diff 是顶标变化的数值
- for (int j = 0; j < len; j++) {
- if (!yUsed[j]) diff = diff <= less[j] ? diff : less[j];
- }
- //diff 等于为了使该顶点 X 能够匹配到一个 Y 顶点, 其 X 的顶标所需要降低的最小值
- // 更新顶标
- for (int j = 0; j < len; j++) {
- if (xUsed[j]) X[j] -= diff;
- if (yUsed[j]) Y[j] += diff;
- else less[j] -= diff;
- }
- }
- }
- // 匹配完成, 可以输出结果
- int res = 0;
- for (int i = 0; i < len; i++) {
- res += graph[match[i]][i];
- }
- System.out.println("最终最大权值:" + res);
- }
- private boolean hungaryDFS(int i) {
- // 设置这个 X 顶点在此轮循环中被访问过
- xUsed[i] = true;
- // 对于这个 X 顶点, 遍历每个 Y 顶点
- for (int j = 0; j < len; j++) {
- if (yUsed[j]) continue; // 每轮循环中每个 Y 顶点只访问一次
- int gap = X[i] + Y[j] - graph[i][j]; //KM 算法的顶标变化公式
- // 只有 X 顶点的顶标加上 Y 顶点的顶标等于 graph 中它们之间的边的权时才能匹配成功
- if (gap == 0) {
- yUsed[j] = true;
- if (match[j] == -1 || hungaryDFS(match[j])) {
- match[j] = i;
- return true;
- }
- } else {
- less[j] = less[j] <= gap ? less[j] : gap;
- }
- }
- return false;
- }
- public static void main(String[] args) {
- int[][] graph = {
- {3, 5, 5, 4, 1},
- {2, 2, 0, 2, 2},
- {2, 4, 4, 1, 0},
- {0, 1, 1, 0, 0},
- {1, 2, 1, 3, 3}
- };
- new KM(graph).km();
- }
- }
来源: http://blog.csdn.net/Q_AN1314/article/details/79493006