Sözlük · approach
Macar Algoritması
Atama problemini (n×n maliyet matrisi, bire-bir minimum-maliyet eşleştirme) polinom-zamanda O(n³) çözen kombinatoryel algoritma; Kuhn (1955) ve Munkres (1957).
Hungarian MethodHungarian AlgorithmKuhn-Munkres Algoritması
Macar Algoritması (Hungarian Method, Kuhn-Munkres Algorithm), atama problemini — n işçi/kaynağın n göreve bire-bir atanması, n×n maliyet matrisinde toplam maliyetin minimum olacak şekilde — polinom-zaman O(n³) içinde çözen kombinatoryel optimizasyon algoritmasıdır. Harold Kuhn 1955 yılında *Naval Research Logistics Quarterly*'de yayımlanan makalesinde algoritmayı tanıttı; adı Macar matematikçiler Dénes König ve Jenő Egerváry'nin 1900'lerin başında geliştirdiği bipartite-matching teoremlerine atfen verildi. James Munkres 1957'de algoritmayı tam-formel polinom-zaman O(n³) prosedüre dönüştürdü; bu yüzden modern literatürde Kuhn-Munkres Algorithm da denir. Çalışma prensibi: matrisin satır/sütun minimumlarını çıkar (satır azaltma + sütun azaltma), sıfırlardan oluşan atama-grafiğinde maksimum eşleştirme bul (König-Egerváry teoremi), tam eşleştirme yoksa sıralı örtme prosedürü ile matris güncelle, tam eşleştirme bulunana kadar tekrarla. Garantili optimum, polinom-zaman, kombinatoryel. Modern hızlı alternatifler: LAP — shortest augmenting path (Jonker ve Volgenant 1987, pratikte 5-20 kat hızlı); auction algorithm (Bertsekas 1988, paralelleştirme-uyumlu). Kuhn (1955), Munkres (1957).
Örnek
5 teknisyen × 5 müşteri için her teknisyenin her müşteriye gidiş süresi farklı 5×5 maliyet matrisi verilmişse, Macar Algoritması toplam seyahat süresini minimum yapan bire-bir eşleştirmeyi saniyeler içinde verir; sezgisel atamadan %15-30 daha iyi sonuç.