Задача рассадки мальчиков и девочек по парам, где каждый хочет сидеть со знакомым, сводится к поиску наибольшего паросочетания в двудольном графе. В таком графе вершины делятся на два множества (мальчики и девочки), а ребра соединяют только вершины из разных множеств (знакомые пары).
Представленный алгоритм использует итеративный подход, начиная с любой непарной вершины. Если для вершины найдена пара, а партнер уже связан с другой вершиной, алгоритм пытается найти для нее альтернативного партнера через «цепную реакцию». Этот процесс поиска альтернативного партнера продолжается рекурсивно, пока не будет найдена свободная пара или не будет перебрано все доступные варианты. Алгоритм работает, пока не будут перебраны все вершины.
Ключевым моментом является использование массива
Алгоритм находит наибольшее паросочетание, но для строгого доказательства его правильности требуются более формальные методы, такие как математическая индукция. Алгоритмическая сложность данного решения O(NM), где N — число вершин, а M — число ребер в графе. Приведенный алгоритм часто называют алгоритмом Куна, а не «венгерским», как ошибочно указано в тексте. Венгерский алгоритм применяется для решения задачи о назначениях или поиска паросочетания минимальной стоимости.
Изображение носит иллюстративный характер
Представленный алгоритм использует итеративный подход, начиная с любой непарной вершины. Если для вершины найдена пара, а партнер уже связан с другой вершиной, алгоритм пытается найти для нее альтернативного партнера через «цепную реакцию». Этот процесс поиска альтернативного партнера продолжается рекурсивно, пока не будет найдена свободная пара или не будет перебрано все доступные варианты. Алгоритм работает, пока не будут перебраны все вершины.
Ключевым моментом является использование массива
match, чтобы фиксировать пары, и массива book, для отметки посещенных вершин в рамках текущей итерации. После успешного построения пары счетчик увеличивается на единицу. Эта итеративная процедура, по сути, находит так называемую удлиняющую цепочку. Алгоритм находит наибольшее паросочетание, но для строгого доказательства его правильности требуются более формальные методы, такие как математическая индукция. Алгоритмическая сложность данного решения O(NM), где N — число вершин, а M — число ребер в графе. Приведенный алгоритм часто называют алгоритмом Куна, а не «венгерским», как ошибочно указано в тексте. Венгерский алгоритм применяется для решения задачи о назначениях или поиска паросочетания минимальной стоимости.
