حل مسئله تخصیص با استفاده از جریان کمینه-هزینه¶
مسئلهٔ تخصیص (assignment problem) دو بیان معادل دارد:
- به شما یک ماتریس مربعی $A[1..N, 1..N]$ داده می‌شود، باید $N$ عنصر را در آن طوری انتخاب کنید که در هر سطر و ستون دقیقاً یک عنصر انتخاب شود و مجموع مقادیر این عناصر کمترین مقدار ممکن باشد.
- $N$ سفارش و $N$ ماشین وجود دارد. هزینهٔ تولید هر سفارش بر روی هر ماشین مشخص است. هر ماشین تنها می‌تواند یک سفارش را انجام دهد. باید تمام سفارش‌ها را به ماشین‌ها طوری تخصیص داد که هزینه کل به حداقل برسد.
در اینجا، راه‌حل این مسئله را بر اساس الگوریتم یافتن جریان کمینه-هزینه (min-cost-flow) بررسی می‌کنیم که مسئله تخصیص را در زمان $\mathcal{O}(N^3)$ حل می‌کند.
توضیحات¶
یک شبکه دوبخشی می‌سازیم: یک رأس منبع $S$ و یک رأس چاهک $T$ وجود دارد. در بخش اول $N$ رأس (متناظر با سطرهای ماتریس یا سفارش‌ها) و در بخش دوم نیز $N$ رأس (متناظر با ستون‌های ماتریس یا ماشین‌ها) قرار دارد. بین هر رأس $i$ از مجموعه اول و هر رأس $j$ از مجموعه دوم، یک یال با ظرفیت ۱ و هزینه $A_{ij}$ رسم می‌کنیم. از منبع $S$ به تمام رأس‌های $i$ از مجموعه اول، یال‌هایی با ظرفیت ۱ و هزینه ۰ رسم می‌کنیم. از هر رأس $j$ از مجموعه دوم به چاهک $T$، یک یال با ظرفیت ۱ و هزینه ۰ رسم می‌کنیم.
در شبکهٔ حاصل، بیشینه جریان با کمینه هزینه را پیدا می‌کنیم. بدیهی است که مقدار جریان برابر $N$ خواهد بود. سپس، برای هر رأس $i$ از بخش اول، دقیقاً یک رأس $j$ از بخش دوم وجود خواهد داشت که جریان $F_{ij} = 1$ باشد. در نهایت، این یک تناظر یک‌به‌یک بین رأس‌های بخش اول و رأس‌های بخش دوم است که راه‌حل مسئله محسوب می‌شود (چون جریان پیدا شده دارای کمترین هزینه است، پس مجموع هزینه‌های یال‌های انتخاب‌شده نیز کمترین مقدار ممکن خواهد بود که معیار بهینگی است).
پیچیدگی این راه‌حل برای مسئله تخصیص به الگوریتمی بستگی دارد که برای جستجوی بیشینه جریان با کمینه هزینه استفاده می‌شود. با استفاده از Dijkstra، پیچیدگی $\mathcal{O}(N^3)$ و با استفاده از Bellman-Ford، پیچیدگی $\mathcal{O}(N^4)$ خواهد بود. این به این دلیل است که اندازه جریان از مرتبه $O(N)$ است و هر تکرار الگوریتم Dijkstra می‌تواند در زمان $O(N^2)$ انجام شود، در حالی که این زمان برای Bellman-Ford برابر $O(N^3)$ است.
پیاده‌سازی¶
پیاده‌سازی ارائه‌شده در اینجا طولانی است و احتمالاً می‌توان آن را به طور قابل توجهی کوتاه‌تر کرد. این پیاده‌سازی از الگوریتم SPFA برای یافتن کوتاه‌ترین مسیرها استفاده می‌کند.
const int INF = 1000 * 1000 * 1000;
vector<int> assignment(vector<vector<int>> a) {
int n = a.size();
int m = n * 2 + 2;
vector<vector<int>> f(m, vector<int>(m));
int s = m - 2, t = m - 1;
int cost = 0;
while (true) {
vector<int> dist(m, INF);
vector<int> p(m);
vector<bool> inq(m, false);
queue<int> q;
dist[s] = 0;
p[s] = -1;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
inq[v] = false;
if (v == s) {
for (int i = 0; i < n; ++i) {
if (f[s][i] == 0) {
dist[i] = 0;
p[i] = s;
inq[i] = true;
q.push(i);
}
}
} else {
if (v < n) {
for (int j = n; j < n + n; ++j) {
if (f[v][j] < 1 && dist[j] > dist[v] + a[v][j - n]) {
dist[j] = dist[v] + a[v][j - n];
p[j] = v;
if (!inq[j]) {
q.push(j);
inq[j] = true;
}
}
}
} else {
for (int j = 0; j < n; ++j) {
if (f[v][j] < 0 && dist[j] > dist[v] - a[j][v - n]) {
dist[j] = dist[v] - a[j][v - n];
p[j] = v;
if (!inq[j]) {
q.push(j);
inq[j] = true;
}
}
}
}
}
}
int curcost = INF;
for (int i = n; i < n + n; ++i) {
if (f[i][t] == 0 && dist[i] < curcost) {
curcost = dist[i];
p[t] = i;
}
}
if (curcost == INF)
break;
cost += curcost;
for (int cur = t; cur != -1; cur = p[cur]) {
int prev = p[cur];
if (prev != -1)
f[cur][prev] = -(f[prev][cur] = 1);
}
}
vector<int> answer(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (f[i][j + n] == 1)
answer[i] = j;
}
}
return answer;
}