Задача о назначениях. Венгерский алгоритм
ฝัง
- เผยแพร่เมื่อ 24 ส.ค. 2024
- На примере матрицы весов 4х4 показываем, как работает венгерский алгоритм. Строим двудольный граф, находим максимальное паросочетание, потом наибольшее, и в заключении - совершенное.
![[TH]FFWS SEA 2024 Fall - Knockout Stage Day 5](http://i.ytimg.com/vi/N2tl9xkQyyU/mqdefault.jpg)
вы чертовски приятный человек! К вам на пары можно ходить с удовольствием! Все понятно, ясно и интересно!
+виктор коледин Спасибо! Буду стараться не разочаровать...
Спасибо вам! Спасли перед контрольной! Здоровья и благополучия вам!
Спасибо! Получила удовольствие от Вашей лекции!
Спасибо Вам огромное за помощь! У меня все получилось!!! Вашим студентам очень повезло!))
Все просто. Максимум функции F есть минимум функции A-F. Т.е. делаете так - берете наибольшее число в матрице (или еще большее, с запасом) - это аналог А. Заменяете элементы Вашей матрицы b_ij на А-b_ij. Далее по уже известному пути - ищете минимум. Элементы, дающие минимум преобразованной матрицы соответствуют элементам исходной мтрицы, дающие максимум. Проверьте на матрице 2х2 - все станет ясно.
спасибо очень понятно объяснено!)
Это наиболее естественная ситуация. Значит выбрано удачное паросочетание. См. задачи с ответами на моем сайте vuz.exponenta.ru (раздел Архив задач) и мою книгу "Графы в Maple", она в сети где-то есть.
офигеть, такой ютубер некогда в моем МЭИ работал, неожиданно)
И продолжает работать еще...
Дядька очень старательно и детально объясняет, но че-то я тупой😕 завтра еще раз посмотрю
Да, это сразу не поймешь...
X(m) - множество вершин, не входящие в паросочетание. Множество X' - вершины в цепях из X(m) в X по тонким вперед, по толстым назад. X(m) обычно включено в X'. Иногда бывают длинные цепи, по несколько раз заходящие в Х.
Цепь x4--y1--x1--y3 есть чередующаяся, т.е. состоит из тонких вперед (из X в У) и толстых назад (из У в Х) и всего там нечетное число. Потом мы "обращаем" эту цепь и получаем все наоборот. Так собственно и надо - мы увеличили число "толстых" ребер.
Спасибо, очень доступно)
Ольга! Надо по тонким вперед, по толстым назад, а у1-х1 тонкое ребро
Супер! Спасибо.
Очень замудренный алгоритм
Здравствуйте! Поправьте если ошибаюсь. Но , насколько я помню, задача о назначениях частный случай транспортной сбалансированной задачи. Матрица назначений , насколько я помню, должна быть бинарная (0 или 1). Вы очень хорошо и понятно объясняете, спасибо Вам. Но , как по мне, так проще составить ЗЛП и решить ее при помощи Его Величества Экселя (попробовал для интереса и получил в результате Вами же полученную матрицу)). Удачи Вам в Вашем деле!
Матрица назначений, естественно, 0 или 1 (назначили или нет). А начальная матрица весов (оценок, затрат и проч) - любая. Спасибо за Эксель (Excel). Забыл про него
@@Kirsanov2011 , только не подумайте, что я с претензией или укором. Я нисколько не сомневаюсь в Вашем профессионализме. Просто я человек ленивый и иду по принципу: пусть машина считает она же железная))) Я в свое время транспортную задачу решал с помощью поиска решений Эксель, потому, что запутался в потенциалах в силу невнимательности. Преподаватель сказал: объяснишь как - зачту. Объяснил, что достаточно правильно составить ЗЛП и натравить на нее Эксель с его знаменитым симплекс-методом. Показал как составил. Зачел. Прошу не подумайте, что я Вас как-то укорял. Просто рассказал решение для лентяев, таких как я)))
Спасибо большое, что отвечаете на мои вопросы. Возник еще один. Может ли быть такое, что чередующуюся цепь нельзя создать так, чтобы увеличилось число толстых линий после обращения, т.е. в итоге пропускаем процесс обращения и переходим к созданию множеств?
очень познавательное видео и хотелось бы уточнить можно ли ее решать с помощью метода имитации отжига
Здравствуйте. У меня возник следующий вопрос: в данном примере можно было выбрать чередующуюся цепь х2-у1-х1-у3, но ее не выбрали. Значит ли это, что можно брать любую, если количество шагов одинаковое и нечетное?
С этим понятно. Скажите пожалуйста, а как составить мн-ва X' и Y', если Х(m) состоит из нескольких элементов?
а как быть если дана матрица эффективности и требуется назначать работников в соответствии с наибольшей эффективностью?
Если в множестве Х(m) больше одного элемента, как записывать мн-во Х'?
А для каких целей в процессе решения выделяется множество {Ym}, ведь оно нигде далее не используется... (Если я не ошибаюсь)
Можно и не выделять. Просто я следую традиции.
У меня одного этот алгоритм давали через дерево
А зачем нам множество Ym?
можно и не отмечать его.