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

[zloy_alu]

кекеке. чистейшая дискретная математика же.

[PoCTo]

у нас это называлось «олимпиадное программирование», и не было ни одного упоминания дискретной математики :)

[0leGG]

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

[Brand]

Стандартные паросочетания. Как к графам дискретки, так и к графам программирования (что одно и то же).

[Aco]

Вот ещё бы алгоритм определения мастества владения технологией…

[kachkaev]

Слегка напомнило транспортную задачу и методы её решения:)

[vikds]

Да. Спасибо большое. Транспортную задачу я тоже попробовал описать =)
В моих блогах. Не даю ссылки, чтобы лишний раз не PR-иться… мне этого не надо. Просто be useful =)

[coldFlame]

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

[vikds]

А код — я согласен не по мотивам «Стива МакКонела».
Но тем не менее… я взял листочек, взял этот код, нарисовал произвольную ситуацию — и, в принципе, он оцень неплохо описывает алгоритм… Аналоги (и мой же ACM ICPC'шный код который я помню наизусть) описывают его на 350 строк… Я так же не думал, что это может быть интересно… =) Ошибался…

Это же программирование… Be creative (ни против Вашего мнения, просто настроение такое) =))

[mikhanoid]

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

[vikds]

Честно. Я как минимум 2 недели думал над аналогией. =)
Прошу прощения, если не удачная получилась… Я старался…

Люблю когда Keep it simple. =) sorry, если не удалось — ставьте минус.

[mikhanoid]

Не. Дело не в аналогии. Можно было бы просто написать: вот есть задача о назначении работников на работу. Вот её так-то формализуем. Получаем задачу о поиске паросочетания в двудольном графе. Решаем её так-то и так-то. Аналогии же и оперирование неабстрактными понятиями тут только затуманивают смысл алгоритма. Мне так кажется. Минусовать не буду, ибо алгоритмы — это хорошо.

[mikhanoid]

Кстати. Было бы неплохо вместо 'альтернирующий' наприсать 'чередующийся', а вместо 'аугментальный' 'улучшающий'. Вроде как по смыслу и по лёгкости чтения эти варианты лучше.

[sunnybear]

если бы все это в онлайне было — цены бы не было: расписал возможности разработчиков и менеджеров, формально описал задачи. И все. Проект готов :)

[vikds]

Простите. Оченью люблю
В Вашем webo.in — очень нравится профессиональный подход!
=))) Да. Мои задачи — это «сферический конь в вакууме», но харбра-люди просили… Я знал этот алгоритм и не мог не поделиться… Я чувствовал ответственность (что пообещал) — вот и написал. На Ваше суждение. =))))

А оптимизатор web — имхо, очень интересно.
Хотелось бы быть in the edge of recently технологии =)

[pcmaniac]

Как мне говорил мой преподаватель по дискретке: «Посмотри на эти красивые и грамотные методы. Они настолько правильные, что никогда не будут применяться в жизни!»

А за толкование — спасибо. Однозначно в мемориз!

[KKS]

помню готовился к экзамену по структурам и алгоритмам, разбирался с венгерским алгоритмом, и в этот момент (~4 часа ночи) захотелось придумать нечто другое своё… то что придумал записал в блокнотик, на всех тестовых наборах сработало, доказывать верность не стал :-)

[Shtorkin]

Взрыв мозга. Но интересно, спасибо большое. Пригодится.

[vikds]

Благодарю!!!

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

* мне во Владе понадобилось 2 года, чтобы с BFS «подняться» до Венгерки =)))

[Shtorkin]

Придется, думаю, все эти методы на практическом уровне рассматривать, учитывая недавние предложения начать IT-бизнес :-)
Удачи Вам.

[vikds]

Благодарю Вас! очень приятно! за приятные отзывы! =)
Насчт практичкеского приминения, не знаю, но для понимани — думаю полезно. =)))

[vikds]

Прошу прощения, я с Владивостока.
У нас 2:30. Очень спать хочется…
Потому — очепятки =) Благодарю за понимание…

[0leGG]

Мм, терминология какая-то непривычная. Обычно во всей литературе русскоязычной альтерирующая == чередующаяся. А так — классная статья, прочёл, освежил знания.

[vikds]

Спасибо (сорри, что отвтчаю пока на каждый коммент)!

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

Не очень нужны эти «замутные» термины, но понимание как это далается — думаю пригодится! =) Мы Ведь Хабр! =))

[0leGG]

А я не совсем программист. Спортивный программист — да, но я в нашей команде не кодер, а математик. Потому и книги настольные не Страуструп и Александреску, а Кормен сотоварищи :)

[EgAr]

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

[mikhanoid]

Хм. Странно… А что играло роль 'веса'?

[Krofes]

Большое спасибо!
С дискретной математикой и ТПР как-то не сложилось в университете, на парах было откровенно скучно.
Если бы лекции разбавляли такими замечательными примерами — было бы намного приятнее учиться.

[HammeremmaH]

Благодарю.
Как и предидущая Ваша статья про нахождение пути, эта — написана доступным языком. Действительно, не всегда сухие определения раскрывают суть и логику решения, а подкрепление доводов картинками — удачный ход.
Продолжайте. :)

[bethoven]

Хорошо расписано %) Интересует вариант когда (в ваших терминах) много задач (10-300) и мало разработчиков (3-10). К примеру есть 30 задач, необходимо их распределить на 5 разработчиков (в один момент времени разработчик выполняет одну задачу и задачи не могут быть прерваны). Известны сроки выполнения задач для каждого разработчика. Необходимо выполнить все задачи за минимально возможное время. $) Вот хотелось бы увидеть статью про алгоритмы для такого рода задач. $)

[Aquary]

Земляк, подумай о карьере преподавателя, в параллель к основной :) Доступно объяснять сложные вещи — этого сильно не хватает в преподавательской среде :)

[sova]

1.
vector maxrow, mincol;

//… чтение a…

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

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