Standart olmayan ödev için Munkres algoritması sorunları

Question

Her zamanki Munkres/Macar algoritmasının çözüme uyacak kadar donanımlı görünmediği bir atama problemi var.

Geleneksel atama probleminde, n işlere atanması gereken işçiler ve her bir işçiye her işin atanması maliyetini içeren bir matris vardır.

Bu varyasyonda, sadece m (m < n) çalışanımız var. Munkres algoritması eşit sayıda işçi ve iş gerektirdiğinden, yedek işlere atanabilecek (n - m) "kukla" işçiler yaratırız. Ek olarak, işler kendileri çok sayıda ayrı kategoride düzenlenir.

Her kategoriden en az 1 işin gerçek (mankensiz) bir işçiye atanması kısıtını empoze etmek istiyoruz. Bu, zarif bir şekilde yapmak zordur: Örneğin, her bir kategoriden rastgele bir iş seçebilir ve her bir gerçek-çalışanla ilişkili maliyeti yapay olarak söndürebilirsiniz, ancak bu, son tahsisin bütünlüğünü ciddi biçimde tehlikeye atan çok kaba bir çözümdür.

Şu anda ne yapıyoruz, algoritmayı her defasında birden çok kez çalıştırıyor, her defasında çıktı atamasını değerlendiriyor ve daha sonra maliyet matrisini değiştiriyor, öyle ki, yalnızca kukla işçiler tarafından atanan kategorilerdeki tüm işlerin maliyetleri azalıyor. Bu yeterli bir şekilde çalışır, ancak orta büyüklükteki veri kümeleri için (n = = 500) süreç biraz zaman alabilir (her Munkres ataması hesaplamak için belki de 10 saniye sürer ve yeterli kategoriler ile önemsiz sayıda yineleme olabilir).

Değiştirilmiş bir Munkres algoritması veya tamamen farklı bir algoritma var mı, bu sorunu daha verimli bir şekilde çözecek mi?

Answer 1

Kategoriler ayrık mı? Her işin bir kategorisi var mı? Öyleyse, minimum maliyet akışı hakkında?

Düğüm tipi:

SRC - source 
SNK - sink 
C - a node or each category 
J - a node for each job 
W - a node for each worker 

bağlantılar:

1) from SRC to C, capacity 1, cost 0 
2) from SRC to C, capacity infinite, cost a high number 
3) from C to J, capacity 1, cost 0 
4) from J to W, capcity 1, the cost of job J done by worker W 
5) from W to SNK, cost 0, capacity 1 

Daha sonra her bir kategori (mümkünse), en az bir işçinin alacak nolu birinci tip 1 bağlantıları dolduracaktır algoritması.