任务分配问题

任务分配问题是在加权二分图中寻找最大（或最小）加权匹配的问题，也称二分图最佳带权匹配问题或二分图最优匹配。^[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.

参看

• 匈牙利算法
• 护士排班问题