Задача о назначениях

Постановка задачи

Пусть имеется [math]\displaystyle{ n }[/math] агентов и [math]\displaystyle{ m }[/math] задач, которые могут быть распределены между этими агентами. Каждому агенту может быть выделена только одна задача, и каждая задача может быть выделена только одному агенту. Стоимость присвоения [math]\displaystyle{ i }[/math]-й задачи [math]\displaystyle{ j }[/math]-му агенту равна [math]\displaystyle{ c(i, j) }[/math]. В случае [math]\displaystyle{ c(i, j) = \infty }[/math] задача [math]\displaystyle{ j }[/math] не может быть назначена агенту [math]\displaystyle{ i }[/math].

Задача о назначениях: сформировать допустимое множество назначений [math]\displaystyle{ A = \{ (i_1, j_1), \ldots, (i_k, j_k) \} }[/math], [math]\displaystyle{ k = \min \{m, n\} }[/math], имеющее макисмальную суммарную стоимость:

[math]\displaystyle{ C(A) = \sum_{s = 1}^k c(i_s, j_s) \to \max. }[/math]

Варианты задачи

При [math]\displaystyle{ m = n }[/math] задача называется линейной: каждому агенту достаётся ровно одна задача, и каждая задача достаётся ровно одному агенту.

В случае единичных весов возникает задача о наибольшем паросочетании в двудольном графе: назначить как можно больше задач.

Алгоритмы решения задачи

• Венгерский алгоритм для линейной задачи, сложность [math]\displaystyle{ O(n^4) }[/math] (может быть уменьшена до [math]\displaystyle{ O(n^3) }[/math]);
• Алгоритм аукциона;
• Алгоритм Гопкрофта-Карпа для задачи с единичными ценами, сложность [math]\displaystyle{ O(m \sqrt{n}) }[/math].