Задача назначения на несколько дней

У меня есть проблема, которая может быть сведена к проблеме назначения. (В предыдущем вопросе я узнал, как это сделать.)

Это означает, что у нас есть набор агентов и набор задач а также функция стоимости . Нам нужно найти назначение, чтобы общая стоимость была минимальной.$A$c ( i , j $T$$c(i,j)$

Венгерский алгоритм может найти оптимальное решение по крайней мере . Что звучит хорошо для меня.$O(n^4)$

Моя новая проблема: есть определенное количество дней. Я должен решить задачу назначения для каждого дня, чтобы каждая задача выполнялась каждый день, и ни один агент не выполнял одну и ту же задачу дважды .

Что я пробовал: мы могли запускать венгерский алгоритм отдельно для каждого дня и ограничивать количество возможных комбинаций на основе результата предыдущего дня. Но это может привести к проблемам в более поздние дни, когда, скорее всего, будет невозможно найти выполнимое решение.

Другая идея - каким-то образом интегрировать локальный поиск, чтобы изменить решения, принятые в предыдущий день. Но я думаю, что мы не можем полагаться на это.

Проблемы, с которыми мне приходится сталкиваться, будут где-то рядом . Матрица затрат будет иметь много одинаковых значений (например, в основном 1 или бесконечность, только некоторые 2 или 3). Таким образом, во время венгерского алгоритма есть много места для создания различных оптимальных решений за один день.С ( i , j $|A| = |T| = 500$$C(i,j)$

Я был бы рад услышать некоторые идеи или советы, как найти хорошее решение проблемы. Заранее спасибо.

Есть путь к этому в полиномиальное время. Я нарисую алгоритм (в обратном порядке ... сначала выполните шаг 2, а затем шаг 1).

1. если мы сможем найти набор из пар агент-задача ( i , j ) , так что каждая задача будет ровно k пар, каждый агент будет ровно k пар и ни одна пара не появится более одного раза, тогда мы сможем найти k назначений которые вместе покрывают этот п K пар агента задач. Мы делаем это путем многократного использования алгоритма максимального двудольного сопоставления, чтобы найти идеальное совпадение в соответствующем двудольном графе, и удаления этого назначения из графа. Теорема Холла о браке гарантирует, что мы можем сделать это.$nk$$(i,j)$$k$$k$$k$$nk$

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

Есть много алгоритмов, которые могут решить поток минимальных затрат ; это особый случай линейного программирования. Для вашей проблемы размера алгоритм, который я рисую, должен быть не только полиномиальным, но и практичным.