WikiDer > Проблема стабильных соседей по комнате

Stable roommates problem

В математика, экономика и Информатика, особенно в области комбинаторика, теория игры и алгоритмы, то проблема соседа по конюшне (SRP) - это проблема поиска стабильное соответствие для набора ровного размера. А соответствие есть разделение множества на непересекающиеся пары («соседи по комнате»). Соответствие стабильный если нет двух элементов, которые не являются соседями по комнате и которые оба предпочитают друг друга своему соседу по комнате при сопоставлении. Это отличается от проблема стабильного брака в том, что проблема соседей по комнате в конюшне допускает совпадение между любыми двумя элементами, а не только между классами «мужчины» и «женщины».

Обычно это выражается как:

В данном случае проблемы соседей по комнате (SRP) каждый из 2n участники ранжируют остальных в строгом порядке предпочтения. Соответствие - это набор п непересекающиеся пары участников. Соответствие M в экземпляре SRP стабильно, если нет двух участников Икс и у, каждый из которых предпочитает другого партнеру в M. Такая пара называется блокирующей M, или быть блокирующей парой по отношению к M.

Решение

в отличие от проблема стабильного брака, стабильное соответствие может не существовать для определенных групп участников и их предпочтений. В качестве минимального примера стабильной пары, которая не существует, рассмотрим 4 человека. А, B, C, и D, чьи рейтинги:

A: (B, C, D), B: (C, A, D), C: (A, B, D), D: (A, B, C)

В этом рейтинге каждый из A, B и C является для кого-то наиболее предпочтительным человеком. В любом решении одно из A, B или C должен быть в паре с D и двумя другими друг с другом (например, AD и BC), но для любого, кто является партнером D, другой участник будет оценивать их наивысшую оценку, а партнер D, в свою очередь, предпочтет этого другого участника над D. В этом примере AC является более благоприятной парой, чем AD, но необходимая оставшаяся пара BD поднимает ту же проблему, иллюстрируя отсутствие стабильного соответствия для этих участников и их предпочтений.

Алгоритм

Эффективный алгоритм был приведен в (Ирвинг 1985).[1] Алгоритм определит для любого случая проблемы, существует ли устойчивое соответствие, и, если да, найдет такое соответствие. Алгоритм Ирвинга O (п2) сложностьпри условии, что подходящие структуры данных используются для выполнения необходимых манипуляций со списками предпочтений и идентификации поворотов.

Алгоритм состоит из двух этапов. На этапе 1 участники предлагать друг к другу, аналогично алгоритму Гейла-Шепли для проблема стабильного брака. Каждый участник упорядочивает других участников по своему предпочтению, в результате чего получается список предпочтений - упорядоченный набор других участников. Затем участники делают предложение каждому человеку в своем списке по порядку, переходя к следующему человеку, если и когда их текущее предложение отклоняется. Участник отклонит предложение, если он уже получил предложение от того, кого он предпочитает. Участник также отклонит ранее принятое предложение, если он позже получит предложение, которое он предпочитает. В этом случае отклоненный участник сделает предложение следующему человеку в своем списке, продолжая до тех пор, пока предложение не будет снова принято. Если какой-либо участник в конечном итоге отвергается всеми другими участниками, это означает, что стабильное сопоставление невозможно. В противном случае Фаза 1 закончится тем, что каждый человек получит предложение от одного из других.

Рассмотрим двух участников, q и п. Если q имеет предложение от п, затем удаляем из q's список всех участников Икс после п, и симметрично для каждого удаленного участника Икс, мы удаляем q из Икс's список, так что q первый в п'список s; и п, последний в q'с, так как q и любой Икс не могут быть партнерами ни в одном стабильном матче. Полученный сокращенный набор списков предпочтений вместе называется таблицей фазы 1. В этой таблице, если какой-либо сокращенный список пуст, то стабильного соответствия нет. В противном случае таблица Фазы 1 будет стабильный стол. Стабильная таблица, по определению, - это набор списков предпочтений из исходной таблицы после того, как члены были удалены из одного или нескольких списков и выполнены следующие три условия (где сокращенный список означает список в стабильной таблице):

(я) п первый на q'сокращенный список тогда и только тогда, когда q последний на п's
(ii) п не на q'сокращенный список тогда и только тогда, когда q не на п's тогда и только тогда, когда q предпочитает, чтобы последний человек в их списке п; или п, последний человек в списке, который q
(iii) ни один сокращенный список не пуст

У стабильных таблиц есть несколько важных свойств, которые используются для обоснования оставшейся части процедуры:

  1. Любая стабильная таблица должна быть подтаблицей таблицы Фазы 1, где подтаблица - это таблица, в которой списки предпочтений подтаблицы совпадают со списками надтаблицы, причем некоторые индивидуумы удалены из списков друг друга.
  2. В любой стабильной таблице, если каждый сокращенный список содержит точно один человек, а затем объединение каждого человека в пару с одним человеком из их списка дает стабильное соответствие.
  3. Если в экземпляре задачи о соседях по комнате стабильное соответствие, то это стабильное соответствие содержится в любой из стабильных таблиц.
  4. Любая стабильная подтаблица стабильной таблицы и, в частности, любая стабильная подтаблица, которая определяет стабильное сопоставление, как в 2, может быть получена последовательностью исключения вращения на стабильном столе.

Эти исключения вращения составляют фазу 2 алгоритма Ирвинга.

По 2, если каждый сокращенный список таблицы фазы 1 содержит ровно одного человека, то это дает соответствие.

В противном случае алгоритм переходит в Фазу 2. A вращение в стабильном столе Т определяется как последовательность (Икс0, у0), (Икс1, у1), ..., (Икск-1, ук-1) такой, что Икся различны, уя первый на Иксясокращенный список (или Икся последний на уясокращенный список) и уя + 1 второй на Иксясокращенный список для i = 0, ..., k-1, где индексы берутся по модулю k. Отсюда следует, что в любой стабильной таблице с сокращенным списком, содержащей не менее двух индивидов, такая ротация существует всегда. Чтобы его найти, начните с такого п0 содержащие не менее двух человек в их сокращенном списке, и рекурсивно определить qя + 1 быть вторым на пясписок и пя + 1 быть последним на qя + 1список, пока эта последовательность не повторится пj, в этот момент обнаруживается поворот: это последовательность пар, начинающаяся с первого появления (пj, qj) и заканчивая парой перед последним вхождением. Последовательность пя до пj называется хвост вращения. Тот факт, что это стабильная таблица, в которой выполняется этот поиск, гарантирует, что каждый пя в их списке есть как минимум два человека.

Чтобы исключить вращение, уя отвергает Икся так что Икся предлагает уя + 1, для каждого я. Чтобы восстановить свойства стабильной таблицы (i) и (ii), для каждого я, все преемники Икся-1 удалены из уясписок и уя удаляется из их списков. Если сокращенный список становится пустым во время этих удалений, то стабильного соответствия нет. В противном случае новая таблица снова является стабильной и либо уже определяет соответствие, поскольку каждый список содержит ровно одну личность, либо остается еще одно вращение для поиска и исключения, поэтому шаг повторяется.

Фазу 2 алгоритма можно резюмировать следующим образом:

Т = Фаза 1 Таблица;пока (истинный) {    идентифицировать а вращение р в Т;    Устранить р из Т;    если немного список в Т становится пустой,        возвращаться значение NULL; (нет стабильный соответствие может существовать)    еще если (каждый уменьшенный список в Т имеет размер 1)        возвращаться то соответствие M = {{Икс, у} | Икс и у находятся на каждый Другой's списки в Т}; (это является а стабильный соответствие)}

Чтобы достичь O (п2) время выполнения, матрица ранжирования, запись которой в строке я и столбец j позиция jй человек в ясписок th; это занимает O (п2) время. С помощью матрицы ранжирования проверка того, предпочитает ли человек одно другому, может выполняться в постоянное время путем сравнения их рангов в матрице. Кроме того, вместо явного удаления элементов из списков предпочтений сохраняются индексы первого, второго и последнего в сокращенном списке каждого человека. Первый человек, который бесподобный, т.е.имеет как минимум два в сокращенных списках, также сохраняется. Затем, на этапе 2, последовательность пя "пройденный" для поиска вращения сохраняется в списке, а массив используется для отметки людей как посещенных, как в стандартном поиск в глубину обход графа. После исключения вращения мы продолжаем сохранять только его хвост, если таковой имеется, в списке и в том виде, в каком он был посещен в массиве, и запускаем поиск следующего вращения с последней особи на хвосте, а в противном случае - со следующего несопоставленного особь, если нет хвоста. Это уменьшает повторное прохождение хвоста, поскольку на него в значительной степени не влияет исключение вращения.

пример

Ниже приведены списки предпочтений для экземпляра Stable Roommates с 6 участниками: 1, 2, 3, 4, 5, 6.

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

Возможное выполнение Этапа 1 состоит из следующей последовательности предложений и отклонений, где → представляет предлагает и × представляет отвергает.

1 → 3
2 → 6
3 → 2
4 → 5
5 → 3;   3 × 1
1 → 4
6 → 5;   5 × 6
6 → 1

Итак, Фаза 1 заканчивается следующими сокращенными списками предпочтений:

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

На этапе 2 вращение р1 = (1,4), (3,2) сначала идентифицируется. Это потому, что 2 является вторым фаворитом 1, а 4 - вторым фаворитом из 3. р1 дает:

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

Далее вращение р2 = (1,2), (2,6), (4,5) отождествляется, и его исключение дает:

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

Следовательно, 1 и 6 совпадают. Наконец, вращение р3 = (2,5), (3,4) отождествляется, и его исключение дает:

1 :   3   4   2   6   5
2 :   6   5   4   1   3
3 :   2   4   5   1   6
4 :   5   2   3   6   1
5 :   3   1   2   4   6
6 :   5   1   3   4   2

Следовательно, соответствие {{1, 6}, {2,4}, {3, 5}} стабильно.

Реализация в программных пакетах

  • Python: Реализация алгоритма Ирвинга доступна как часть соответствие библиотека.[2]
  • Ява: Модель программирования ограничений для поиска всех стабильных соответствий в проблеме соседей по комнате с неполными списками доступна по лицензии CRAPL.[3][4]
  • р: Та же самая модель программирования ограничений также доступна как часть R сопоставление рынков упаковка.[5][6]
  • API: MatchingTools API предоставляет бесплатный интерфейс прикладного программирования для алгоритма.[7]
  • Веб приложение: Веб-сайт "Dyad Finder" предоставляет бесплатную веб-реализацию алгоритма, включая исходный код для веб-сайта и решатель, написанный на JavaScript.[8]

Рекомендации

  1. ^ Ирвинг, Роберт В. (1985), "Эффективный алгоритм для решения проблемы" стабильных соседей по комнате "", Журнал алгоритмов, 6 (4): 577–595, Дои:10.1016/0196-6774(85)90033-1
  2. ^ Wilde, H .; Рыцарь, В .; Гиллард, Дж. (2020). «Matching: библиотека Python для решения игр на совпадение». Журнал открытого программного обеспечения. Дои:10.21105 / joss.02169.
  3. ^ Проссер, П. (2014). «Стабильные соседи по комнате и программирование ограничений» (PDF). Конспект лекций по информатике, издание CPAIOR 2014, Springer International Publishing. 8451: 15–28.
  4. ^ «Ограничение кодирования для проблемы соседей по квартире». Выпуск Java.
  5. ^ Кляйн, Т. (2015). «Анализ стабильных соответствий в R: Package MatchingMarkets» (PDF). Виньетка для R Package MatchingMarkets.
  6. ^ «MatchMarkets: Анализ стабильных совпадений». Проект R. 2019-02-04.
  7. ^ «MatchingTools API».
  8. ^ "Dyad Finder". dyad-finder.web.app. Получено 2020-05-06.
  9. ^ «Библиотека компонентов трекера». Репозиторий Matlab. Получено 5 января, 2019.

дальнейшее чтение