hozzárendelési feladat (matematika, operációkutatás) A hozzárendelési feladat (assignment problem) egy optimalizálási probléma, ahol adott két halmaz (pl. dolgozók és feladatok), és cél az elemek egymáshoz rendelése oly módon, hogy a hozzárendelés költsége minimális legyen. A probléma gyakran gráf-alapú formában jelenik meg, ahol a csúcsok két halmaza között súlyozott élek vannak.
Adott egy ( n n ) méretű költségmátrix ( C ), ahol ( C ) az ( i )-edik dolgozóhoz rendelt ( j )-edik feladat elvégzésének költségét jelenti. Cél az ( n )-elemű hozzárendelés kiválasztása úgy, hogy az összköltség minimális legyen.
A hozzárendelési probléma megoldható a magyar módszerrel (Hungarian Algorithm), amely hatékonyan képes kezelni a négyzetes költségmátrixokat.
Tegyük fel, hogy a következő mátrixot kaptuk:
| Feladat 1 | Feladat 2 | Feladat 3 | |
|---|---|---|---|
| Dolgozó 1 | 9 | 2 | 7 |
| Dolgozó 2 | 6 | 4 | 3 |
| Dolgozó 3 | 5 | 8 | 1 |
A cél a dolgozók és feladatok hozzárendelése a költségek minimalizálása érdekében.
A magyar módszer a következő lépésekben működik: 1. Sor- és oszlop-redukció: - Vonjuk ki minden sorból a legkisebb elemet. - Vonjuk ki minden oszlopból a legkisebb elemet. 2. Nullák lefedése vonalakkal: - Jelöljük ki a nullákat a mátrixban úgy, hogy a lehető legkevesebb vízszintes és függőleges vonallal lefedjük őket. 3. Optimalitás ellenőrzése: - Ha a vonalak száma megegyezik a mátrix méretével, akkor optimális hozzárendelést találunk. - Ha nem, akkor újraállítjuk a mátrixot (lépéseket ismételve), amíg optimális megoldást nem kapunk.
A SciPy könyvtár beépített függvényeket biztosít a hozzárendelési feladat megoldására.
from scipy.optimize import linear_sum_assignment
import numpy as np
# Költségmátrix
cost_matrix = np.array([
,
,
])
# Magyar algoritmus alkalmazása
row_ind, col_ind = linear_sum_assignment(cost_matrix)
# Eredmények
print("Hozzárendelések (sor, oszlop):", list(zip(row_ind, col_ind)))
print("Minimális költség:", cost_matrix.sum())
Hozzárendelések (sor, oszlop): Minimális költség: 9
A C++-ban használható az Kuhn–Munkres algoritmus vagy egy saját implementáció a hozzárendelési feladat megoldására.
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;
const int INF = numeric_limits<int>::max();
vector<int> hungarian_algorithm(const vector<vector<int>>& cost) {
int n = cost.size();
vector<int> u(n, 0), v(n, 0), p(n, 0), way(n, 0);
for (int i = 1; i < n; ++i) {
vector<int> minv(n, INF);
vector<bool> used(n, false);
int j0 = 0;
p = i;
do {
used = true;
int i0 = p, delta = INF, j1;
for (int j = 1; j < n; ++j) {
if (!used) {
int cur = cost - u - v;
if (cur < minv) {
minv = cur;
way = j0;
}
if (minv < delta) {
delta = minv;
j1 = j;
}
}
}
for (int j = 0; j < n; ++j) {
if (used) {
u] += delta;
v -= delta;
} else {
minv -= delta;
}
}
j0 = j1;
} while (p != 0);
do {
int j1 = way;
p = p;
j0 = j1;
} while (j0 != 0);
}
vector<int> result(n - 1);
for (int j = 1; j < n; ++j) {
result - 1] = j - 1;
}
return result;
}
int main() {
vector<vector<int>> cost = {
{9, 2, 7},
{6, 4, 3},
{5, 8, 1}
};
vector<int> assignment = hungarian_algorithm(cost);
cout << "Hozzárendelések:" << endl;
for (int i = 0; i < assignment.size(); ++i) {
cout << "Dolgozó " << i + 1 << " -> Feladat " << assignment + 1 << endl;
}
return 0;
}
Hozzárendelések: Dolgozó 1 -> Feladat 2 Dolgozó 2 -> Feladat 3 Dolgozó 3 -> Feladat 1
linear_sum_assignment függvénye gyors és egyszerű megoldást kínál.