РЕАЛИЗАЦИЯ ЭФФЕКТИВНОГО АЛГОРИТМА НАХОЖДЕНИЯ ВСЕХ УСТОЙЧИВЫХ ПАРОСОЧЕТАНИЙ И ИССЛЕДОВАНИЯ ПРЕДЕЛЬНОГО ЗАКОНА ДЛЯ ИХ КОЛИЧЕСТВА ПРИ СЛУЧАЙНЫХ МАТРИЦАХ ПРЕДПОЧТЕНИЙ
Введение 3
1. Определение устойчивого паросочетания и алгоритмы его поиска 5
1.1. Основные определения 5
1.2. Описание алгоритма поиска устойчивого паросочетания 7
1.3. Реализация основного алгоритма 8
2. Алгоритм поиска всех устойчивых паросочетаний Д.Кнута 11
2.1. Описание и реализация алгоритма 11
3. Алгоритм поиска всех устойчивых паросочетаний Д.Гасфилда 13
3.1. Операция Breakmarriage 13
3.2. Алгоритм нахождения всех устойчивых пар 16
3.3. Поиск всех устойчивых паросочетаний 20
4. Исследования алгоритмов поиска всех устойчивых
паросочетаний 27
4.1. Анализ эффективности алгоритмов 27
4.2. Модель распределения 31
Заключение 35
Список литературы 36
Приложение
Проблема устойчивого паросочетания заключается в поиске устойчивого соответствия между элементами двух множеств, имеющих свои предпочтения. Механизм решения этой задачи используется в реальной жизни для распределения студентов по университетам, интернов по больницам, сотрудников по стажировкам и донорских органов по нуждающимся в них людям.
Решение задачи было описано в 1962 году математиками Дэвидом Гейлом и Ллойдом Шепли в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly.
Позднее Д. Кнут описал алгоритм нахождения всех устойчивых паросочетаний в своих лекциях “Устойчивость супружеских пар и другие комбинаторные задачи”, который имеет сложность O(n3 S), где n - размерность задачи, S - кол-во устойчивых паросочетаний. В 1987 году Д. Гасфилдом в работе “ Three fast algorithms for four problems in stable marriage” (три быстрых алгоритма для решения четырёх проблем устойчивых паросочетаний) был описан более эффективный алгоритм поиска всех устойчивых паросочетаний сложностью О^+nS). Идея, ведущая к улучшению времени выполнения алгоритма, заключается в использовании теорем о структуре стабильных браков, чтобы избежать дублирования, присущего более раннему алгоритму Д.Кнута.
Целью работы является изучение возможных алгоритмов поиска всех устойчивых паросочетаний и поиск модели распределения количества паросочетаний.
Постановка задачи:
1. Изучение проблемы поиска всех устойчивых паросочетаний.
2. Реализация алгоритма Д. Кнута поиска всех устойчивых паросочетаний и его тестирование при случайных матрицах предпочтений различных размерностей.
3. Реализация более эффективного алгоритма Д.Гасфилда поиска всех устойчивых паросочетаний и проведение большого количества экспериментов для матриц предпочтений большой размерности.
4. Сравнение времени работы двух реализованных алгоритмов.
5. Поиск модели распределения количества паросочетаний при случайных матрицах предпочтений. Сравнение полученных результатов с теоретическими высказываниями относительно закона распределения.
В ходе данной работы были изучены и реализованы алгоритмы нахождения всех устойчивых паросочетаний сложностью O(n3S) - алгоритм Д.Кнута, и сложностью O(n2+nS) - алгоритм Д.Гасфилда для задач заданной размерности. Был проведён анализ эффективности работы программ реализующих алгоритмы поиска всех устойчивых паросочетаний, показавший, что алгоритмы были реализованы корректно. Были проведены 1000 экспериментов и изучено поведение данных в выборке. В результате исследования удалось опровергнуть гипотезу о логнормальности распределения данных. Также удалось выдвинуть гипотезу о распределении данных по закону Фреше, вероятность справедливости которой оказалась 0.22558 для выборки объема 1000 задачи размерности 200, что является довольно высоким показателем и дает основания полагать, что количества устойчивых паросочетаний при стремлении размерности задачи к бесконечности подчиняются закону распределения Фреше, что дает почву для дальнейшего исследования вопроса в виде математических теорем.
