[Algorytmika] Problem przydziału ekspertów

Awatar użytkownika
lukas1929
Użytkownik
Użytkownik
Posty: 45
Rejestracja: 14 paź 2017, o 12:43
Płeć: Mężczyzna
Lokalizacja: Haugesund
Podziękował: 1 raz
Pomógł: 9 razy

[Algorytmika] Problem przydziału ekspertów

Post autor: lukas1929 » 14 paź 2017, o 15:16

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
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Algorytmika] Problem przydziału ekspertów

Post autor: Afish » 15 paź 2017, o 05:38

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.

ODPOWIEDZ