Как стать автором
Обновить

Комментарии 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. Очень спать хочется…
Потому — очепятки =) Благодарю за понимание…
Мм, терминология какая-то непривычная. Обычно во всей литературе русскоязычной альтерирующая == чередующаяся. А так — классная статья, прочёл, освежил знания.
Спасибо (сорри, что отвтчаю пока на каждый коммент)!

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

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

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

//… чтение a…

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

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

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