Hungarian算法

一、基本概念

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];
        }
    }
}

2、從未匹配的結點出發，尋找增廣路徑。增廣路徑是指一系列相鄰的邊，這些邊交替地連接未匹配的結點和已匹配的結點，通過這些邊可以將一個未匹配的結點與一個未匹配的結點相連接。如果找到了增廣路徑，則將該路徑上的所有邊都加入匹配集合中；否則執行第三步。

3、找出未匹配結點中的最小頂標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算法主要應用於圖像處理、資源分配和調度等領域。其中，在圖像匹配方面，匈牙利算法可用於特徵點的匹配和多目標跟蹤；在資源分配和調度方面，匈牙利算法可用於任務調度、車輛調度和人員分配等問題。