Помощь студентам в учебе
Исследование устойчивых паросочетаний на основе задачи о зачислении абитуриентов в вузы
|
ВВЕДЕНИЕ 7
1 УСТОЙЧИВЫЕ ПАРОСОЧЕТАНИЯ 9
1.1 История развития теории устойчивых паросочетаний 9
1.2 Применение устойчивых паросочетаний 12
1.2.1 Программа распределения студентов в терапевтической
интернатуре США 13
1.2.2 Процесс распределения учащихся по школам 15
1.2.3 Программа пересадки почек 17
1.2.4 Проблемы и трудности децентрализованных рынков 18
1.2.5 Программа распределения помощников федеральных судей 20
1.3 Основные определения теории устойчивых паросочетаний 21
1.3.1 Понятие устойчивого паросочетания 21
1.3.2 Пример профилей предпочтения и устойчивого паросочетания 24
1.4 Выводы по разделу 26
2 АЛГОРИТМЫ ПОСТРОЕНИЯ УСТОЙЧИВЫХ ПАРОСОЧЕТАНИЙ 27
2.1 Анализ существующих механизмов поступления абитуриентов в вузы . 27
2.1.1 Поступление абитуриентов в вузы Турции 28
2.1.2 Поступление абитуриентов в вузы Германии 29
2.1.3 Поступление абитуриентов в вузы России 30
2.2 Постановка задачи о зачислении абитуриентов в вузы 32
2.3 Многокритериальный серийный диктаторский механизм (MCSD) 34
2.4 Механизм отложенного принятия (Deferred Acceptance Algorithm) 36
2.4.1 Математическая модель механизма отложенного принятия 36
2.4.2 Пример работы алгоритма отложенного принятия 38
2.4.3 Теоремы теории устойчивых паросочетаний 39
2.5 Модификация механизма отложенного принятия для задачи «один-ко-
многим» 41
2.6 Алгоритм верхнего торгового цикла (Top Trading Cycle) 42
2.6.1 Математическая модель алгоритма верхнего торгового цикла 42
2.6.2 Пример работы алгоритма верхнего торгового цикла 43
2.7 Модификация механизма TTC для задачи «один-ко-многим» 44
2.8 Выводы по разделу 45
3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И СРАВНИТЕЛЬНЫЙ АНАЛИЗ 47
3.1 Сравнительный анализ механизмов по времени работы 47
3.2 Сравнительный анализ механизмов по стабильности найденного
решения 54
3.3 Демонстрация работы программы 55
3.4 Выводы по разделу 55
ЗАКЛЮЧЕНИЕ 56
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 58
ПРИЛОЖЕНИЕ 1 Код программы 61
1 УСТОЙЧИВЫЕ ПАРОСОЧЕТАНИЯ 9
1.1 История развития теории устойчивых паросочетаний 9
1.2 Применение устойчивых паросочетаний 12
1.2.1 Программа распределения студентов в терапевтической
интернатуре США 13
1.2.2 Процесс распределения учащихся по школам 15
1.2.3 Программа пересадки почек 17
1.2.4 Проблемы и трудности децентрализованных рынков 18
1.2.5 Программа распределения помощников федеральных судей 20
1.3 Основные определения теории устойчивых паросочетаний 21
1.3.1 Понятие устойчивого паросочетания 21
1.3.2 Пример профилей предпочтения и устойчивого паросочетания 24
1.4 Выводы по разделу 26
2 АЛГОРИТМЫ ПОСТРОЕНИЯ УСТОЙЧИВЫХ ПАРОСОЧЕТАНИЙ 27
2.1 Анализ существующих механизмов поступления абитуриентов в вузы . 27
2.1.1 Поступление абитуриентов в вузы Турции 28
2.1.2 Поступление абитуриентов в вузы Германии 29
2.1.3 Поступление абитуриентов в вузы России 30
2.2 Постановка задачи о зачислении абитуриентов в вузы 32
2.3 Многокритериальный серийный диктаторский механизм (MCSD) 34
2.4 Механизм отложенного принятия (Deferred Acceptance Algorithm) 36
2.4.1 Математическая модель механизма отложенного принятия 36
2.4.2 Пример работы алгоритма отложенного принятия 38
2.4.3 Теоремы теории устойчивых паросочетаний 39
2.5 Модификация механизма отложенного принятия для задачи «один-ко-
многим» 41
2.6 Алгоритм верхнего торгового цикла (Top Trading Cycle) 42
2.6.1 Математическая модель алгоритма верхнего торгового цикла 42
2.6.2 Пример работы алгоритма верхнего торгового цикла 43
2.7 Модификация механизма TTC для задачи «один-ко-многим» 44
2.8 Выводы по разделу 45
3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И СРАВНИТЕЛЬНЫЙ АНАЛИЗ 47
3.1 Сравнительный анализ механизмов по времени работы 47
3.2 Сравнительный анализ механизмов по стабильности найденного
решения 54
3.3 Демонстрация работы программы 55
3.4 Выводы по разделу 55
ЗАКЛЮЧЕНИЕ 56
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 58
ПРИЛОЖЕНИЕ 1 Код программы 61
За последние полвека было сформулировано множество интересных проблем, основной идеей которых является необходимость распределения людей или объектов в пары друг с другом. В качестве примера можно рассмотреть распределение интернов по больницам, распределение сотрудников по вакансиям, сопоставление пациента и донора, распределение учащихся по школам, распределение абитуриентов по вузам. Такая необходимость существовала и ранее, например, при составлении танцующих пар, при рассадке гостей за столом , однако механизмы автоматизации данного процесса стали появляться сравнительно недавно.
Для решения подобных задач стали использовать теорию графов. Действительно, составив по исходным данным двудольный граф, легко заметить, что задача сводится к известной задаче о поиске максимального паросочетания. Однако такой поиск не учитывает индивидуальные предпочтения каждого объекта относительно своей пары. Поэтому для решения данных задач было необходимо разработать алгоритм, который занимается распределением на основе упорядоченных предпочтений каждого объекта. Такие алгоритмы стали называть алгоритмами поиска устойчивых паросочетаний (Stable matching), которые учитывают пожелания каждого объекта и не могут быть улучшены относительно удовлетворения предпочтений.
Впоследствии возникла необходимость расширить данный подход с задач распределения вида «один-к-одному», как в случае с сотрудниками и вакансиями, так как на одну вакансию обычно претендует один сотрудник, на задачи распределения вида «один-ко-многим», как в случае с абитуриентами и вузами, так как в один вуз может поступить множество студентов, но каждый студент обучается не более чем в одном вузе. Задачи распределения такого типа встречаются сейчас очень часто в различных сферах и на различных рынках, поэтому разработка эффективных решений в этой области очень актуальна. Последние десятилетия ведутся активные исследования. Одними из новых разработок являются алгоритмы отложенного принятия решений DA (Deferred Acceptance) и алгоритм верхнего торгового цикла TTC (Top Trading Cycle).
Целью данной работы является исследование алгоритмов построения устойчивых паросочетаний вида «один-ко-многим» и сравнение их друг с другом по времени работы и эффективности распределения.
Для достижения поставленной цели необходимо решить следующие задачи:
- выполнить анализ предметной области;
- рассмотреть и модифицировать для задачи «один-ко-многим» эффективные алгоритмы поиска устойчивых паросочетаний, таких как алгоритм Гейла-Шепли, алгоритм DA, алгоритм ТТС, многокритериальный серийный диктаторский механизм ;
- реализовать алгоритмы на языке С++;
- протестировать алгоритмы на различных экспериментальных данных;
- проанализировать полученные результаты
Для решения подобных задач стали использовать теорию графов. Действительно, составив по исходным данным двудольный граф, легко заметить, что задача сводится к известной задаче о поиске максимального паросочетания. Однако такой поиск не учитывает индивидуальные предпочтения каждого объекта относительно своей пары. Поэтому для решения данных задач было необходимо разработать алгоритм, который занимается распределением на основе упорядоченных предпочтений каждого объекта. Такие алгоритмы стали называть алгоритмами поиска устойчивых паросочетаний (Stable matching), которые учитывают пожелания каждого объекта и не могут быть улучшены относительно удовлетворения предпочтений.
Впоследствии возникла необходимость расширить данный подход с задач распределения вида «один-к-одному», как в случае с сотрудниками и вакансиями, так как на одну вакансию обычно претендует один сотрудник, на задачи распределения вида «один-ко-многим», как в случае с абитуриентами и вузами, так как в один вуз может поступить множество студентов, но каждый студент обучается не более чем в одном вузе. Задачи распределения такого типа встречаются сейчас очень часто в различных сферах и на различных рынках, поэтому разработка эффективных решений в этой области очень актуальна. Последние десятилетия ведутся активные исследования. Одними из новых разработок являются алгоритмы отложенного принятия решений DA (Deferred Acceptance) и алгоритм верхнего торгового цикла TTC (Top Trading Cycle).
Целью данной работы является исследование алгоритмов построения устойчивых паросочетаний вида «один-ко-многим» и сравнение их друг с другом по времени работы и эффективности распределения.
Для достижения поставленной цели необходимо решить следующие задачи:
- выполнить анализ предметной области;
- рассмотреть и модифицировать для задачи «один-ко-многим» эффективные алгоритмы поиска устойчивых паросочетаний, таких как алгоритм Гейла-Шепли, алгоритм DA, алгоритм ТТС, многокритериальный серийный диктаторский механизм ;
- реализовать алгоритмы на языке С++;
- протестировать алгоритмы на различных экспериментальных данных;
- проанализировать полученные результаты
Данная работа посвящена исследованию устойчивых паросочетаний как способу эффективного распределения и сопоставления друг с другом агентов рынков с заданными предпочтениями.
В результате выполнения работы была осуществлена модификация существующих алгоритмов поиска устойчивых паросочетаний, таких как многокритериальный серийный диктаторский механизм, алгоритм отложенного принятия и алгоритм верхнего торгового цикла для задачи вида «один-ко- многим», проведен сравнительный анализ полученных модификаций по времени работы и осуществлена проверка найденных паросочетаний на устойчивость.
Для проведения сравнительного анализа модификации эффективных методов поиска устойчивых паросочетаний были реализованы на языке С++ в среде разработки Microsoft Visual Studio 2017. Для того чтобы измерить время работы методов, были зафиксированы такие параметры, как количество вузов и константа K, задающая количество заявлений, которые могут подать абитуриенты. Наибольшее количество вузов равно 1000, наибольшее значение константы K равно 5. Такие значения были взяты, чтобы максимально приблизить размеры сгенерированных данных к реальным данным приемной кампании в РФ. Для пяти комбинаций зафиксированных параметров было выбрано по 8 значений количества поступающих абитуриентов, для каждой зафиксированной тройки параметров количества абитуриентов, вузов и константы K было проведено по три теста времени и в качестве результата взято среднее арифметическое трех измерений.
Для проведения анализа полученных решений на устойчивость была реализована функция, принимающая построенное паросочетание и перебирающая все пары, состоящие из абитуриента и вуза, чтобы проверить, сколь - ко пар являются блокирующими.
В ходе сравнительного анализа был сделан вывод, что предложенные модификации выдают стабильные устойчивые решения, и время нахождения этих решений приемлемо для применения в процессах централизованного распределения агентов рынка. Алгоритмы серийного диктатора и отложенного принятия демонстрируют высокую эффективность по времени работы, в то же время алгоритм верхнего торгового цикла ощутимо уступает им по времени, но предлагает более удовлетворительные для агентов рынка решения из-за инновационного подхода. Данные выводы подтверждают теоретические оценки. Эти свойства модификаций алгоритмов поиска устойчивых паросочетаний делают возможным их применение на различных рынках, та - ких как приемные кампании в вузы, для устранения проблемы децентрализованных рынков и перехода к централизации.
Использование исследованных механизмов позволяет облегчить процесс распределения абитуриентов по вузам и повысить эффективность конечного распределения. В частности, это позволяет повысить проходной балл и средний уровень абитуриентов на некоторых факультетах.
В дальнейшем планируется исследовать данные механизмы на степень удовлетворенности агентов рынка полученным распределением и предложить наиболее эффективный механизм для использования в приемных кампаниях российских вузов.
В результате выполнения работы была осуществлена модификация существующих алгоритмов поиска устойчивых паросочетаний, таких как многокритериальный серийный диктаторский механизм, алгоритм отложенного принятия и алгоритм верхнего торгового цикла для задачи вида «один-ко- многим», проведен сравнительный анализ полученных модификаций по времени работы и осуществлена проверка найденных паросочетаний на устойчивость.
Для проведения сравнительного анализа модификации эффективных методов поиска устойчивых паросочетаний были реализованы на языке С++ в среде разработки Microsoft Visual Studio 2017. Для того чтобы измерить время работы методов, были зафиксированы такие параметры, как количество вузов и константа K, задающая количество заявлений, которые могут подать абитуриенты. Наибольшее количество вузов равно 1000, наибольшее значение константы K равно 5. Такие значения были взяты, чтобы максимально приблизить размеры сгенерированных данных к реальным данным приемной кампании в РФ. Для пяти комбинаций зафиксированных параметров было выбрано по 8 значений количества поступающих абитуриентов, для каждой зафиксированной тройки параметров количества абитуриентов, вузов и константы K было проведено по три теста времени и в качестве результата взято среднее арифметическое трех измерений.
Для проведения анализа полученных решений на устойчивость была реализована функция, принимающая построенное паросочетание и перебирающая все пары, состоящие из абитуриента и вуза, чтобы проверить, сколь - ко пар являются блокирующими.
В ходе сравнительного анализа был сделан вывод, что предложенные модификации выдают стабильные устойчивые решения, и время нахождения этих решений приемлемо для применения в процессах централизованного распределения агентов рынка. Алгоритмы серийного диктатора и отложенного принятия демонстрируют высокую эффективность по времени работы, в то же время алгоритм верхнего торгового цикла ощутимо уступает им по времени, но предлагает более удовлетворительные для агентов рынка решения из-за инновационного подхода. Данные выводы подтверждают теоретические оценки. Эти свойства модификаций алгоритмов поиска устойчивых паросочетаний делают возможным их применение на различных рынках, та - ких как приемные кампании в вузы, для устранения проблемы децентрализованных рынков и перехода к централизации.
Использование исследованных механизмов позволяет облегчить процесс распределения абитуриентов по вузам и повысить эффективность конечного распределения. В частности, это позволяет повысить проходной балл и средний уровень абитуриентов на некоторых факультетах.
В дальнейшем планируется исследовать данные механизмы на степень удовлетворенности агентов рынка полученным распределением и предложить наиболее эффективный механизм для использования в приемных кампаниях российских вузов.