Hungarian algorithm

Angol

Főnév

Hungarian algorithm (tsz. Hungarian algorithms)

1. (informatika) magyar módszer

---

A Hungarian algoritmus, más néven Kuhn–Munkres algoritmus, egy hatékony módszer a hozzárendelési probléma (assignment problem) megoldására. A feladat lényege, hogy adott egy n×n-es költségmátrix, amelyben minden sor egy munkást, minden oszlop pedig egy feladatot jelent. A cél az, hogy minden munkához rendeljünk egy feladatot úgy, hogy a teljes költség (vagy idő, távolság stb.) minimális legyen.

Ez a módszer magyar matematikusról, Egerváry Jenőről kapta a nevét, mivel az algoritmus alapját az általa leírt Egerváry-tétel adta meg. Maga az algoritmust Harold Kuhn publikálta 1955-ben, később munkáját James Munkres továbbfejlesztette.

---

2. A hozzárendelési probléma megfogalmazása

Adott:

• Egy n × n méretű költségmátrix ${\textstyle C=[c_{ij}]}$, ahol ${\textstyle c_{ij}}$ az i-edik munkás j-edik feladathoz történő hozzárendelésének költsége.

Cél:

• Válasszunk ki pontosan n darab hozzárendelést (minden sorból és oszlopból egyet), úgy hogy az összköltség minimális legyen.

---

3. Gyakorlati példák

• Gépkezelők hozzárendelése különböző gépekhez
• Szállítmányozási útvonalak minimalizálása
• Munkaerő optimalizálása
• Kép-összepárosítás számítógépes látásban
• Ajánlórendszerek (pl. film és néző párosítás)

---

4. Miért nehéz ez a probléma?

A hozzárendelési probléma kombinatorikus természetű. Minden munkás-feladat párosítás ${\textstyle n!}$ lehetőséget jelent. Ez exponenciálisan nő a ${\textstyle n}$ értékével. Azonban a Hungarian algoritmus polinomiális időben fut, pontosan O(n³) komplexitású, így hatékonyan megoldja a problémát.

---

5. A Hungarian algoritmus lépései (Minimum költség esetén)

1. Sor- és oszlopcsökkentés (normalizálás)
   • Minden sorból vonjuk ki a sor legkisebb elemét.
   • Minden oszlopból vonjuk ki az oszlop legkisebb elemét.
   • Ezzel garantáljuk, hogy a mátrixban minden sorban és oszlopban legyen legalább egy nulla.
2. Nullák lefedése a minimális számú vonallal
   • Húzzunk át sorokat és oszlopokat úgy, hogy az összes nullát lefedjük, és használjunk minimális számú vonalat.
3. Optimalitásvizsgálat
   • Ha az összes nulla lefedhető n darab vonallal, akkor megtaláltuk az optimális hozzárendelést.
   • Ha kevesebb vonal szükséges, mint ${\textstyle n}$, akkor módosítjuk a mátrixot.
4. Mátrix módosítása
   • Keressük meg a legkisebb nem lefedett elemet.
   • Ezt az értéket vonjuk ki minden nem lefedett sorból, és adjuk hozzá minden kétszeresen lefedett elemhez.
   • Ez új nullákat hoz létre, lehetővé téve az új hozzárendelést.
5. Ismételjük a 2–4. lépéseket, amíg meg nem kapjuk az optimális párosítást.

---

6. Vizuális példa

Költségmátrix:

	F1	F2	F3
M1	9	2	7
M2	6	4	3
M3	5	8	1

Lépés 1 – sorcsökkentés:

• Soronként legkisebb: M1:2, M2:3, M3:1
• Új mátrix:

	F1	F2	F3
M1	7	0	5
M2	3	1	0
M3	4	7	0

Lépés 2 – oszlopcsökkentés:

• Oszloponként legkisebb: F1:3, F2:0, F3:0
• Új mátrix:

	F1	F2	F3
M1	4	0	5
M2	0	1	0
M3	1	7	0

Innen már megkereshető az optimális párosítás: például M1→F2, M2→F1, M3→F3.

---

7. Maximális értékű hozzárendelés

Ha a cél maximális érték elérése (pl. maximális profit), akkor előbb át kell alakítani a mátrixot:

$${\text{új }}c_{ij}={\text{max érték a mátrixban}}-c_{ij}$$

Így az optimalizálás ismét minimumra irányul, és a Hungarian algoritmus használható.

---

8. Bővítések és variációk

• Nem négyzetes mátrix: ha több munkás van, mint feladat, vagy fordítva, dummy sorokat vagy oszlopokat adunk hozzá nulla költséggel.
• Költség-korlátozott hozzárendelés: ha bizonyos hozzárendelések tiltottak, azokat végtelen (nagy) költséggel jelöljük.
• Dinamikus hozzárendelés: változó input esetén valós időben kell futtatni az algoritmust.

---

9. Előnyök és alkalmazások

✅ Előnyök

• Pontos (nem heurisztika!)
• Gyors (O(n³))
• Stabil és determinisztikus eredményt ad
• Alkalmazható széles körben

📌 Alkalmazások

• Gép–munkás hozzárendelés
• Feladatkiosztás AI rendszerekben
• Arcfelismerés, objektumkövetés (kép–cél megfeleltetés)
• Gazdasági modellek és párosításelmélet
• Logisztikai problémák, útvonaltervezés

---

10. Összefoglalás

A Hungarian algoritmus egy elegáns, hatékony és optimális megoldást nyújtó eljárás a hozzárendelési problémákra:

• Kombinatorikus természetű problémákra is jól alkalmazható
• Minimalizál vagy maximalizál adott költség-/értékfüggvény szerint
• Széles körű gyakorlati alkalmazása van a gépi tanulástól a gyártásoptimalizálásig

További információk

• Hungarian algorithm - Szótár.net (en-hu)
• Hungarian algorithm - Sztaki (en-hu)
• Hungarian algorithm - Merriam–Webster
• Hungarian algorithm - Cambridge
• Hungarian algorithm - WordNet
• Hungarian algorithm - Яндекс (en-ru)
• Hungarian algorithm - Google (en-hu)
• Hungarian algorithm - Wikidata
• Hungarian algorithm - Wikipédia (angol)