Комментарии 34
кекеке. чистейшая дискретная математика же.
у нас это называлось «олимпиадное программирование», и не было ни одного упоминания дискретной математики :)
А это и есть дискретка. А в случае венгерки — вообще теория принятия решений. Олимпиадное программирование — более общее понятие, туда можно и разбор грамматик, и вычислительную геометрию вместить. Так что то, что у вас не упоминали — не значит, что это не задача дискретной математики.
Стандартные паросочетания. Как к графам дискретки, так и к графам программирования (что одно и то же).
Вот ещё бы алгоритм определения мастества владения технологией…
Слегка напомнило транспортную задачу и методы её решения:)
Статья хорошая и нужная, а вот код по-моему недостаточно читабельный.
Как реализация годится, а как иллюстрация — нет.
Как реализация годится, а как иллюстрация — нет.
А код — я согласен не по мотивам «Стива МакКонела».
Но тем не менее… я взял листочек, взял этот код, нарисовал произвольную ситуацию — и, в принципе, он оцень неплохо описывает алгоритм… Аналоги (и мой же ACM ICPC'шный код который я помню наизусть) описывают его на 350 строк… Я так же не думал, что это может быть интересно… =) Ошибался…
Это же программирование… Be creative (ни против Вашего мнения, просто настроение такое) =))
Но тем не менее… я взял листочек, взял этот код, нарисовал произвольную ситуацию — и, в принципе, он оцень неплохо описывает алгоритм… Аналоги (и мой же ACM ICPC'шный код который я помню наизусть) описывают его на 350 строк… Я так же не думал, что это может быть интересно… =) Ошибался…
Это же программирование… Be creative (ни против Вашего мнения, просто настроение такое) =))
IMHO, было бы гораздо понятнее, если бы задача была сведена к простой абстрактной формулировке на графе, а потом был бы приведён алгоритм её решения с доказательством корректности. А то все эти пространные рассуждения ничего не дают, потому что разработчики и задачи автоматически не ассоциируются со структурами данных.
Честно. Я как минимум 2 недели думал над аналогией. =)
Прошу прощения, если не удачная получилась… Я старался…
Люблю когда Keep it simple. =) sorry, если не удалось — ставьте минус.
Прошу прощения, если не удачная получилась… Я старался…
Люблю когда Keep it simple. =) sorry, если не удалось — ставьте минус.
Не. Дело не в аналогии. Можно было бы просто написать: вот есть задача о назначении работников на работу. Вот её так-то формализуем. Получаем задачу о поиске паросочетания в двудольном графе. Решаем её так-то и так-то. Аналогии же и оперирование неабстрактными понятиями тут только затуманивают смысл алгоритма. Мне так кажется. Минусовать не буду, ибо алгоритмы — это хорошо.
Кстати. Было бы неплохо вместо 'альтернирующий' наприсать 'чередующийся', а вместо 'аугментальный' 'улучшающий'. Вроде как по смыслу и по лёгкости чтения эти варианты лучше.
если бы все это в онлайне было — цены бы не было: расписал возможности разработчиков и менеджеров, формально описал задачи. И все. Проект готов :)
Простите. Оченью люблю
В Вашем webo.in — очень нравится профессиональный подход!
=))) Да. Мои задачи — это «сферический конь в вакууме», но харбра-люди просили… Я знал этот алгоритм и не мог не поделиться… Я чувствовал ответственность (что пообещал) — вот и написал. На Ваше суждение. =))))
А оптимизатор web — имхо, очень интересно.
Хотелось бы быть in the edge of recently технологии =)
В Вашем webo.in — очень нравится профессиональный подход!
=))) Да. Мои задачи — это «сферический конь в вакууме», но харбра-люди просили… Я знал этот алгоритм и не мог не поделиться… Я чувствовал ответственность (что пообещал) — вот и написал. На Ваше суждение. =))))
А оптимизатор web — имхо, очень интересно.
Хотелось бы быть in the edge of recently технологии =)
Как мне говорил мой преподаватель по дискретке: «Посмотри на эти красивые и грамотные методы. Они настолько правильные, что никогда не будут применяться в жизни!»
А за толкование — спасибо. Однозначно в мемориз!
А за толкование — спасибо. Однозначно в мемориз!
помню готовился к экзамену по структурам и алгоритмам, разбирался с венгерским алгоритмом, и в этот момент (~4 часа ночи) захотелось придумать нечто другое своё… то что придумал записал в блокнотик, на всех тестовых наборах сработало, доказывать верность не стал :-)
Взрыв мозга. Но интересно, спасибо большое. Пригодится.
Благодарю!!!
Нечего больше сказать.
Единственное — я с ДВ нашей Родины. И мне пришлось изучать все это самому, начиная с «BFS» и вплоть до Венгерки. Имхо, это апофеоз разумных алгоритмов на графах, очень рад что Вы это знали!!! =)))
* мне во Владе понадобилось 2 года, чтобы с BFS «подняться» до Венгерки =)))
Нечего больше сказать.
Единственное — я с ДВ нашей Родины. И мне пришлось изучать все это самому, начиная с «BFS» и вплоть до Венгерки. Имхо, это апофеоз разумных алгоритмов на графах, очень рад что Вы это знали!!! =)))
* мне во Владе понадобилось 2 года, чтобы с BFS «подняться» до Венгерки =)))
Прошу прощения, я с Владивостока.
У нас 2:30. Очень спать хочется…
Потому — очепятки =) Благодарю за понимание…
У нас 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 но оно не объявленно в данном коде
…
в общем описание очень помогло а код немного недоделанный. хотя когда понимаешь идею — реализовать не так уж и сложно.
vector maxrow, mincol;
//… чтение a…
mincol.assign (n, 0);
minrow.assign (n, 0);
вместо minrow следует написать в данной задаче maxrow потому что minrow вообще не объявленное имя
2. используется INF но оно не объявленно в данном коде
…
в общем описание очень помогло а код немного недоделанный. хотя когда понимаешь идею — реализовать не так уж и сложно.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача о назначениях