Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Задача о назначениях для матрицы из 0 и 1 |
Автор: Einwill 21.8.2007, 18:41 |
Интересует алгоритм решения задачи о назначениях в случае, когда матрица цен содержит только нули или единицы. Оригинальная Задача о назначениях (Assignment problem) формулируется так: Пусть у нас есть n рабочих и n задач, которые надо выполнить. Матрица nxn описывает наши потери, в случае назначения конкретного рабочего на конкретную задачу. Каждого рабочего можно назначить только на одну задачу, и все задачи должны быть "назначены" кому-либо. Цель -- минимизировать потери. Т.о. в данной матрице надо выбрать n элементов (по одному в каждом столбцу и в каждой строке) так, чтобы сумма выбранных элементов была минимальна. На математическом языке: Для матрицы A надо найти такую перестановку \pi, что \sum A(i,\pi(i)) -- минимальна. Эта задача решается Венгерским алгоритмом (Алгоритмом Куна-Мункера). Это строго-полиномиальный алгоритм, со сложностью O(n^3). Так вот, меня интересует наиболее быстрый алгоритм решения этой задачи для случая, когда матрица состоит только из 0 и 1. Буду благодарен за любые ссылки и подсказки ![]() |
Автор: ne0n 21.8.2007, 21:24 |
если не ошибаюсь Метод ветвей и границ.... |
Автор: Einwill 21.8.2007, 23:52 |
Ну, метод ветвей и границ тут, очевидно, проиграет Венгерскому алгоритму. Ладно, сам спросил, сам отвечу ![]() Матрицу цен в данном случае можно рассматривать, как двудольный граф (n и n вершин). И тогда мы получаем хорошо изученную задачу паросочетания невзвешенного двудольного графа (Bipartite matching problem). наилучший из известных алгоритмов решает задачу за время O(n^{1/2}*log(n^3/m)), где m -- кол-во ребер в двудольном графе (кол-во единиц в матрице). Таки это быстрее, чем O(n^3) Венгерского алгоритма ![]() Рекомендуются к изучению ссылки, упомянутые тут: http://www.cs.sunysb.edu/~algorith/files/matching.shtml В оссобенности: http://www.avglab.com/andrew/soft.html http://www.cs.sunysb.edu/~algorith/implement/bipm/implement.shtml (Ссылки содержат реализацию на Pascal, C/C++, Modula) |