Стабильная проблема с соседями по комнате

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

Обычно это формулируется как:

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

Решение

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

А:(Б,С,Г), Б:(С,А,Г), С:(А,В,Г), D:(А,В,С)

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

Алгоритм

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

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

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

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

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

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

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

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

В противном случае алгоритм переходит к этапу 2. Ротация в стабильной таблице T определяется как последовательность ( x ₀ , y ₀ ), ( x ₁ , y ₁ ), ..., ( x _k-1 , y _k-1 ) такие, что x _i различны, y _i находится первым в x _i сокращенном списке (или x _i является последним в y _i сокращенном списке ), а y _i+1 является вторым в x _i сокращенном списке , для i = 0,...,k-1, где индексы берутся по модулю k. Отсюда следует, что в любой стабильной таблице с сокращенным списком, содержащим хотя бы два человека, такая ротация всегда существует. Чтобы найти его, начните с такого p0 _, содержащего по крайней мере двух человек в их сокращенном списке, и рекурсивно определите q _i+1 как второй в p _i списке и p _i+1 как последний в q _{i+ 1} , пока эта последовательность не повторит некоторый p _j , после чего обнаруживается вращение: это последовательность пар, начинающаяся с первого вхождения ( p _j , q _j ) и заканчивающаяся парой перед последним вхождением. Последовательность pi _до p вращения _j называется хвостом . Тот факт, что это стабильная таблица, в которой происходит этот поиск, гарантирует, что . _{человека} в списке каждого pi есть как минимум два

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

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

T = Phase 1 table;while (true) {    identify a rotation r in T;    eliminate r from T;    if some list in T becomes empty,        return null; (no stable matching can exist)    else if (each reduced list in T has size 1)        return the matching M = {{x, y} | x and y are on each other's lists in T}; (this is a stable matching)}

Чтобы достичь O( n ² ) время выполнения, матрица ранжирования, запись которой в строке i и столбце j представляет собой позицию j -го человека в i -м списке; это занимает O( n ² ) время. С помощью матрицы ранжирования проверка того, предпочитает ли человек одного другому, может осуществляться за постоянное время путем сравнения их рангов в матрице. Более того, вместо явного удаления элементов из списков предпочтений сохраняются индексы первого, второго и последнего в сокращенном списке каждого отдельного человека. первый индивидуум, который не имеет себе равных Также сохраняется , т.е. имеет как минимум два человека в своих сокращенных списках. Затем, на этапе 2, последовательность pi _, «пройденная» для поиска вращения, сохраняется в списке, и массив используется для маркировки отдельных лиц как посещенных, как при стандартном поиска в глубину обходе графа . После исключения вращения продолжаем хранить только его хвост, если он есть, в списке и как посещенный в массиве, а поиск следующего вращения начинаем с последней особи на хвосте, а в противном случае — со следующей несовпавшейся особи. индивидуальный, если нет хвоста. Это уменьшает повторное прохождение хвоста, поскольку исключение вращения практически не влияет на него.

Пример

Ниже приведены списки предпочтений для экземпляра «Собители по комнате» с участием 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 заканчивается следующими сокращенными списками предпочтений: (например, мы вычеркиваем 5 вместо 1: потому что 1: получает как минимум 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

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

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

вращение r ₂ Далее идентифицируется = (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 совпадают. Наконец, вращение r ₃ = (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 : реализация алгоритма Ирвинга доступна как часть matching библиотека.
• Java : модель программирования с ограничениями для поиска всех устойчивых совпадений в задаче соседей по комнате с неполными списками доступна по лицензии CRAPL.
• R : та же модель программирования с ограничениями также доступна как часть R. matchingMarkets упаковка.
• API : API MatchingTools предоставляет бесплатный интерфейс прикладного программирования для алгоритма.
• Веб-приложение : веб-сайт «Dyad Finder» предоставляет бесплатную веб-реализацию алгоритма, включая исходный код для веб-сайта и решатель, написанный на JavaScript .
• Matlab : Алгоритм реализован в assignStableRoommates Функция, которая является частью Военно-морской исследовательской лаборатории США бесплатной библиотеки компонентов трекера .

Источники

• Ирвинг, Роберт В. (1985), «Эффективный алгоритм решения проблемы «стабильных соседей по комнате», Journal of Algorithms , 6 (4): 577–595, doi : 10.1016/0196-6774(85)90033-1

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

• Фляйнер, Тамаш; Ирвинг, Роберт В.; Мэнлав, Дэвид Ф. (2007), «Эффективный алгоритм решения проблемы «стабильных соседей по комнате», Theoretical Computer Science , 381 (1–3): 162–176, doi : 10.1016/j.tcs.2007.04.029
• Гасфилд, Дэниел М.; Ирвинг, Роберт В. (1989), Проблема стабильного брака: структура и алгоритмы , MIT Press.
• Ирвинг, Роберт В.; Мэнлав, Дэвид Ф. (2002), «Проблема стабильных соседей по комнате со связями» (PDF) , Journal of Algorithms , 43 (1): 85–105, CiteSeerX   10.1.1.108.7366 , doi : 10.1006/jagm.2002.1219