任務分配問題

任務分配問題是在加權二分圖中尋找最大（或最小）加權匹配的問題，也稱二分圖最佳帶權匹配問題或二分圖最優匹配。^[1]此類問題通常使用匈牙利算法（KM算法）或轉換為一個網絡費用流問題進行求解。

詳述

分為以下幾類：

• 線性任務分配問題：${\displaystyle P}$是二元組${\displaystyle (a,b)}$的集合，其中${\displaystyle a}$和${\displaystyle b}$分別是集合${\displaystyle A}$和${\displaystyle B}$中的元素。${\displaystyle C}$是某一函數，並滿足特定約束條件，例如：${\displaystyle A}$的每一個元素必須在${\displaystyle P}$中出現一次，或者${\displaystyle B}$的每一個元素必須在${\displaystyle P}$中出現一次，或者以上二者都必須滿足。線性任務分配問題的目標就是最大化或者最小化${\displaystyle C(a,b)}$之和。
  
  該問題是線性的，因為代價函數${\displaystyle C()}$只取決於特定的二元組${\displaystyle (a,b)}$，而與其它的二元組沒有任何關係。

• 二次任務分配問題：給定${\displaystyle n}$家工廠和${\displaystyle n}$個庫房。每個庫房被分配給一家工廠。很顯然有${\displaystyle n!}$種不同的分配組合。每家工廠和它的庫房間的代價函數被定義為二者間的距離和物流量的乘積。如何分配以使所有的代價總和最小？

這些問題都是組合優化的研究對象，可以轉化為帶權二分圖上的最優匹配問題。

帶權二分圖

一個帶權二分圖 ${\displaystyle G=(X,Y,E)}$ 中的邊 ${\displaystyle (u,v)\in E}$ 都帶有一個權值 ${\displaystyle f(u,v)}$。該二分圖的一個最佳帶權匹配是它所有匹配中，所有匹配邊權值之和中最大的一個。

舉例

有一些員工要完成一些任務。各個員工完成不同任務所花費的時間都不同。每個員工只分配一項任務。每項任務只被分配給一個員工。怎樣分配員工與任務以使所花費的時間最少？

婚配問題：有一些男人和一些女人，各位男人如果和某位女人結婚則其婚姻穩定程度具有不同的穩定數值。如何匹配可以使得所有配對的穩定值總和最大？也稱婚姻匹配問題。

算法

匈牙利算法是眾多用於解決線性任務分配問題的算法之一，它可以在多項式時間內解決問題。 分配問題是運輸問題的特例，運輸問題是最少成本流量問題的特例，而它們都是線性規劃的特例。因此，單純形法可以作為解決這些問題的通法。然而，針對每種特殊情形設計的專門算法可以提高解決問題的效率。如果問題的成本函數包含二次不等式，則稱之為二次分配問題。

任務分配問題一般可以在多項式時間內轉化成最大流問題（Maximum Flow Problem）。通過建立模型，使用費用流算法解決。

參考實現

以下是使用C++實現的匈牙利算法（KM算法）：

#include <cstdio>
#include <string.h>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int const MAX = 1000;
int const inf = INT_MAX;

int w[MAX][MAX];
int link[MAX];//代表当前与Y集合中配对的X集合中的点
int visx[MAX], visy[MAX];
int lx[MAX], ly[MAX];
int n, m;//代表X和Y中元素的个数
 
int can(int t)
{
    visx[t] = 1;
    for(int i = 1; i <= m; i++){
        if(!visy[i] && lx[t] + ly[i] == w[t][i]){//这里“lx[t]+ly[i]==w[t][i]”决定了这是在相等子图中找增广路的前提，非常重要
            visy[i] = 1;
            if(link[i] == -1 || can(link[i])){
                link[i] = t;
                return 1;
            }
        }
    }
    return 0;
}

int km(void)
{
    int sum = 0; memset(ly, 0, sizeof(ly));
    for(int i = 1; i <= n; i++){//把各个lx的值都设为当前w[i][j]的最大值
        lx[i] = -inf;
        for(int j = 1; j <= n; j++){
            if(lx[i] < w[i][j])
                lx[i] = w[i][j];
        }
    }

    memset(link, -1, sizeof(link));
    for(int i = 1; i <= n; i++){
        while(1){
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            if(can(i))//如果它能够形成一条增广路径，那么就break
                break;
            int d = inf;//否则，后面应该加入新的边,这里应该先计算d值
            for(int j = 1; j <= n; j++)//对于搜索过的路径上的XY点，设该路径上的X顶点集为S，Y顶点集为T，对所有在S中的点xi及不在T中的点yj
                if(visx[j])
                    for(int k = 1; k <= m; k++)
                       if(!visy[k])
                            d = min(d, lx[j] + ly[k] - w[j][k]);
            if(d == inf)
            return -1;//找不到可以加入的边，返回失败（即找不到完美匹配）
            for (int j = 1; j <= n; j++)
                if (visx[j])
                    lx[j] -= d;
            for(int j = 1; j <= m; j++)
                if(visy[j])
                    ly[j] += d;
            }
    }
    for(int i = 1; i <= m; i++)
        if(link[i] > -1)
            sum += w[link[i]][i];
    return sum;
}

參考文獻

1. 李煜東. 算法竞赛进阶指南. 中原出版傳媒集團 - 河南電子影像出版社. ISBN 978-7-89388-198-5.

參看

• 匈牙利算法
• 護士排班問題