Problem przydziału na wiele dni

Mam problem, który można sprowadzić do problemu przydziału. (W poprzednim pytaniu dowiedziałem się, jak to zrobić.)

Co oznacza, że mamy zestaw $A$ agentów i zestaw zadań, a także funkcję kosztu . Musimy znaleźć zadanie, aby całkowity koszt był minimalny. $T$ $c(i,j)$

Algorytm węgierski może znaleźć optymalne rozwiązanie, w co najmniej . Które brzmi dla mnie dobrze. $O(n^4)$

Mój nowy problem to: Dana liczba dni. Muszę rozwiązać problem przypisania na każdy dzień, aby każde zadanie było wykonywane codziennie, a żaden agent nie wykonał tego samego zadania dwa razy .

Co próbowałem: Możemy uruchomić węgierski algorytm osobno dla każdego dnia i ograniczyć liczbę możliwych kombinacji w oparciu o wynik z poprzedniego dnia. Wpadłoby to jednak w kłopoty w późniejszych dniach, w których najprawdopodobniej niemożliwe będzie znalezienie realnego rozwiązania.

Innym pomysłem jest integracja wyszukiwania lokalnego w celu zmiany decyzji podjętych poprzedniego dnia. Ale myślę, że nie możemy na tym polegać.

Przypadki, z którymi muszę się zmierzyć, będą gdzieś . Macierz kosztów będzie miała wiele takich samych wartości (np. Głównie 1 lub nieskończoność, tylko około 2 lub 3). Tak więc podczas węgierskiego algorytmu jest dużo miejsca na stworzenie różnych optymalnych rozwiązań na jeden dzień. $|A| = |T| = 500$ $C(i,j)$

Z przyjemnością usłyszę kilka pomysłów lub doradzę, jak znaleźć dobre rozwiązanie problemu. Z góry dziękuję.

algorithms graph-theory assignment-problem

— Patrick Schmidt
źródło

To świetne pytanie! Sugerowałbym użycie przepływu minimalnego kosztu, twierdzenia małżeństwa Halla i maksymalnego dwustronnego dopasowania.

— Peter Shor,

Jest na to sposób w czasie wielomianowym. Naszkicuję algorytm (w odwrotnej kolejności ... najpierw wykonaj krok 2, a drugi krok 1).

$nk$ $(i,j)$ $k$ $k$ $k$ $nk$
$nk$ $s$ $t$ $k$ $0$ $k$ $0$ $i$ $j$ $1$ $c(i,j)$ $0$ $1$ $(i,j)$ $1$

Istnieje wiele algorytmów, które mogą rozwiązać minimalny przepływ ; jest to szczególny przypadek programowania liniowego. W przypadku twojego problemu algorytm, który szkicuję, powinien być nie tylko czasem wielomianowym, ale także praktyczny.

— Peter Shor
źródło

Ostatnie pytanie: algorytm przepływu kosztu minimalnego w kroku 2 (wybrałem anulowanie cyklu na początek) zapewnia optymalne rozwiązanie. Algorytm maksymalnego dopasowania w kroku 1 robi to. Czy to koniecznie oznacza, że całe rozwiązanie jest optymalne? Ponieważ zgaduję, że problem dotyczy NP-Complete.

— Patrick Schmidt

Całe rozwiązanie jest optymalne. Byłoby to dobre pytanie do przypisania w kombinatorycznym kursie optymalizacji, ponieważ jest to nieco zaskakujące, że możesz to zrobić.

— Peter Shor