Венгерский алгоритм

Задачу о назначениях (5*5) решаем алгоритмом Куна (Harold W. Kuhn). По ходу решения строим двудольные графы, выполняем альфа- преобразование, ищем чередующиеся цепи.

[@НикитаЛыжников-з3р]

Спасибо за видео, очень простое и доходчивое объяснение.

[@NikIlvik]

Очень хорошо мужик объясняет, до меня сразу дошло, помогло разобраться))

[@ProDotaBass]

Спасибо вам, благодаря вам я сдал экзамен. Только у нас примеры были 7*7.

[@koshergamer9093]

Огромное спасибо, благодаря вам сдал курсач на 5

[@ЕгорМорозов-и9у]

просто "Царь объяснения!"

[@Kirsanov2011]

Егор Фёдоров Спасибо! Это я старался улучшить свою старую лекцию по этой теме: kzbin.info/www/bejne/iJ63lpareNahi5I

[@alword]

Kirsanov2011 у вас правда отлично получается! Хороший материал для повторения!

[@ZQutui]

Спасибо вам за данные алгоритмы,редко найдешь понятное обьяснение

[@ZQutui]

Данные имею ввиду что смотрел не только это видео от вас)

[@АлексейАнисимов-и5о]

Для такой задачи но с 5 станками 5 операциями 5 деталями писал программу 35 лет назад на планировании и организации производства. Проверка правильности решения для группы 30 человек 30 (на перфокартах)

[@RuVl_13]

Надо отметить, что тут еще очень качественно разбирается задача о максимальном паросочетании

[@УльянаБелкина-ю1ф]

Спасибо большое, очень понятно :)

[@penguin_of_linux3762]

У нас в шараге альфа-преобразование называют "операция Эгервари". Просто на заметку

[@vdozorov]

Сложность в целом не такая большая (для современных программ и для небольшой матрицы) перебором - количество перестановок = !n Но сравнивая с венгерским (n^3), мы получаем очень серьёзный выигрыш над перебором)

[@Federation1323]

Это бесподобно! Михаил Николаевич, а будет ли видео по доказательству венгерского алгоритма?

[@АндрійПерун-п1й]

А сколько таких операций будет обработано (то есть, как быстро мы дойдем до совершенного паросочетания) ?

[@TheNewWorld823]

Здравствуйте! Не подскажете, какой микрофон Вы используете?

[@Kirsanov2011]

Bluetooth

[@Ilichi]

Здравствуйте А что если нужно найти совершенное паросочетание в двудольном графе, в котором разное количество вершин в долях?

[@ilyazuyev5432]

Ни х...я не понял! Ну очень интересно!!

[@КонстантинЛемешев-з8д]

Очень интересно! Спасибо! "Наткнулся" на венгерский алгоритм, просматривая книгу 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) Поправка: Кун - из США.

[@Kirsanov2011]

Спасибо!

[@Tatiana-zs3dc]

а как искать двойственные переменные (цены)?

[@constantinekhvalin6038]

Небольшая поправка: Кун не был венгром, он был американцем.

[@Kirsanov2011]

Спасибо. Да, но фамилия венгерская

[@constantinekhvalin6038]

Спасибо за видео!

[@АлександрГартель]

Это алгоритм за O(n^4) или O(n^3)?

[@Kirsanov2011]

Не задумывался... Надо в литературе посмотреть...