A Kuhn-Munkres-algoritmus, más néven a magyar módszer, egy optimalizációs algoritmus, amelyet két halmaz elemei közötti párosítás problémájának megoldására használnak. Az algoritmus különösen hasznos bipartit gráfok esetén, ahol a cél a minimális vagy maximális súlyú párosítás megtalálása.
Az algoritmus a párosítási probléma optimalizálására lineáris programozási technikákat alkalmaz. A cél: 1. Kiválasztani (n) élből álló párosítást úgy, hogy minden sorhoz és oszlophoz pontosan egy él tartozzon. 2. Minimalizálni a kiválasztott élek költségének összegét.
KuhnMunkres(C):
1. Sorcsökkentés:
Minden sorból vond ki a legkisebb elemet.
2. Oszlopcsökkentés:
Minden oszlopból vond ki a legkisebb elemet.
3. Lefedő vonalak:
Használj a lehető legkevesebb vonalat az összes nulla lefedésére.
4. Ha a lefedő vonalak száma n:
- Térj vissza az aktuális párosítással.
Különben:
- Keress egy nem lefedett minimumot.
- Vond ki ezt az értéket a nem lefedett elemekből.
- Add hozzá a kétszeresen lefedett elemekhez.
- Ismételd a lefedő vonalakat.
5. Állítsd elő a párosítást a nullák pozíciója alapján.
import numpy as np
def hungarian_algorithm(cost_matrix):
n = cost_matrix.shape
# 1. Sorok csökkentése
for i in range(n):
cost_matrix -= np.min(cost_matrix)
# 2. Oszlopok csökkentése
for j in range(n):
cost_matrix -= np.min(cost_matrix)
# Lefedett sorok/oszlopok
cover_rows = np.zeros(n, dtype=bool)
cover_cols = np.zeros(n, dtype=bool)
# Nullák lefedése
def cover_zeros(matrix):
marked_zeros = np.zeros_like(matrix, dtype=bool)
for i in range(n):
for j in range(n):
if matrix == 0 and not cover_rows and not cover_cols:
marked_zeros = True
cover_rows = True
cover_cols = True
break
return marked_zeros
marked_zeros = cover_zeros(cost_matrix)
# Lefedő vonalak ellenőrzése
def count_lines():
return np.sum(cover_rows) + np.sum(cover_cols)
while count_lines() < n:
min_val = np.min(cost_matrix)
cost_matrix -= min_val
cost_matrix += min_val
marked_zeros = cover_zeros(cost_matrix)
# Párosítás meghatározása
result =
for i in range(n):
for j in range(n):
if marked_zeros:
result.append((i, j))
return result
# Példa mátrix
cost_matrix = np.array([
,
,
])
assignment = hungarian_algorithm(cost_matrix)
print("Optimális párosítás:", assignment)
Kimenet:
Optimális párosítás:
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
void subtract_min(vector<vector<int>>& cost) {
int n = cost.size();
// Sorok csökkentése
for (int i = 0; i < n; ++i) {
int row_min = *min_element(cost.begin(), cost.end());
for (int j = 0; j < n; ++j) {
cost -= row_min;
}
}
// Oszlopok csökkentése
for (int j = 0; j < n; ++j) {
int col_min = INT_MAX;
for (int i = 0; i < n; ++i) {
col_min = min(col_min, cost);
}
for (int i = 0; i < n; ++i) {
cost -= col_min;
}
}
}
void print_assignment(const vector<pair<int, int>>& assignment) {
for (const auto& p : assignment) {
cout << "(" << p.first << ", " << p.second << ")" << endl;
}
}
int main() {
vector<vector<int>> cost = {
{4, 1, 3},
{2, 0, 5},
{3, 2, 2}
};
subtract_min(cost);
// Ezen a ponton a teljes Kuhn-Munkres megoldás kiterjeszthető
cout << "Csökkentett költségmátrix:" << endl;
for (const auto& row : cost) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
return 0;
}