Задача о соседях по комнате

В отличие от задачи о супружеских парах, задача о соседях по комнате может и не иметь, вообще говоря, решения. Например, пусть имеется четверо лиц — A, B, C и D, имеющих предпочтения:

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

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

Эффективный алгоритм решения предложен Ирвингом в 1985 году[1]. Алгоритм определяет, существует ли решение задачи и, если существует, находит его.

Алгоритм Ирвинга имеет сложность O(n²). Он определяет подходящие структуры данных для манипуляции со списками предпочтения и перестановками (смотрите ниже).

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

В противном случае переходим к этапу 2, на котором набор S последовательно изменяется с помощью так называемых перестановок. Пусть (p,q) принадлежит S, но (q,p) не принадлежит. Для каждого такого p определяем его текущего второго фаворита, являющегося следующим участником в списке предпочтений участника p после q, который может принять предложение p. Перестановка в S — это последовательность (p₀,q₀), (p₁,q₁),. . ., (p_k-1,q_k-1), такая, что (p_i,q_i) входит в S для любого i, и q_i+1 является вторым фаворитом участника p_i (здесь i + 1 берётся по модулю k). Если такая перестановка (p₀,q₀), . . . , (p_2k,q_2k) имеет нечетную длину, мы нашли так называемый нечетный набор, который показывает, что стабильного соответствия нет. В противном случае заменяем пары (p_i,q_i) на (p_i,q_i+1) (где i + 1 берётся по модулю k).

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

	S = output of Phase 1;
	while (true) {
	    identify a rotation r in S;
	    if (r is an odd party)
		return null; (there is no stable matching)
	    else
		apply r to S;
	    if (S is a matching)
		return S; (guaranteed to be stable)
	}

• Robert W. Irving, David F. Manlove. The Stable Roommates Problem with Ties // Journal of Algorithms. — 2002. — Т. 43, вып. 1. — С. 85—105. — doi:10.1006/jagm.2002.1219.