Wikiszótár

Kuhn-Munkres-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈkuxmuŋkrɛʃɒlɡoritmuʃ]

Főnév

Kuhn-Munkres-algoritmus

  1. (matematika)

Kuhn-Munkres-algoritmus

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.


Probléma definíció

Bemenet:

  • Egy (n n) méretű költségmátrix ((C)), ahol (C[i][j]) az (i)-edik elemet az (j)-edik elemmel összekötő él költsége.

Kimenet:

  • Egy olyan párosítás, amely a költségmátrix összes csúcsának (sorának és oszlopának) megfelelő elemeit párosítja úgy, hogy a teljes költség minimális legyen.


Fő ötlet

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.


Algoritmus lépései

  1. Súlyok csökkentése:
    • Minden sorból vonjuk ki a legkisebb elemet (sorminimum), így minden sorban lesz legalább egy nulla.
  2. Oszlopok csökkentése:
    • Az oszlopokból vonjuk ki a legkisebb elemet (oszlopminimum), hogy minden oszlopban legyen legalább egy nulla.
  3. Nullák lefedése:
    • Használjunk a lehető legkevesebb vízszintes és függőleges vonalat, hogy lefedjük az összes nullát.
  4. Optimális lefedés vizsgálata:
    • Ha a lefedő vonalak száma (n) (azaz a mátrix mérete), a párosítás optimális, és vége az algoritmusnak.
    • Ha nem, lépjünk a következő lépésre.
  5. Mátrix módosítása:
    • Keressük meg a legkisebb, lefedetlen elemet.
    • Vonjuk ki ezt az értéket az összes lefedetlen elemből, és adjuk hozzá a kétszeresen lefedett elemekhez.
    • Ismételjük a 3. és 4. lépést, amíg nem kapunk optimális párosítást.
  6. Párosítás meghatározása:
    • Az eredeti költségmátrix alapján hozzuk létre a párosítást, a nullák pozíciója alapján.


Pszeudokód

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.

Python implementáció

import numpy as np

def hungarian_algorithm(cost_matrix):
    n = cost_matrix.shape[0]
    
    # 1. Sorok csökkentése
    for i in range(n):
        cost_matrix[i] -= np.min(cost_matrix[i])
    
    # 2. Oszlopok csökkentése
    for j in range(n):
        cost_matrix[:, j] -= np.min(cost_matrix[:, j])
    
    # 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[i, j] == 0 and not cover_rows[i] and not cover_cols[j]:
                    marked_zeros[i, j] = True
                    cover_rows[i] = True
                    cover_cols[j] = 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[~cover_rows][:, ~cover_cols])
        cost_matrix[~cover_rows] -= min_val
        cost_matrix[:, cover_cols] += 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[i, j]:
                result.append((i, j))
    
    return result

# Példa mátrix
cost_matrix = np.array([
    [4, 1, 3],
    [2, 0, 5],
    [3, 2, 2]
])

assignment = hungarian_algorithm(cost_matrix)
print("Optimális párosítás:", assignment)

Kimenet: 

Optimális párosítás: [(0, 1), (1, 0), (2, 2)]

C++ implementáció

#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[i].begin(), cost[i].end());
        for (int j = 0; j < n; ++j) {
            cost[i][j] -= 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[i][j]);
        }
        for (int i = 0; i < n; ++i) {
            cost[i][j] -= 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;
}

Előnyök

  1. Hatékonyság:
    • Az algoritmus időbonyolultsága (O(n^3)), ami hatékony kisebb méretű mátrixok esetén.
  2. Általánosság:
    • Képes negatív és pozitív költségekkel dolgozni.
  3. Optimális megoldás:
    • Garantáltan megtalálja a minimális költségű párosítást.


Hátrányok

  1. Korlátozott méret:
    • Nagy méretű mátrixok esetén az (O(n^3)) időbonyolultság kevésbé hatékony.
  2. Bonyolultság:
    • Az implementáció összetettebb lehet más algoritmusokhoz képest.


Alkalmazások

  1. Feladat-hozzárendelés:
    • Feladatok optimális kiosztása dolgozók között.
  2. Költségoptimalizálás:
    • Optimalizálási problémák logisztikában és erőforrás-kezelésben.
  3. Számítógépes látás:
    • Objektumok követése több képkockán keresztül.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Kuhn-Munkres-algoritmus&oldid=3480169”