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
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ą.
.