Тема: РЕАЛИЗАЦИЯ ЭФФЕКТИВНОГО АЛГОРИТМА НАХОЖДЕНИЯ ВСЕХ УСТОЙЧИВЫХ ПАРОСОЧЕТАНИЙ И ИССЛЕДОВАНИЯ ПРЕДЕЛЬНОГО ЗАКОНА ДЛЯ ИХ КОЛИЧЕСТВА ПРИ СЛУЧАЙНЫХ МАТРИЦАХ ПРЕДПОЧТЕНИЙ

Проблема устойчивого паросочетания заключается в поиске устойчивого соответствия между элементами двух множеств, имеющих свои предпочтения. Механизм решения этой задачи используется в реальной жизни для распределения студентов по университетам, интернов по больницам, сотрудников по стажировкам и донорских органов по нуждающимся в них людям.
Решение задачи было описано в 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, что является довольно высоким показателем и дает основания полагать, что количества устойчивых паросочетаний при стремлении размерности задачи к бесконечности подчиняются закону распределения Фреше, что дает почву для дальнейшего исследования вопроса в виде математических теорем.

Купить