Hungarian算法

发布时间：2023-05-21

一、基本概念

Hungarian算法，即匈牙利算法，是一种求解二分图最大权完美匹配问题的有效方法。该算法由E. W. Dijkstra和C. T. Wong在1955年提出，并由H. W. Kuhn在1957年发表。它的时间复杂度为O(n^3)，是解决该问题时间复杂度最小的算法之一。 所谓二分图，就是指一个图中的结点可以被分为两个互不相交的子集S和T，而且所有的边都连接S和T中的结点。最大权完美匹配问题，即给定一个带权二分图，找出一个完美匹配集合，使得该匹配集合中所有边的权值之和最大。

二、算法流程

首先，我们需要将带权二分图表示为一个n * n的矩阵W，其中W(i, j)表示第i个结点和第j个结点之间的边的权值。 然后，我们需要执行以下步骤：

  1. 将W矩阵中每一行中的最小值减去该行中的所有元素，并将每一列中的最小值减去该列中的所有元素。这是为了保证在后续寻找增广路径时能够找到更小的权值。
void reduce(int n, vector<vector<int>>& W, vector<int>& h, vector<int>& v) {
    for (int i = 0; i < n; i++) {
        h[i] = *min_element(W[i].begin(), W[i].end());
        for (int j = 0; j < n; j++) {
            W[i][j] -= h[i];
        }
    }
    for (int j = 0; j < n; j++) {
        v[j] = *min_element(W.begin(), W.end(),
            [&](vector<int> a, vector<int> b) { return a[j] < b[j]; }
        )[j];
        for (int i = 0; i < n; i++) {
            W[i][j] -= v[j];
        }
    }
}
  1. 从未匹配的结点出发，寻找增广路径。增广路径是指一系列相邻的边，这些边交替地连接未匹配的结点和已匹配的结点，通过这些边可以将一个未匹配的结点与一个未匹配的结点相连接。如果找到了增广路径，则将该路径上的所有边都加入匹配集合中；否则执行第三步。
  2. 找出未匹配结点中的最小顶标d，并将每个未匹配结点的顶标值减去d，每个已匹配的结点的顶标值增加d。然后重新执行第2步。
bool findPath(int i, int n, vector<vector<int>>& W, vector<int>& match, vector<int>& vis, vector<int>& slack) {
    for (int j = 0; j < n; j++) {
        if (W[i][j] == 0 && !vis[j]) {
            vis[j] = true;
            if (match[j] == -1 || findPath(match[j], n, W, match, vis, slack)) {
                match[j] = i;
                return true;
            } else {
                slack[j] = min(slack[j], h[i] + v[j] - W[i][j]);
            }
        }
    }
    return false;
}
void KM(int n, vector<vector<int>>& W, vector<int>& match) {
    vector<int> h(n), v(n, 0), slack(n);
    for (int i = 0; i < n; i++) {
        match[i] = -1;
        h[i] = *min_element(W[i].begin(), W[i].end());
        for (int j = 0; j < n; j++) {
            W[i][j] -= h[i];
            v[j] = min(v[j], W[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        while (true) {
            vector<int> vis(n, false);
            slack.assign(n, INT_MAX);
            if (findPath(i, n, W, match, vis, slack)) {
                break;
            }
            int d = *min_element(slack.begin(), slack.end());
            for (int j = 0; j < n; j++) {
                if (vis[j]) {
                    h[match[j]] -= d;
                    v[j] -= d;
                } else {
                    slack[j] -= d;
                }
            }
        }
    }
}

三、性能分析

Hungarian算法的时间复杂度为O(n^3)，其中n是结点数。对于小规模的带权二分图，该算法能够在合理的时间内得到正确的结果。但是对于大规模的带权二分图，该算法的计算时间会变得十分长，因此需要使用更优秀的算法来求解。

四、应用场景

Hungarian算法主要应用于图像处理、资源分配和调度等领域。其中，在图像匹配方面，匈牙利算法可用于特征点的匹配和多目标跟踪；在资源分配和调度方面，匈牙利算法可用于任务调度、车辆调度和人员分配等问题。

推荐文章