Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Задача о назначениях для матрицы из 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. Буду благодарен за любые ссылки и подсказки smile Реализации на любых языках программирования тоже приветствуются.

Автор: ne0n 21.8.2007, 21:24
если не ошибаюсь Метод ветвей и границ....

Автор: Einwill 21.8.2007, 23:52
Ну, метод ветвей и границ тут, очевидно, проиграет Венгерскому алгоритму.

Ладно, сам спросил, сам отвечу smile

Матрицу цен в данном случае можно рассматривать, как двудольный граф (n и n вершин). И тогда мы получаем хорошо изученную задачу паросочетания невзвешенного двудольного графа (Bipartite matching problem). наилучший из известных алгоритмов решает задачу за время O(n^{1/2}*log(n^3/m)), где m -- кол-во ребер в двудольном графе (кол-во единиц в матрице). Таки это быстрее, чем O(n^3) Венгерского алгоритма smile И, что удивительно, это быстрее, чем "разумноожидаемое" O(n*m).

Рекомендуются к изучению ссылки, упомянутые тут: 
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)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)