[Algorytmika] Problem przydziału ekspertów

[lukas1929]

Jest następujące zadanie do wykonania.

Mamy zbiór n ekspertów i m zadań. Każde zadanie wymaga pewnych umiejętności i każdy z ekspertów posiada pewne umiejętności co zapisujemy w wektorze o pewnej ustalonej długości.

Na przykład, umiejętności eksperta:

[1 0 0 1 0 1 1]

wymagania dla zadania:

[2 0 1 0 0 0 1]

(takie wymaganie oznaczają, że w zbiorze ekspertów przypisanych do zadania powinno być co najmniej dwóch mających umiejętność 1, co najmniej jeden mający umiejętność 3, co najmniej jeden mający ostatnią umiejętność)

Problemem jest przypisanie ekspertów do zadań (każdy ekspert do jednego zadania, do każdego zadania zbiór ekspertów) w taki sposób aby ilość niepokrytych zapotrzebowań na zadaniach była jak najmniejsza.

Poszukuje optymalnego algorytmu dla tego problemu o złożoności niższej niż wykładnicza. Popularny algorytm dla problemu przypisywania Hungarian algorithm to algorytm przydziału pracowników do zadań po najmniejszych kosztach. Tutaj mamy odwrotnie, bo chodzi o maksymalizowanie liczby wykorzystanych umiejętności (lecz to akurat łatwo odwrócić). Głównym problemem jest to, że u mnie chodzi o przydział zbioru ekspertów do każdego zadania (nie 1-1 jak w standardowym Hungarian algorithm).

Czy przy pewnych modyfikacjach dałoby się zastosować Hungarian algorithm dla tego problemu ?

Nie pogardziłbym również jakąś inną optymalną metodą.

.

[Afish]

Dla mnie bardziej wygląda to na modyfikację set cover niż metody węgierskiej. Nawet rozwiązanie problemu decyzyjnego niespecjalnie przybliża do ogólnego problemu, bo ciągle wchodzi wykładnicza liczba podzbiorów. Osobiście poszukałbym jakiejś heurystyki połączonej z zasadą a priori.

Jednocześnie myślałem nad wielomianową redukcją do set cover i nie doszedłem do niczego konkretnego, wiec nie mam pewności, że to coś tego pokroju, niemniej takie mam przeczucie.