A Magyar módszer, amelyet Harold Kuhn dolgozott ki és publikált 1955-ben, egy hatékony algoritmus a költségminimalizáló hozzárendelési probléma megoldására. Az algoritmus neve a magyar származású matematikusok, Dénes Kőnig és Jeno Egerváry munkásságára utal, amelyeken az eljárás alapul.
A hozzárendelési probléma célja egy (n n) költségmátrixban a megfelelő hozzárendelés megtalálása úgy, hogy: - Minden munkához egy munkás van rendelve. - A hozzárendelés összköltsége minimális legyen.
Egy (n n) költségmátrix ((C)), ahol (C) a (i)-edik munkás hozzárendelésének a (j)-edik munkához tartozó költsége.
Az optimális hozzárendelés, amely minimalizálja az összköltséget.
Az algoritmus időkomplexitása: (O(n^3)), ahol (n) a mátrix mérete.
HungarianMethod(C):
Sor- és oszlopcsökkentés:
Minden sorból vond ki a legkisebb elemet.
Minden oszlopból vond ki a legkisebb elemet.
Lefedés nullák alapján:
Takarjuk le a nullákat a lehető legkevesebb sorral és oszloppal.
Ha a lefedés száma = mátrix mérete, térj vissza a hozzárendeléssel.
Nullák kezelése:
Jelöljük ki a legkisebb nem lefedett elemet.
Minden lefedett sorhoz adjuk hozzá ezt az elemet, és minden nem lefedett oszlopból vonjuk ki.
Ismételjük az eljárást, amíg optimális hozzárendelést kapunk.
import numpy as np
def hungarian_method(cost_matrix):
n = len(cost_matrix)
cost = np.array(cost_matrix)
# Sorcsökkentés
cost -= cost.min(axis=1, keepdims=True)
# Oszlopcsökkentés
cost -= cost.min(axis=0, keepdims=True)
# Lefedés nullák alapján
while True:
row_covered = np.zeros(n, dtype=bool)
col_covered = np.zeros(n, dtype=bool)
zero_mark = np.zeros_like(cost, dtype=bool)
# Nullák kijelölése
for i in range(n):
for j in range(n):
if cost == 0 and not row_covered and not col_covered:
zero_mark = True
row_covered = True
col_covered = True
break
# Lefedés nullák alapján
row_covered = False
col_covered = np.any(zero_mark, axis=0)
# Ellenőrzés: lefedett sorok és oszlopok száma
if np.sum(row_covered) + np.sum(col_covered) == n:
break
# Nullák kezelése
uncovered_min = np.min(cost)
cost -= uncovered_min
cost += uncovered_min
# Optimális hozzárendelés
assignment =
for i in range(n):
for j in range(n):
if zero_mark:
assignment.append((i, j))
return assignment
# Példa használat
cost_matrix = [
,
,
,
]
assignment = hungarian_method(cost_matrix)
print("Optimális hozzárendelés:", assignment)
Kimenet:
Optimális hozzárendelés:
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;
void reduce_rows(vector<vector<int>>& cost) {
for (auto& row : cost) {
int min_val = *min_element(row.begin(), row.end());
for (auto& cell : row) {
cell -= min_val;
}
}
}
void reduce_columns(vector<vector<int>>& cost) {
int n = cost.size();
for (int j = 0; j < n; ++j) {
int min_val = numeric_limits<int>::max();
for (int i = 0; i < n; ++i) {
min_val = min(min_val, cost);
}
for (int i = 0; i < n; ++i) {
cost -= min_val;
}
}
}
vector<pair<int, int>> hungarian_method(vector<vector<int>>& cost) {
int n = cost.size();
reduce_rows(cost);
reduce_columns(cost);
vector<bool> row_covered(n, false);
vector<bool> col_covered(n, false);
vector<pair<int, int>> assignment;
while (true) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (cost == 0 && !row_covered && !col_covered) {
assignment.emplace_back(i, j);
row_covered = true;
col_covered = true;
break;
}
}
}
if (assignment.size() == n) break;
int uncovered_min = numeric_limits<int>::max();
for (int i = 0; i < n; ++i) {
if (!row_covered) {
for (int j = 0; j < n; ++j) {
if (!col_covered) {
uncovered_min = min(uncovered_min, cost);
}
}
}
}
for (int i = 0; i < n; ++i) {
if (!row_covered) {
for (int j = 0; j < n; ++j) {
cost -= uncovered_min;
}
}
if (col_covered) {
for (int j = 0; j < n; ++j) {
cost += uncovered_min;
}
}
}
}
return assignment;
}
int main() {
vector<vector<int>> cost = {
{9, 11, 14, 11},
{6, 15, 13, 13},
{12, 13, 6, 8},
{11, 9, 10, 12}
};
auto assignment = hungarian_method(cost);
cout << "Optimális hozzárendelés:" << endl;
for (const auto& pair : assignment) {
cout << "(" << pair.first << ", " << pair.second << ")" << endl;
}
return 0;
}
Kimenet:
Optimális hozzárendelés: (0, 1) (1, 0) (2, 2) (3, 3)
A Magyar módszer széles körben használt optimalizálási problémák megoldására, különösen logisztikai és erőforrás-elosztási alkalmazásokban.