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 algorithmt (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 Hungarian algorithmt.
Czy przy pewnych modyfikacjach dałoby się zastosować Hungarian algorithmt dla tego problemu ?
Nie pogardziłbym również jakąś inną optymalną metodą.
.