Comments 34
у нас это называлось «олимпиадное программирование», и не было ни одного упоминания дискретной математики :)
А это и есть дискретка. А в случае венгерки — вообще теория принятия решений. Олимпиадное программирование — более общее понятие, туда можно и разбор грамматик, и вычислительную геометрию вместить. Так что то, что у вас не упоминали — не значит, что это не задача дискретной математики.
Стандартные паросочетания. Как к графам дискретки, так и к графам программирования (что одно и то же).
Вот ещё бы алгоритм определения мастества владения технологией…
Да. Спасибо большое. Транспортную задачу я тоже попробовал описать =)
В моих блогах. Не даю ссылки, чтобы лишний раз не PR-иться… мне этого не надо. Просто be useful =)
Статья хорошая и нужная, а вот код по-моему недостаточно читабельный.
Как реализация годится, а как иллюстрация — нет.
А код — я согласен не по мотивам «Стива МакКонела».
Но тем не менее… я взял листочек, взял этот код, нарисовал произвольную ситуацию — и, в принципе, он оцень неплохо описывает алгоритм… Аналоги (и мой же ACM ICPC'шный код который я помню наизусть) описывают его на 350 строк… Я так же не думал, что это может быть интересно… =) Ошибался…

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

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

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

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

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

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

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

Не очень нужны эти «замутные» термины, но понимание как это далается — думаю пригодится! =) Мы Ведь Хабр! =))
А я не совсем программист. Спортивный программист — да, но я в нашей команде не кодер, а математик. Потому и книги настольные не Страуструп и Александреску, а Кормен сотоварищи :)
Спасибо. Вспомнил институтские занятия по параллельному программированию (в рамках курса вычислительных систем). Алгоритм применялся для распределения задачи состоящей из подзадач между узлами вычислительной системы.
UFO landed and left these words here
Большое спасибо!
С дискретной математикой и ТПР как-то не сложилось в университете, на парах было откровенно скучно.
Если бы лекции разбавляли такими замечательными примерами — было бы намного приятнее учиться.
Благодарю.
Как и предидущая Ваша статья про нахождение пути, эта — написана доступным языком. Действительно, не всегда сухие определения раскрывают суть и логику решения, а подкрепление доводов картинками — удачный ход.
Продолжайте. :)
Хорошо расписано %) Интересует вариант когда (в ваших терминах) много задач (10-300) и мало разработчиков (3-10). К примеру есть 30 задач, необходимо их распределить на 5 разработчиков (в один момент времени разработчик выполняет одну задачу и задачи не могут быть прерваны). Известны сроки выполнения задач для каждого разработчика. Необходимо выполнить все задачи за минимально возможное время. $) Вот хотелось бы увидеть статью про алгоритмы для такого рода задач. $)

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

//… чтение a…

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

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

в общем описание очень помогло а код немного недоделанный. хотя когда понимаешь идею — реализовать не так уж и сложно.
Only those users with full accounts are able to leave comments. Log in, please.