Проблема стабильного брака
В математике , экономике и информатике проблема стабильного брака (также проблема стабильного соответствия или SMP ) — это проблема поиска стабильного соответствия между двумя наборами элементов одинакового размера с заданным порядком предпочтений для каждого элемента. Сопоставление — это биекция элементов одного множества на элементы другого множества. Паросочетание неустойчиво , если:
Другими словами, сопоставление стабильно, если не существует совпадения ( A , B ), которое оба предпочитают друг друга своему текущему партнеру в рамках сопоставления.
Даны n мужчин и n женщин, где каждый человек расположил всех представителей противоположного пола в порядке предпочтения, женитесь на мужчинах и женщинах вместе так, чтобы не было двух людей противоположного пола, которые предпочли бы иметь друг друга, чем их нынешние партнеры. . При отсутствии таких пар людей множество браков считается устойчивым.
Существование двух классов, которые должны быть соединены друг с другом (гетеросексуальные мужчины и женщины в этом примере), отличает эту проблему от проблемы стабильных соседей по комнате .
Алгоритмы поиска решений проблемы стабильного брака находят применение в различных реальных ситуациях, возможно, наиболее известным из них является назначение выпускников-медиков на их первые приемы в больнице. [1] В 2012 году Нобелевская мемориальная премия по экономическим наукам была присуждена Ллойду С. Шепли и Элвину Э. Роту «за теорию стабильного распределения и практику проектирования рынка». [2]
Важным и масштабным применением стабильного брака является назначение пользователей серверам в крупной распределенной интернет-службе. [3] Миллиарды пользователей получают доступ к веб-страницам, видео и другим службам в Интернете, что требует, чтобы каждый пользователь был сопоставлен с одним из (потенциально) сотен тысяч серверов по всему миру, которые предлагают эту услугу. Пользователь предпочитает серверы, которые находятся достаточно близко, чтобы обеспечить более быстрое время отклика для запрошенной услуги, что приводит к (частичному) предпочтительному порядку серверов для каждого пользователя. Каждый сервер предпочитает обслуживать пользователей с меньшими затратами, что приводит к (частичному) предпочтительному упорядочению пользователей для каждого сервера. Сети доставки контентакоторые распространяют большую часть мирового контента и услуг, решают эту большую и сложную проблему стабильного брака между пользователями и серверами каждые десятки секунд, чтобы миллиарды пользователей могли сопоставляться с их соответствующими серверами, которые могут предоставить запрошенные веб-страницы, видео или другие Сервисы. [3]
