Задачу о назначениях (5*5) решаем алгоритмом Куна (Harold W. Kuhn). По ходу решения строим двудольные графы, выполняем альфа- преобразование, ищем чередующиеся цепи.
Пікірлер: 28
@user-ph8wd2cr5g3 жыл бұрын
Спасибо за видео, очень простое и доходчивое объяснение.
@ProDotaBass5 жыл бұрын
Спасибо вам, благодаря вам я сдал экзамен. Только у нас примеры были 7*7.
@NikIlvik6 жыл бұрын
Очень хорошо мужик объясняет, до меня сразу дошло, помогло разобраться))
@Federation13236 жыл бұрын
Это бесподобно! Михаил Николаевич, а будет ли видео по доказательству венгерского алгоритма?
@koshergamer9093 Жыл бұрын
Огромное спасибо, благодаря вам сдал курсач на 5
@user-hh2jr9me2r3 жыл бұрын
Для такой задачи но с 5 станками 5 операциями 5 деталями писал программу 35 лет назад на планировании и организации производства. Проверка правильности решения для группы 30 человек 30 (на перфокартах)
@user-mb6in6bk7c9 жыл бұрын
просто "Царь объяснения!"
@Kirsanov20119 жыл бұрын
Егор Фёдоров Спасибо! Это я старался улучшить свою старую лекцию по этой теме: kzbin.info/www/bejne/iJ63lpareNahi5I
@alword7 жыл бұрын
Kirsanov2011 у вас правда отлично получается! Хороший материал для повторения!
@Ilichi8 жыл бұрын
Здравствуйте А что если нужно найти совершенное паросочетание в двудольном графе, в котором разное количество вершин в долях?
@RuVl_1311 ай бұрын
Надо отметить, что тут еще очень качественно разбирается задача о максимальном паросочетании
@user-yc3cd4nk5z8 жыл бұрын
А сколько таких операций будет обработано (то есть, как быстро мы дойдем до совершенного паросочетания) ?
@ZQutui7 жыл бұрын
Спасибо вам за данные алгоритмы,редко найдешь понятное обьяснение
@ZQutui7 жыл бұрын
Данные имею ввиду что смотрел не только это видео от вас)
@user-if2cc5ed5i6 жыл бұрын
Спасибо большое, очень понятно :)
@penguin_of_linux37626 жыл бұрын
У нас в шараге альфа-преобразование называют "операция Эгервари". Просто на заметку
@Tatiana-zs3dc2 жыл бұрын
а как искать двойственные переменные (цены)?
@vdozorov Жыл бұрын
Сложность в целом не такая большая (для современных программ и для небольшой матрицы) перебором - количество перестановок = !n Но сравнивая с венгерским (n^3), мы получаем очень серьёзный выигрыш над перебором)
@TheNewWorld823 Жыл бұрын
Здравствуйте! Не подскажете, какой микрофон Вы используете?
@Kirsanov2011 Жыл бұрын
Bluetooth
@user-dx3nu4el5e7 жыл бұрын
Это алгоритм за O(n^4) или O(n^3)?
@Kirsanov20117 жыл бұрын
Не задумывался... Надо в литературе посмотреть...
@ilyazuyev54324 жыл бұрын
Ни х...я не понял! Ну очень интересно!!
@constantinekhvalin60385 жыл бұрын
Небольшая поправка: Кун не был венгром, он был американцем.
@Kirsanov20115 жыл бұрын
Спасибо. Да, но фамилия венгерская
@constantinekhvalin60385 жыл бұрын
Спасибо за видео!
@user-nf7et6xl4l6 жыл бұрын
Очень интересно! Спасибо! "Наткнулся" на венгерский алгоритм, просматривая книгу The Euclidean Matching Problem (books.google.ru/books?id=zgBSDQAAQBAJ&printsec=frontcover&dq=The+Euclidean+Matching+Problem&hl=ru&sa=X&redir_esc=y#v=onepage&q=The%20Euclidean%20Matching%20Problem&f=false) Поправка: Кун - из США.