10 июля 2009 в 13:58

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


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




1. Задача (формулировка).


Мы будем проще (в терминах). =)

Представим себе задачу: нужно эффективным образом реализовать некоторый относительно большой проект. Для проекта была отобрана команда первоклассных разработчиков, разбирающихся в различных областях. И так уж посчастливилось, что есть сведения (накопленная статистика) о степени (эффективности) владения технологиями для каждого. Но, к сожалению, разработчиков в команде не так уж и много, а точнее – столько же, сколько и технологий будет использовано в проекте.

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

2. Подход к решению


In the end, all business operations can be reduced to three words: people, product, and profits ©. Если мы попробуем изобразить поставленную перед нам и задачу на листе бумаги, то наверняка получим подобную иллюстрацию, как на рисунке (с такими картинками).

Получился — граф. Вершины слева – разработчики, вершины справа – технологии (задачи). Ребра, которые их соединяют – означают то, насколько разработчик в ней разбирается. Эти цифры, т.е. степень владения разработчиком данной технологией, очень важны, но к ним обратимся чуть позже. А пока мы уже верно наметили направление, в котором эффективно решается данная задача:




3. Графы


Самые основы графов были изложены в статье (max cost), поэтому сразу перейду к терминологии, касающейся данной задачи:

Двудольный граф – граф, у которого существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям. В нашей задаче тоже есть четкое разделение: одни вершины – это разработчики, другие – задачи, и связи (эффективность владения) есть только между разработчиками и задачами.
Паросочетанием неориентированного графа G называется подмножество M его ребер E, выбранное так, что никакие два ребра из M не являются смежными, т.е. не имеют общей вершины. В терминах нашей задачи синонимом этому будет «назначение», чтобы каждый задействованный разработчик взял на себя отдельную задачу. И не получилось такого, что два разработчика прорабатывают одну проблему, или один «бедняга» отвечал за две задачи.

В теории графов наша проблема, как это ни странно, называется Задачей о Назначениях (ЗН). =) Она является частным случаем задачи нахождения максимального паросочетания. В самом деле, мы ведь стремимся максимально задействовать ресурсы, чтобы одновременно прорабатывалось максимальное число технологий, поэтому в терминах графов — пытаемся найти «максимальное паросочетание», составить максимальное количество пар разработчик-задача.

4. Максимальное паросочетание


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



Как же увеличить паросочетания (назначения)?


Выберем незадействованного разработчика, которому еще не назначена задача. Посмотрим, с чем бы он мог справиться, т.е. знакомые ему технологии. Если нашли среди них свободную – отлично, это то, что мы и искали. Назначаем. А если задача уже «занята» другим разработчиком? Попробуем занятому разработчику подыскать другую свободную технологию, ведь в таком случае эту — мы бы назначили нашему незадействованному подопечному. В общем, из вершины незадействованного разработчика или разработчика, которому мы пытаемся переназначить задачу, мы просматриваем все знакомые ему технологии на наличие свободной:
  • если нашли свободную – поиск завершен
  • если задача уже кому-то назначена, то пройдя по этому ребру паросочетания, попытаемся «переназначить» технологию разработчику, участвующему в данном назначении

В ходе такого обхода графа мы пытаемся из «незадействованного разработчика» попасть в «свободную задачу». Таким образом поиск «разворачивается» в следующее дерево:



Добавим еще немного терминологии из теории графов, простыми словами:

Экспонированная вершина – это вершина, которая не участвует в текущем паросочетании. Т.е. либо «незадействованный разработчик», либо «свободная задача».
Альтернирующая цепь – это цепь, ребра которой попеременно лежат или не лежат в паросочетании. (…- владение технологией – назначенная задача – владение технологией – назначенная задача — …)
Альтернирующее дерево – дерево, состоящее из альтернирующих цепей
Аугментальная цепь – это такая альтернирующая цепь, начальная и конечная вершины которой экспонированы. Вот как называется то, что мы и ищем! =)
Аугментальное дерево – соответственно дерево, в котором хотя бы одна из веток – это аугментальная цепь.

Вот и нашли способ наращивать паросочетание, стремясь получить максимальное. Нужно строить альтенирующее дерево. Когда оно станет аугментальным, искать аугментальные цепи из «незадействованного разработчика» в «свободную задачу» и потом «переназначать» задачи вдоль них. Это выгодно, т.к. увеличивает количество «задач в обработке» на 1:



Теперь мы уже сможем задействовать наибольшее количество технологий в проекте. Самое время принять во внимание еще одно важное условие поставленной перед нами проблемы: эффективность владения технологиями. Мы ведь хотим оптимально назначить всем задачи.

5. Венгерский метод.


Найти решение с максимальной суммарной эффективностью (стоимостью). Звучит, в некотором смысле, похоже на задачу об оптимальной упаковке рюкзака. Наводит на мысль. Вот если бы нам представилась возможность действовать по принципу «жадных алгоритмов».

Мы бы для начала всем разработчикам до упора назначили задачи в соответствии с их максимальными способностями. Если всем разработчикам удалось сразу же распределить задачи — отлично. Но такое происходит не часто. Вдруг два человека, оптимально владеют одной и той же технологией, кому она достанется и что делать в этой ситуации? Одному из разработчиков нужно будет подыскать иную свободную задачу, так же наиболее соответствующую его способностям. Если при текущих (максимальных требованиях) условиях не найдется свободной задачи, то нужно будет попробовать подыскать среди задач, предварительно немного занизив наши требования. Как бы искусственно занизить способности разработчиков в графе. Если в таких условиях обнаружим свободную задачу – получим аугментальное дерево. «Поменяем» по цепочке паросочетания, после чего будет +1. И продолжим назначать таким вот оптимальным образом, пока всем не подыщем работу.

Стратегия ясна.


Мы почти разгадали принцип Венгерского алгоритма. Но как все же построить решение по принципу «жадных алгоритмов»: до упора назначить по max способностям, потом чуть занизить способности и добавив к рассмотрению новые задач, до упора назначить их, занизить… и.т.д.? Как оценить способности и оптимальность текущего назначения?

Вся «фишка» этого алгоритма заключается в следующем. Нам дан всего один параметр в графе – эффективность решения определенной задачи разработчиком, что указано на ребрах. Эта величина присвоена парам разработчик-задача. Мы же «разделим» (отделим от пар) эти величины на две. Искусственно добавим два дополнительных параметра. Одни величины будут приписаны вершинам задач, другие — вершинам разработчиков.

Попробую привести такую интерпретацию:
  • у разработчиков мы укажем их «способности», допустим в единицах «сил», просто указывающие на то, насколько эффективно мы можем их задействовать или задействовали.
  • у задач мы укажем их «изученность», или, если можно так выразиться, «переизбыток внимания». Этот параметр будем так же измерять в «силе». Переизбыток внимания к задаче возникает в следующей ситуации. Если мы какого-то разработчика «недогрузили», т.е. он способен решать задачу на 5, а ему досталась всего на 3. То у него остается еще 2 «силы» которые он, в принципе, может уделить какой-то из знакомых ему задач. Бегать между кабинетов, консультировать по телефону, давать советы тем, кто занимается любимой ему технологией.




Таким образом, величины указанные на ребрах мы «разделим» на 2 значения, приписанных уже вершинам: эффективность решения задачи = способность разработчика + изученность задачи. В принципе, логично. Чем способней разработчик или чем более известна технология, тем лучше будет реализована эта часть в проекте. Эффективней.

В конце, после того как мы найдем решение, мы конечно будем учитывать только величины на ребрах, но сейчас эта «фишка» поможет нам найти решение. =)

6. Описание алгоритма


Инициализируем граф. Будучи «упертыми оптимистами», мы для каждого разработчика рассчитаем его максимальную «способность» по знакомым ему технологиям, и присвоим ему это число. Everyone enjoys doing the kind of work for which he is best suited ©. О задачах пока ничего неизвестно, поэтому их «изученность» инициализируем нулями.

При поиске «свободной задачи» для «незадействованного разработчика» мы ограничимся теперь только (назовем их) оптимальными ребрами графа, т.е. теми, для которых выполняется равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина).



Далее мы поступаем так же, как и при поиске максимального паросочетания. Хватаем по очереди незадействованных разработчиков и, подыскивая им свободные задачи, строим альтернирующее дерево (состоящее из чередующихся цепей), но уже только по оптимальным ребрам. Далее возможно 2 ситуации:
  • Удалось обнаружить свободную задачу. Дерево стало аугментальным. «Переназначаем» задачи, наращиваем паросочетание. Начинаем строить альтернирующее дерево заново, т.к. мало ли как там граф изменился
  • Мы не нашли (не достигли) свободную задачу по оптимальным ребрам. А она есть, т.к. начинали ведь мы со свободного разработчика, а в графе у нас одинаковое количество задач и разработчиков. Полученное альтернирующее дерево становится, так называемым, Венгерским (весь метод так же называется). В данном случае нам нужно будет немного понизить наши требования к разработчикам и начать поиски заново. Failure is simply the opportunity to begin again, this time more intelligently (с).




Вот и подошли к последнему моменту Венгерского метода для чего все эти дополнительные параметры и «способности» задумывались. Допустим, что, наращивая альтернирующее дерево, мы в конечном итоге получили — Венгерское дерево. Рассмотрим, какие вершины попадут в это дерево:
  • Незадействованные разработчики, т.к. именно с них мы начинаем стоить дерево
  • Разработчики и задачи, до которых можно дотянуться по оптимальным ребрам из незадействованных разработчиков. Т.к. именно через их «переназначение» мы пытаемся трудоустроить последних.

Снаружи этого дерева, в оставшемся графе будут присутствовать:
  • Разработчики и задачи, находящиеся в паросочетании, но недоступные из свободных вершин (разработчиков). Нашли им работу – нечего их пока трогать.
  • Задачи, недостижимые по оптимальным ребрам – до них нам и нужно будет добраться. Поэтому при построении дерева мы будем отмечать вершины, в которые удалось попасть. А эти задачи, соответственно, останутся неотмеченными.

Далее в цикле мы пробежим по «границе» дерева: по тем ребрам, которые соединяют незадействованных разработчиков или разработчиков, достижимых из них (может их удастся «переназначить»), со смежными задачами (по неоптимальным ребрам). По этим ребрам мы вычислим минимальное на текущий момент «несоответствие» способностей разработчика, чтобы он смог приступить к этой задаче: delta = min(способность разработчика (вершина) + изученность задачи (вершина) — эффективность решения задачи (ребро)).



После чего внутри венгерского дерева мы:
  • Понизим способности разработчиков на delta, чтобы «присоединить» наименее безболезненным способом, по крайней мере, одно ребро к альтернирующему дереву, по которому в следующий раз будем продолжать поиски свободной задачи
  • Повысим «изученность» задач на delta, чтобы внутри уже сейчас построенного аугментального графа ребра — остались оптимальными. Т.е. чтобы сохранилось равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина)

Мини-интерпретация: мы понижаем способности разработчикам, чтобы впоследствии «пристроить» хотя бы одного из них. Мы его пристроим, но он будет работать не в соответствии со своей квалификацией. Он бы смог большего. Поэтому у него высвобождается некоторое количество времени, чтобы проконсультировать коллег по задаче, в которой он наиболее компетентен. Она становится более изученной в команде. Ей в свою очередь наверняка занимался другой разработчик, который теперь тоже сможет подменяться в случае чего. Можно понизить и его компетенцию на изученность задачи. И так далее «по цепочке» в команде повышается «изученность» задач и немного понижаются способности разработчиков, чтобы найти им назначения.



Все. Все шаги данного метода рассмотрены. Продолжаем в том же духе… Success is not final, failure is not fatal: it is the courage to continue that counts.



7. Алгоритм словами, очень кратко


Соберем теперь все до кучи:
  • Инициализация. Разработчикам – max способности. Задачи – не изучены.
  • Пока не всем разработчикам нашли задачи.
    • Пока удается построить аугментальное дерево (находить свободные задачи) по оптимальным ребрам
      • «Переназначаем» задачи, увеличивая паросочетания
    • Не достигли свободной задачи. Венгерское дерево.
      • Понижаем способности разработчиков на min величину


8. Листинг


Код, конечно, будет покороче, чем все мое описание. =)

Я взял его здесь. На мой взгляд, очень хорошая реализация. Единственное отличие, у автора приведен код метода минимизации назначений (если, допустим, на ребрах – зарплата), а в статье мы распределяли задачи с целью получения максимальной эффективности. Поэтому, слегка модифицировав код, приведу ниже реализацию максимального метода:

int n;
vector < vector<int> > a;      // Матрица эффективности a[разраб][задача]
vector<int> xy, yx;             // Паросочетания: xy[разраб], yx[задача]
vector<char> vx, vy;            // Альтернирующее дерево vx[разраб], vy[задача]
vector<int> maxrow, mincol;     // Способности, изученность

bool dotry (int i) {
    if (vx[i]) return false;
    vx[i] = true;
    for (int j=0; j<n; ++j)
        if (a[i][j]-maxrow[i]-mincol[j] == 0)
            vy[j] = true;
    for (int j=0; j<n; ++j)
        if (a[i][j]-maxrow[i]-mincol[j] == 0 && yx[j] == -1) {
            xy[i] = j;
            yx[j] = i;
            return true;
        }
    for (int j=0; j<n; ++j)
        if (a[i][j]-maxrow[i]-mincol[j] == 0 && dotry (yx[j])) {
            xy[i] = j;
            yx[j] = i;
            return true;
        }
    return false;
}

int main() {

    // ... чтение a ...
    
    mincol.assign (n, 0);
    minrow.assign (n, 0);
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            maxrow[i] = max (maxrow[i], a[i][j]);

    xy.assign (n, -1);
    yx.assign (n, -1);
    for (int c=0; c<n; ) {
        vx.assign (n, 0);
        vy.assign (n, 0);
        int k = 0;
        for (int i=0; i<n; ++i)
            if (xy[i] == -1 && dotry (i))
                ++k;
        c += k;
        if (k == 0) {
            int z = INF;
            for (int i=0; i<n; ++i)
                if (vx[i])
                    for (int j=0; j<n; ++j)
                        if (!vy[j])
                            z = min (z, maxrow[i]+mincol[j]-a[i][j]);
            for (int i=0; i<n; ++i) {
                if (vx[i]) maxrow[i] -= z;
                if (vy[i]) mincol[i] += z;
            }
        }
    }

    int ans = 0;
    for (int i=0; i<n; ++i)
        ans += a[i][xy[i]];
    printf ("%d\n", ans);
    for (int i=0; i<n; ++i)
        printf ("%d ", xy[i]+1);
}


* This source code was highlighted with Source Code Highlighter.


9. Итого


Если кто-то видит Венгерку впервые. И после прочтения описания, а за ним листинга – возникнет уверенное впечатление «да тут по листингу и без этих описаний все понятно, что было распинаться». Буду все же надеяться, что хоть отчасти описание добавило понимания в работу алгоритма. Буду искренне рад за Вас! а мне, в свою очередь, это немного даст почувствовать, что писал, наверное, не зря. =)

+54
17333
129
vikds 107,4 G+

Комментарии (34)

+7
zloy_alu #
кекеке. чистейшая дискретная математика же.
0
PoCTo #
у нас это называлось «олимпиадное программирование», и не было ни одного упоминания дискретной математики :)
+4
0leGG #
А это и есть дискретка. А в случае венгерки — вообще теория принятия решений. Олимпиадное программирование — более общее понятие, туда можно и разбор грамматик, и вычислительную геометрию вместить. Так что то, что у вас не упоминали — не значит, что это не задача дискретной математики.
0
Brand #
Стандартные паросочетания. Как к графам дискретки, так и к графам программирования (что одно и то же).
0
Aco #
Вот ещё бы алгоритм определения мастества владения технологией…
+3
kachkaev #
Слегка напомнило транспортную задачу и методы её решения:)
+2
vikds #
Да. Спасибо большое. Транспортную задачу я тоже попробовал описать =)
В моих блогах. Не даю ссылки, чтобы лишний раз не PR-иться… мне этого не надо. Просто be useful =)
+1
coldFlame #
Статья хорошая и нужная, а вот код по-моему недостаточно читабельный.
Как реализация годится, а как иллюстрация — нет.
+1
vikds #
А код — я согласен не по мотивам «Стива МакКонела».
Но тем не менее… я взял листочек, взял этот код, нарисовал произвольную ситуацию — и, в принципе, он оцень неплохо описывает алгоритм… Аналоги (и мой же ACM ICPC'шный код который я помню наизусть) описывают его на 350 строк… Я так же не думал, что это может быть интересно… =) Ошибался…

Это же программирование… Be creative (ни против Вашего мнения, просто настроение такое) =))
+2
mikhanoid #
IMHO, было бы гораздо понятнее, если бы задача была сведена к простой абстрактной формулировке на графе, а потом был бы приведён алгоритм её решения с доказательством корректности. А то все эти пространные рассуждения ничего не дают, потому что разработчики и задачи автоматически не ассоциируются со структурами данных.
0
vikds #
Честно. Я как минимум 2 недели думал над аналогией. =)
Прошу прощения, если не удачная получилась… Я старался…

Люблю когда Keep it simple. =) sorry, если не удалось — ставьте минус.
0
mikhanoid #
Не. Дело не в аналогии. Можно было бы просто написать: вот есть задача о назначении работников на работу. Вот её так-то формализуем. Получаем задачу о поиске паросочетания в двудольном графе. Решаем её так-то и так-то. Аналогии же и оперирование неабстрактными понятиями тут только затуманивают смысл алгоритма. Мне так кажется. Минусовать не буду, ибо алгоритмы — это хорошо.
+2
mikhanoid #
Кстати. Было бы неплохо вместо 'альтернирующий' наприсать 'чередующийся', а вместо 'аугментальный' 'улучшающий'. Вроде как по смыслу и по лёгкости чтения эти варианты лучше.
+1
sunnybear #
если бы все это в онлайне было — цены бы не было: расписал возможности разработчиков и менеджеров, формально описал задачи. И все. Проект готов :)
0
vikds #
Простите. Оченью люблю
В Вашем webo.in — очень нравится профессиональный подход!
=))) Да. Мои задачи — это «сферический конь в вакууме», но харбра-люди просили… Я знал этот алгоритм и не мог не поделиться… Я чувствовал ответственность (что пообещал) — вот и написал. На Ваше суждение. =))))

А оптимизатор web — имхо, очень интересно.
Хотелось бы быть in the edge of recently технологии =)
0
pcmaniac #
Как мне говорил мой преподаватель по дискретке: «Посмотри на эти красивые и грамотные методы. Они настолько правильные, что никогда не будут применяться в жизни!»

А за толкование — спасибо. Однозначно в мемориз!
0
KKS #
помню готовился к экзамену по структурам и алгоритмам, разбирался с венгерским алгоритмом, и в этот момент (~4 часа ночи) захотелось придумать нечто другое своё… то что придумал записал в блокнотик, на всех тестовых наборах сработало, доказывать верность не стал :-)
0
Shtorkin #
Взрыв мозга. Но интересно, спасибо большое. Пригодится.
0
vikds #
Благодарю!!!

Нечего больше сказать.
Единственное — я с ДВ нашей Родины. И мне пришлось изучать все это самому, начиная с «BFS» и вплоть до Венгерки. Имхо, это апофеоз разумных алгоритмов на графах, очень рад что Вы это знали!!! =)))

* мне во Владе понадобилось 2 года, чтобы с BFS «подняться» до Венгерки =)))
0
Shtorkin #
Придется, думаю, все эти методы на практическом уровне рассматривать, учитывая недавние предложения начать IT-бизнес :-)
Удачи Вам.
0
vikds #
Благодарю Вас! очень приятно! за приятные отзывы! =)
Насчт практичкеского приминения, не знаю, но для понимани — думаю полезно. =)))
0
vikds #
Прошу прощения, я с Владивостока.
У нас 2:30. Очень спать хочется…
Потому — очепятки =) Благодарю за понимание…
+3
0leGG #
Мм, терминология какая-то непривычная. Обычно во всей литературе русскоязычной альтерирующая == чередующаяся. А так — классная статья, прочёл, освежил знания.
+1
vikds #
Спасибо (сорри, что отвтчаю пока на каждый коммент)!

Я сам долго «передумывал», как ее приподнести Хабра-сообществу, не отягощая не очень нужной терминологией. Пытался… =)

Не очень нужны эти «замутные» термины, но понимание как это далается — думаю пригодится! =) Мы Ведь Хабр! =))
0
IDDQD #
Это не совсем для программистов :)
+1
0leGG #
А я не совсем программист. Спортивный программист — да, но я в нашей команде не кодер, а математик. Потому и книги настольные не Страуструп и Александреску, а Кормен сотоварищи :)
0
EgAr #
Спасибо. Вспомнил институтские занятия по параллельному программированию (в рамках курса вычислительных систем). Алгоритм применялся для распределения задачи состоящей из подзадач между узлами вычислительной системы.
0
mikhanoid #
Хм. Странно… А что играло роль 'веса'?
НЛО прилетело и опубликовало эту надпись здесь
+1
Krofes #
Большое спасибо!
С дискретной математикой и ТПР как-то не сложилось в университете, на парах было откровенно скучно.
Если бы лекции разбавляли такими замечательными примерами — было бы намного приятнее учиться.
+2
HammeremmaH #
Благодарю.
Как и предидущая Ваша статья про нахождение пути, эта — написана доступным языком. Действительно, не всегда сухие определения раскрывают суть и логику решения, а подкрепление доводов картинками — удачный ход.
Продолжайте. :)
+1
bethoven #
Хорошо расписано %) Интересует вариант когда (в ваших терминах) много задач (10-300) и мало разработчиков (3-10). К примеру есть 30 задач, необходимо их распределить на 5 разработчиков (в один момент времени разработчик выполняет одну задачу и задачи не могут быть прерваны). Известны сроки выполнения задач для каждого разработчика. Необходимо выполнить все задачи за минимально возможное время. $) Вот хотелось бы увидеть статью про алгоритмы для такого рода задач. $)

+1
Aquary #
Земляк, подумай о карьере преподавателя, в параллель к основной :) Доступно объяснять сложные вещи — этого сильно не хватает в преподавательской среде :)
0
sova #
1.
vector maxrow, mincol;

//… чтение a…

mincol.assign (n, 0);
minrow.assign (n, 0);

вместо minrow следует написать в данной задаче maxrow потому что minrow вообще не объявленное имя
2. используется INF но оно не объявленно в данном коде

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

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.