Задача о назначениях: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) Описание задачи |
Daryin (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
== Алгоритмы решения задачи == | == Алгоритмы решения задачи == | ||
* [[Венгерский алгоритм]]<ref>Kuhn, H W. “The Hungarian Method for the Assignment Problem.” Naval Research Logistics Quarterly 2, no. 1 (March 1955): 83–97. doi:10.1002/nav.3800020109.</ref><ref>Kuhn, H W. “Variants of the Hungarian Method for Assignment Problems.” Naval Research Logistics Quarterly 3, no. 4 (December 1956): 253–58. doi:10.1002/nav.3800030404.</ref><ref>Munkres, James. “Algorithms for the Assignment and Transportation Problems.” Journal of the Society for Industrial and Applied Mathematics 5, no. 1 (March 1957): 32–38. doi:10.1137/0105003.</ref> для линейной задачи, сложность <math>O(n^4)</math> (может быть уменьшена до <math>O(n^3)</math>); | * [[Венгерский алгоритм]]<ref>Kuhn, H W. “The Hungarian Method for the Assignment Problem.” Naval Research Logistics Quarterly 2, no. 1 (March 1955): 83–97. doi:10.1002/nav.3800020109.</ref><ref>Kuhn, H W. “Variants of the Hungarian Method for Assignment Problems.” Naval Research Logistics Quarterly 3, no. 4 (December 1956): 253–58. doi:10.1002/nav.3800030404.</ref><ref>Munkres, James. “Algorithms for the Assignment and Transportation Problems.” Journal of the Society for Industrial and Applied Mathematics 5, no. 1 (March 1957): 32–38. doi:10.1137/0105003.</ref> для линейной задачи, сложность <math>O(n^4)</math> (может быть уменьшена<ref>Tomizawa, N. “On Some Techniques Useful for Solution of Transportation Network Problems.” Networks 1, no. 2 (1971): 173–94. doi:10.1002/net.3230010206.</ref> до <math>O(n^3)</math>); | ||
* [[Алгоритм аукциона]]<ref>Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.</ref><ref>Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.</ref>; | * [[Алгоритм аукциона]]<ref>Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.</ref><ref>Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.</ref>; | ||
* [[Алгоритм Гопкрофта-Карпа]]<ref>Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.</ref> для задачи с единичными ценами, сложность <math>O(m \sqrt{n})</math>. | * [[Алгоритм Гопкрофта-Карпа]]<ref>Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.</ref> для задачи с единичными ценами, сложность <math>O(m \sqrt{n})</math>. | ||
Версия от 21:09, 10 июня 2015
Постановка задачи
Пусть имеется [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] задача называется линейной: каждому агенту достаётся ровно одна задача, и каждая задача достаётся ровно одному агенту.
В случае единичных весов возникает задача о наибольшем паросочетании в двудольном графе: назначить как можно больше задач.
Алгоритмы решения задачи
- Венгерский алгоритм[1][2][3] для линейной задачи, сложность [math]\displaystyle{ O(n^4) }[/math] (может быть уменьшена[4] до [math]\displaystyle{ O(n^3) }[/math]);
- Алгоритм аукциона[5][6];
- Алгоритм Гопкрофта-Карпа[7] для задачи с единичными ценами, сложность [math]\displaystyle{ O(m \sqrt{n}) }[/math].
Литература
- ↑ Kuhn, H W. “The Hungarian Method for the Assignment Problem.” Naval Research Logistics Quarterly 2, no. 1 (March 1955): 83–97. doi:10.1002/nav.3800020109.
- ↑ Kuhn, H W. “Variants of the Hungarian Method for Assignment Problems.” Naval Research Logistics Quarterly 3, no. 4 (December 1956): 253–58. doi:10.1002/nav.3800030404.
- ↑ Munkres, James. “Algorithms for the Assignment and Transportation Problems.” Journal of the Society for Industrial and Applied Mathematics 5, no. 1 (March 1957): 32–38. doi:10.1137/0105003.
- ↑ Tomizawa, N. “On Some Techniques Useful for Solution of Transportation Network Problems.” Networks 1, no. 2 (1971): 173–94. doi:10.1002/net.3230010206.
- ↑ Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.
- ↑ Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.
- ↑ Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.