Sözlük · approach
Ağırlıklı İki Parçalı Eşleştirme
İki ayrık düğüm kümesi arasında, kenarların ağırlıklı olduğu iki parçalı bir grafte, maksimum (veya minimum) toplam ağırlığa sahip eşleştirmeyi bulma OR problemi.
Weighted Bipartite MatchingBipartite Matching WeightedWeighted Maximum Matching
Ağırlıklı iki parçalı eşleştirme (weighted bipartite matching), iki ayrık düğüm kümesi U ve V arasında, her olası (u,v) kenarına bir ağırlık atanmış olan iki parçalı bir grafta, hiçbir düğüm birden fazla kenara dokunmamak şartıyla, maksimum (veya minimum) toplam ağırlığa sahip kenar kümesini bulma problemidir. Operasyon araştırmasının ve kombinatoryel optimizasyonun en genel eşleştirme çerçevesidir; özel halleri: kare ve dengeli (|U| = |V|) durumu **atama problemi**dir ve Macar Algoritması (Kuhn 1955; Munkres 1957) ile O(n³) polinom-zamanda çözülür; dikdörtgen durum (|U| ≠ |V|) için dummy düğüm/kenar ile genişletme uygulanır; her iki tarafın da serbestçe eşleşmemiş kalabildiği maksimum-ağırlıklı eşleştirme problemleri ise daha geneldir. Algoritmalar: ağırlıklı maksimum eşleştirme polinom-zamanda çözülebilir (Edmonds 1965 ve sonrası), klasik atama hali için Macar O(n³), LAP (Jonker-Volgenant 1987) pratikte daha hızlı. Saha uygulamaları: personel-görev atama, müşteri-teknisyen eşleştirme, reklam yerleştirme, online iki-parçalı eşleştirme (#034), ihale-paket eşleştirme. Burkard, Dell'Amico ve Martello (2009) kanonik referans.
Örnek
10 personel + 10 görev arasında, her (personel, görev) çiftine bir yetkinlik-süre puanı atanmışsa, ağırlıklı iki parçalı eşleştirme toplam puanı maksimize eden bire-bir atamayı verir; Macar Algoritması ile O(n³) çözüm garantili optimum.