[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

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/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

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Hungarian_algorithm

).

Czy przy pewnych modyfikacjach dałoby się zastosować [url=https://en.wikipedia.org/wiki/Hungarian_algorithm]Hungarian algorithm[/url] 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.