Известия РАН. Теория и системы управления, 2022, № 6, стр. 123-132

Введение. Рассматривается реляционная модель коллективного выбора, состоящая в отыскании результирующей ранжировки, в максимальной степени учитывающей индивидуальные предпочтения, которые могут быть описаны индивидуальными ранжировками.

Различные подходы к агрегированию индивидуальных предпочтений в рамках реляционной модели группового выбора описаны в многочисленных работах, начиная с основанных на классических идеях Ш. Борда и Н. Кондорсе, затем на концепции рационального коллективного выбора, реализованной в аксиоматическом подходе К. Эрроу, а также методах, использующих понятие близости бинарных отношений [1–5].

В работе для нахождения оптимальной агрегированной ранжировки предлагается применить метод ветвей и границ для построения медианы Кемени, являющейся наиболее близкой ко всем индивидуальным ранжировкам и тем самым отражающей консенсус между индивидуальными предпочтениями. Для нахождения медианы Кемени известны эвристические методы и точные методы дискретной оптимизации, разработанные, в частности, в [4, 6–8]. При этом точные переборные методы хорошо применимы в ограниченной постановке, а эвристические методы (например, алгоритм Кука–Сейфорда, медиана Литвака в пространстве векторов предпочтений) используют различные эвристики и способы определения ранга вариантов. Окончательное ранжирование может дать разные результаты в зависимости от выбора эвристического метода и, в частности, отличаться от результата точного метода.

Предлагаемый алгоритм значительно уменьшает перебор в этой экспоненциальной задаче, позволяет решать задачи большой размерности, что иллюстрируется приведенными результатами. Некоторые другие идеи метода, на котором основан этот алгоритм, можно найти в [9].

Для работы алгоритма не требуется специальных ограничений на исходные бинарные отношения, задающие индивидуальные предпочтения. Это могут быть не только линейные порядки или квазипорядки, но и произвольные бинарные отношения, заданные как совокупности упорядоченных пар. В данной работе авторы не рассматривают вопросы, связанные с интерпретацией и возможном практическом приложении подобных обобщений.

1. Рациональный коллективный выбор в реляционной модели агрегирования индивидуальных предпочтений. Проблема рационального коллективного выбора в рамках реляционной модели агрегирования индивидуальных предпочтений формулируется следующим образом, например в [4]. Группа из m лиц рассматривает несколько возможных вариантов (альтернатив) $A = \{ {{a}_{1}},...,{{a}_{n}}\} $ решения некоторой проблемы. Индивидуальные предпочтения членов группы выражаются ранжированиями, строгими или нестрогими, и задают профиль $\left\langle {{{\rho }_{1}},....,{{\rho }_{m}}} \right\rangle $ бинарных отношений на А.

Обозначим через LO [n] совокупность всех линейных порядков на А, т.е. бинарных отношений на А, являющихся одновременно рефлексивными, антисимметричными, транзитивными и линейными. Под строгим ранжированием понимается любое отношение из LO [n] , для нестрогого ранжирования необязательно условие антисимметричности. Расстояние между бинарными отношениями $\rho ,\rho {\kern 1pt} ' \subseteq A \times A$ с матрицами $R(\rho ) = {{\left\| {{{r}_{{ij}}}} \right\|}_{{n \times n}}}$, $R(\rho {\kern 1pt} ') = {\text{||}}r_{{ij}}^{'}{\text{|}}{{{\text{|}}}_{{n \times n}}}$, где ${{r}_{{ij}}}$, $r_{{ij}}^{'} \in \{ 0,{\text{1\} ,}}$ будем задавать метрикой Хемминга:

В качестве реляционного правила агрегирования предлагается выбрать медиану Кемени, т.е результирующую строгую ранжировку, “наиболее близкую” в смысле метрики Хемминга к индивидуальным ранжировкам. Таким образом, рассматриваемая задача сводится к нахождению линейной ранжировки $\hat {\rho } \in LO\,\,[n]$, минимизирующей функцию

т.е.

В общем случае такая ранжировка может оказаться неединственной и потребуется нахождение всего множества

2. Применение метода ветвей и границ для получения результирующей ранжировки. Опишем метод ветвей и границ и предложенный алгоритм для нахождения результирующей ранжировки (1.1). Целевой функцией является $D(\rho )$, и мы ищем либо любое $\hat {\rho },$ удовлетворяющее (1.1), либо все множество (1.2). При этом, как показано в [9], в случае $\left| {{\text{Arg}}\mathop {\min }\limits_{\rho \in LO[n]} D(\rho )} \right| > 1$ при наличии дополнительной информации можно выделить единственную ранжировку либо множественность решений указывает на эквивалентность некоторых групп вариантов.

Для дальнейшего понадобятся некоторые обозначения и утверждения. Пусть ${{R}^{t}}(\rho ) = {\text{||}}r_{{ij}}^{t}{\text{|}}{{{\text{|}}}_{{n \times n}}}$ – матрица бинарного отношения ${{\rho }_{t}}$, $t = \overline {1,m} $,

т.е. $p_{{ij}}^{{(1)}} = m - {{p}_{{ij}}}$, $p_{{ij}}^{*} = \min ({{p}_{{ij}}},p_{{ij}}^{{(1)}}),$ $i,j = \overline {1,n} $. Тогда, очевидно, что

Рассмотрим бинарное отношение $\tilde {\rho }$ с матрицей $R(\tilde {\rho }) = {{\left\| {{{{\tilde {r}}}_{{ij}}}} \right\|}_{{n \times n}}}$, построенное из ${{\rho }_{1}},{{\rho }_{2}},...,{{\rho }_{m}}$ по следующему правилу: ${{\tilde {r}}_{{ij}}} = 1 \Leftrightarrow {{p}_{{ij}}} \geqslant m{\text{/}}2$, $i,j = \overline {1,n} $. Тогда в силу (2.1)

Для доказательства (2.2) достаточно рассмотреть случаи:

а) ${{\tilde {r}}_{{ij}}} = 1$. Тогда ${{p}_{{ij}}} \geqslant m{\text{/}}2 \Rightarrow 2{{p}_{{ij}}} \geqslant m \Rightarrow $ ${{p}_{{ij}}} \geqslant m - {{p}_{{ij}}} = p_{{ij}}^{{(1)}}$, откуда, используя (2.1), получаем

б) ${{\tilde {r}}_{{ij}}} = 0$. Тогда ${{p}_{{ij}}} \leqslant m{\text{/}}2 \Rightarrow 2{{p}_{{ij}}} \leqslant m \Rightarrow $ ${{p}_{{ij}}} \leqslant m - {{p}_{{ij}}} = p_{{ij}}^{{(1)}}$, откуда, используя (2.1), получаем

Определим на множестве произвольных бинарных отношений $\rho $ на множестве $A$ с $R(\rho ) = {\text{||}}{{r}_{{ij}}}{\text{|}}{{{\text{|}}}_{{n \times n}}}$(т.е. при любом выборе ${{r}_{{ij}}} \in \{ 0,1\} $, $i,j = \overline {1,n} $) минимально возможное значение величины

В силу (2.2), это значение достигается при ${{r}_{{ij}}} = {{\tilde {r}}_{{ij}}}$_, $j = \overline {1,n} $. Обозначив минимально возможное значение величины ${{D}_{i}}(\rho )$ через α_i, получаем, что

При этом $D(\tilde {\rho })$ – минимально возможное значение величины $D(\rho )$ для всех бинарных отношений ρ на множестве $A$. Используя (2.2), имеем

Допустимыми решениями (последовательностями) являются последовательности альтернатив $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{n}}}}}} \right\rangle ,$ где $\{ {{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{n}}}}}\} = A$, т.е. перестановки множества A, каждая из которых соответствует некоторой ранжировке, т.е. линейному порядку вида ${{a}_{{{{i}_{1}}}}} \succ {{a}_{{{{i}_{2}}}}} \succ ... \succ {{a}_{{{{i}_{{n - 1}}}}}} \succ {{a}_{{{{i}_{n}}}}}$ (или, что то же самое, вида ${{a}_{{{{i}_{n}}}}} \prec {{a}_{{{{i}_{{n - 1}}}}}} \prec ... \prec {{a}_{{{{i}_{2}}}}} \prec {{a}_{{{{i}_{1}}}}}$) на A, где ${{a}_{{{{i}_{1}}}}}$(соответственно ${{a}_{{{{i}_{n}}}}}$) – наибольший (наименьший) элемент в этом линейном порядке. Множество возможных решений описывается n деревьями, каждое из которых имеет начальную вершину (1-го уровня), соответствующую некоторой альтернативе ${{a}_{{{{i}_{1}}}}}$, ${{i}_{1}} = 1,2,...,n$. Каждая вершина ${{a}_{{{{i}_{1}}}}}$ 1-го уровня соединяется ребрами со всеми вершинами ${{a}_{{{{i}_{2}}}}} \in A{{\backslash }}\{ {{a}_{{{{i}_{1}}}}}\} $ 2-го уровня. Каждая вершина ${{a}_{{{{i}_{2}}}}} \in A{{\backslash }}\{ {{a}_{{{{i}_{1}}}}}\} $ 2-го уровня соединяется ребрами со всеми вершинами из множества $A{{\backslash }}\{ {{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}}\} $ 3-го уровня и т.д., пока не дойдем до вершин последнего n-го уровня. Объединение этих деревьев дает лес Л допустимых решений. Единственная цепь, соединяющая в Л любую вершину ${{a}_{{{{i}_{n}}}}}$ n-го уровня с одной из вершин 1-го уровня, дает нам одно из допустимых решений $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{n}}}}}} \right\rangle ,$ где ${{a}_{{{{i}_{1}}}}}$ – вершина 1-го уровня, а ${{a}_{{{{i}_{n}}}}}$ – вершина n-го уровня. Кроме того, каждой промежуточной вершине ${{a}_{{{{i}_{k}}}}}$ $k$-го уровня, где $k = \overline {2,n - 1} $, аналогичным образом ставим в соответствие последовательность $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}} \right\rangle ,$ однозначно определяемую единственной цепью, соединяющей ${{a}_{{{{i}_{k}}}}}$с некоторой (единственной) вершиной ${{a}_{{{{i}_{1}}}}}$ 1-го уровня. Такие последовательности также будем называть допустимыми. Тем самым каждая вершина ${{a}_{{{{i}_{k}}}}}$ k-го уровня, где $k = \overline {1,n - 1} $, определяет множество допустимых решений, а именно последовательностей вида

продолжающих (т.е. с одинаковой первой частью последовательности длины $k$) допустимую последовательность $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}} \right\rangle $. Воспользуемся величинами ${{\alpha }_{i}}$ для получения нижних оценок для $D(\rho )$ на множествах допустимых решений, соответствующих каждой промежуточной вершине в Л. Очевидно, что величина является нижней оценкой для множества всех допустимых решений. Приведем теперь нижние оценки величины $D(\rho )$ для вершин 1-го уровня. Нижние оценки будут уточняться по мере увеличения номера уровня вершин. Каждая вершина a_i 1-го уровня соответствует выбору альтернативы a_i в качестве наибольшего элемента. Это полностью определяет величину для всех линейных порядков $\rho $ на A с наибольшим элементом a_i, которую обозначим через ${{\beta }_{i}}$, поскольку в силу такого выбора для $R(\rho ) = {\text{||}}{{r}_{{ij}}}{\text{|}}{{{\text{|}}}_{{n \times n}}}$ выполняется ${{r}_{{ii}}} = 1$, ${{r}_{{ij}}} = 0$ при $i \ne j$. Следовательно, используя (2.1), получаем

Но тогда можно уточнить нижние оценки величины $D(\rho )$ для допустимых решений, соответствующих выбору a_i в качестве вершины 1-го уровня, т.е. решений, соответствующих дереву с начальной вершиной a_i. Это будет величина

(т.е. в качестве нижней оценки для взяли сумму точного значения величины ${{\beta }_{i}} = {{D}_{i}}(\rho )$ для всех решений, соответствующих этому дереву, и сумму нижних оценок α_j  для остальных ${{D}_{j}}(\rho )$).

Заметим далее, что выбор некоторой альтернативы a_i в качестве вершины последнего $n$-го уровня соответствует выбору альтернативы a_i в качестве наименьшего элемента, а это полностью определяет величину

для всех линейных порядков ρ на $A$ с наименьшим элементом a_i, которую обозначим через ${{\gamma }_{i}}$, поскольку в силу такого выбора для $R(\rho ) = {\text{||}}{{r}_{{ij}}}{\text{|}}{{{\text{|}}}_{{n \times n}}}$ выполняется ${{r}_{{ij}}} = 1,$ $j = \overline {1,n} $. Тогда, используя (2.1), получаем

Обозначим ${{\eta }_{i}} = {{\gamma }_{i}} - {{\alpha }_{i}}$, $i = \overline {1,n} .$ Учитывая то, что в любом из допустимых решений какая-нибудь из альтернатив a_j  является наименьшим элементом, а следовательно, даст вклад в $D(\rho )$, равный ${{D}_{j}}(\rho ) = {{\gamma }_{j}} = {{\alpha }_{j}} + {{\eta }_{j}}$, получаем еще одно уточнение для нижней оценки величины $D(\rho )$ для допустимых решений, соответствующих выбору a_i в качестве вершины 1-го уровня, т.е. решений, соответствующих дереву с начальной вершиной a_i. Это будет величина, которую обозначаем через ${{\nu }_{i}}$ и определяем по формуле

Аналогично находятся нижние оценки и для каждой промежуточной вершины ${{a}_{{{{i}_{k}}}}}$ k-го уровня, где $k = \overline {2,n - 1} $, которая, как отмечалось выше, задает некоторое множество допустимых решений. Ранее этой вершине была поставлена в соответствие допустимая последовательность $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}} \right\rangle ,$ однозначно определяемая единственной цепью, соединяющей ${{a}_{{{{i}_{k}}}}}$ с некоторой (единственной) вершиной ${{a}_{{{{i}_{1}}}}}$ 1-го уровня. Поставим теперь этой последовательности в соответствие длину ${{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}}$, равную ее вкладу в $D(\rho )$ для всех допустимых решений $\rho $, продолжающих ее, т.е.

которую удобно определять по мере увеличения уровня $k$, согласно рекуррентному соотношению где начальная величина ${{\beta }_{{{{i}_{1}}}}}$ была определена ранее. Для организации вычислительного процесса последовательного определения этих величин остается уточнить порядок вычисления величины

Любое допустимое решение $\rho $, продолжающее допустимую последовательность $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}} \right\rangle $, имеет вид $\left\langle {{{a}_{{{{i}_{1}}}}},,...,{{a}_{{{{i}_{k}}}}},{{a}_{{{{i}_{{k + 1}}}}}},...,{{a}_{{{{i}_{n}}}}}} \right\rangle $, где ${{a}_{{{{i}_{n}}}}} \prec ... \prec {{a}_{{{{i}_{{k + 1}}}}}} \prec {{a}_{{{{i}_{k}}}}} \prec ... \prec {{a}_{{{{i}_{1}}}}}$. Следовательно, для $R(\rho ) = {\text{||}}{{r}_{{ij}}}{\text{|}}{{{\text{|}}}_{{n \times n}}}$ справедливы равенства

дающие возможность однозначно определить значение ${{D}_{{{{i}_{k}}}}}(\rho )$ для указанных допустимых решений $\rho $. Такая однозначность позволяет обозначить величину ${{D}_{{{{i}_{k}}}}}(\rho )$ для любого допустимого решения $\rho $, продолжающего допустимую последовательность $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}} \right\rangle $, иначе (без указания бинарного отношения $\rho $, используемого в ней) ${{D}_{{{{i}_{k}}}}}(\rho ) = {{D}_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}}$. Тогда равенство (2.4) можно переписать в виде (исключаем вхождение неопределенного параметра $\rho $)

По аналогии с формулой (2.3), приведенной ранее для величины ${{\nu }_{i}}$, соответствующей вершине a_i 1-го уровня, приведем теперь формулу для величины ${{\nu }_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}}$, соответствующей промежуточной вершине ${{a}_{{{{i}_{k}}}}}$, принадлежащей k-му уровню, где $k = \overline {2,n - 1} $. Эта формула является нижней оценкой для $D(\rho )$ на множестве всех допустимых решений $\rho $, продолжающих допустимую последовательность $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}} \right\rangle $, однозначно определяемую вершиной ${{a}_{{{{i}_{k}}}}}$:

Приведем, кроме того, некоторые формулы для вычисления величины ${{D}_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}}$, основанные на равенствах (2.5). Например, из (2.5) следует, что число ${{D}_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}}$ равно сумме расстояний от i_k-х строк матриц ${{R}^{t}} = R({{\rho }_{t}}) = {\text{||}}r_{{ij}}^{t}{\text{|}}{{{\text{|}}}_{{n \times n}}}$, $t = \overline {1,m} $, до вектор-строки $({{r}_{1}},...,{{r}_{n}})$, где

Кроме того, для большей простоты вычислений можно также воспользоваться матрицами P, P⁽¹⁾, а также равенствами (2.1):

поскольку в силу (2.5)

Отметим при этом, что

где ρ – линейный порядок, соответствующий допустимой последовательности $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{n}}}}}} \right\rangle $.

Замечание 1. Из формулы (2.6) следует, что при $k = \overline {3,n} $ в случае $\{ {{a}_{{i_{1}^{'}}}},{{a}_{{i_{2}^{'}}}},...,{{a}_{{i_{{k - 1}}^{'}}}}\} = \{ {{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{{k - 1}}}}}}\} $ (т.е. при $\{ {{i}_{1}},...,{{i}_{{k - 1}}}\} = \{ i_{1}^{'},...,i_{{k - 1}}^{'}\} $) выполняется ${{D}_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}} = {{D}_{{i_{1}^{'}i_{2}^{'} \cdots i_{{k - 1{{i}_{k}}}}^{'}}}}$, что дает экономию в общем объеме вычислений. Например, ${{D}_{{2,1,3}}} = {{D}_{{1,2,3}}}$, ${{D}_{{2,1,4}}} = {{D}_{{1,2,4}}}$, ${{D}_{{3,1,4}}} = {{D}_{{1,3,4}}}$, ${{D}_{{3,2,4}}} = {{D}_{{2,3,4}}}$. Учитывая этот факт, можно сократить количество вычисляемых величин ${{D}_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}}$ в $(k - 1)!$ раз.

Описанный лес допустимых решений Л дает схему ветвления для поставленной задачи. Заметим, что при достаточно большом n количество вершин в Л может оказаться чрезмерно большим (например, в Л имеется $n!$ вершин одного только n-го уровня). В связи с этим будем при обходе вершин из Л использовать так называемое правило отсечения, позволяющее отсекать в Л вершины вместе с цепями, соединяющими эти вершины с вершинами n-го уровня. Чтобы сформулировать это правило, понадобится величина $\tilde {D}$, которую будем называть рекордом. Текущее значение этой величины определяется при первом достижении любой вершины n-го уровня и уточняется при каждом прохождении любой другой вершины n-го уровня. В процессе обхода вершин из Л будем для каждой текущей вершины ${{a}_{{{{i}_{k}}}}}$, принадлежащей k-му уровню, $1 \leqslant k \leqslant n$, где $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}} \right\rangle $ – допустимая последовательность, находить величины ${{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}},{{\nu }_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}}$ . Тогда при k = n величина ${{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}} = {{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{n}}}}}$ дает точное значение величины $D(\rho )$ для линейного порядка $\rho $, определяемого последовательностью $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{n}}}}}} \right\rangle $. При каждом прохождении вершины n-го уровня уточним значение $\tilde {D}$ так, чтобы оно равнялось минимальному значению среди всех вычисленных на данном этапе величин вида ${{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{n}}}}}$. В этом случае для любой вершины ${{a}_{{{{i}_{k}}}}}$, принадлежащей $k$-му уровню, где $1 \leqslant k \leqslant n - 2$, в случае выполнения неравенства

вершина ${{a}_{{{{i}_{k}}}}}$ может быть исключена из Л вместе с цепями, соединяющими эту вершину с вершинами n-го уровня. При выполнении этого условия все линейные порядки $\rho $, которые соответствуют допустимым решениям, продолжающим последовательность $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}} \right\rangle ,$ имеют значение $D(\rho )$, превышающее $\tilde {D}$, а следовательно, не могут принадлежать ${\text{Arg}}\mathop {\min }\limits_{\rho \in LO[n]} D(\rho )$. В случае, если ищем хотя бы одно решение из ${\text{Arg}}\mathop {\min }\limits_{\rho \in LO[n]} D(\rho )$, условие отсечения (2.8) можно заменить на более слабое ${{\nu }_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}} \geqslant $ $\tilde {D}$. При выполнении этого условия все линейные порядки, которые соответствуют допустимым последовательностям, продолжающим $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}} \right\rangle $, не дадут улучшения рекорда $\tilde {D}$.

Замечание 2. В силу (2.7) для любой вершины (n – 1)-го уровня, соответствующей допустимой последовательности $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{{n - 1}}}}}}} \right\rangle $, выполняется равенство ${{\nu }_{{{{i}_{1}}{{i}_{2}}...{{i}_{{n - 1}}}}}} = {{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{{n - 1}}}}}} + {{\alpha }_{{{{i}_{n}}}}} + {{\eta }_{{{{i}_{n}}}}} = $ ${{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{{n - 1}}}}}} + {{\gamma }_{{{{i}_{n}}}}}$ = = ${{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{{n - 1}}}}}} + {{D}_{{{{i}_{1}}{{i}_{2}}...{{i}_{n}}}}}$ = ${{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{n}}}}}$, где $\{ {{i}_{n}}\} = \{ 1,2,...,n\} {{\backslash }}\{ {{i}_{1}},...,{{i}_{{n - 1}}}\} $. Другими словами, ${{\nu }_{{{{i}_{1}}{{i}_{2}}...{{i}_{{n - 1}}}}}} = {{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{n}}}}}$ = D(ρ), где $\rho $ – линейный порядок, соответствующий допустимой последовательности $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{n}}}}}} \right\rangle $. Отсюда следует, что уточнение рекорда можно производить уже при достижении любой вершины (n – 1)-го уровня. Допустимая последовательность $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{{n - 1}}}}}}} \right\rangle $, соответствующая этой вершине, однозначно определяет допустимую последовательность $\left\langle {{{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{n}}}}}} \right\rangle $, и при этом ${{\nu }_{{{{i}_{1}}{{i}_{2}}...{{i}_{{n - 1}}}}}} = {{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{n}}}}}.$ Таким образом, переход от вершин (n – 1)-го уровня к вершинам n-го уровня является излишним.

Опишем теперь порядок прохождения вершин в Л. В [10] описаны три возможных способа продолжения ветвления. Применим к решению нашей задачи следующий способ. При выборе вершины для очередного ветвления (т.е. для прохождения продолжающих эту вершину цепей леса Л) берется не исключенная вершина ${{a}_{{{{i}_{k}}}}}$ максимального уровня k, где $1 \leqslant k \leqslant n - 2$, из множества всех достигнутых к этому моменту вершин леса Л и имеющая минимальное значение ${{\nu }_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}}$ среди всех вершин этого уровня. Выбор вершины ${{a}_{{{{i}_{k}}}}}$ k-го уровня однозначно определяет множество вершин $A{{\backslash }}\{ {{a}_{{{{i}_{1}}}}},{{a}_{{{{i}_{2}}}}},...,{{a}_{{{{i}_{k}}}}}\} $ $(k + 1)$-го уровня. Если таких вершин несколько, то выбираем среди них вершину с минимальным значением ${{\beta }_{{{{i}_{1}}{{i}_{2}}...{{i}_{k}}}}},$ а если и таковых несколько, то – с наименьшим номером i_k.

3. Ускорение метода. Построим по матрице $P = {{R}^{1}} + ... + {{R}^{m}} = {\text{||}}{{p}_{{ij}}}{\text{|}}{{{\text{|}}}_{{n \times n}}}$ матрицу $\tilde {R} = {\text{||}}{{\tilde {r}}_{{ij}}}{\text{|}}{{{\text{|}}}_{{n \times n}}}$, где ${{\tilde {r}}_{{ii}}} = 1$, $i = \overline {1,n} $, а в случае $i \ne j$ выполняется: ${{\tilde {r}}_{{ij}}} = 1$, если ${{p}_{{ij}}} > {{p}_{{ji}}}$, ${{\tilde {r}}_{{ij}}} = 0$, если ${{p}_{{ij}}} < {{p}_{{ji}}}$, и ${{\tilde {r}}_{{ij}}} = 1{\text{/}}2$, если ${{p}_{{ij}}} = {{p}_{{ji}}}$. Рассмотрим для каждой альтернативы ${{a}_{i}} \in A$ величину

Нетрудно показать (см., например, [1]), что если числа ${{\kappa }_{i}}$, $i = \overline {1,n} $, можно линейно упорядочить таким образом, что ${{\kappa }_{{{{i}_{1}}}}} = 1,{{\kappa }_{{{{i}_{2}}}}} = 2,...,{{\kappa }_{{{{i}_{n}}}}} = n$, то ${\text{Arg}}\mathop {\min }\limits_{\rho \subseteq A \times A} D(\rho )$ (здесь минимум берется на множестве всех бинарных отношений на A) состоит из единственного бинарного отношения, являющегося линейным порядком, и в этом случае ${\text{Arg}}\mathop {\min }\limits_{\rho \subseteq A \times A} D(\rho )$ = ${\text{Arg}}\mathop {\min }\limits_{\rho \in LO[n]} D(\rho )$. Понятно, что такой случай является очень редким, но всегда по числам ${{\kappa }_{1}},...,{{\kappa }_{n}}$ может быть построен квазипорядок $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\rho } $ на $A$: $\left\langle {{{a}_{i}},{{a}_{j}}} \right\rangle \in \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\rho } \Leftrightarrow {{\kappa }_{i}} \leqslant {{\kappa }_{j}}$. Указанный квазипорядок определяет множество всех линейных порядков $\lambda \in LO\,\,[n]$, согласованных с $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\rho } $, т.е. удовлетворяющих условию $\langle {{a}_{i}},{{a}_{j}}\rangle \, \in \,\lambda \, \Rightarrow \,\langle {{a}_{i}},{{a}_{j}}\rangle \, \in \,\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\rho } $. Выделив все согласованные $\lambda \in LO\,\,[n]$, можно перед началом работы метода ветвей и границ предварительно посчитать значение $D(\lambda )$ для выделенных таким образом $\lambda \in LO\,\,[n]$ и получить некоторое предварительное используемое в алгоритме значение рекорда $\tilde {D}$. Тогда применение этого значения в самом начале работы алгоритма (в случае его близости к $D_{{\min }}^{{LO}} = \min \{ D(\rho )\,{\text{|}}\,\rho \in LO\,\,[n]\} $) может увеличить число отсечений и тем самым сократить время работы алгоритма. В тех случаях, когда найдутся $\lambda \in {\text{Arg}}\mathop {\min }\limits_{\rho \in LO[n]} D(\rho )$, согласованные с $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\rho } $, в результате совершения описанных предварительных вычислений будет уже в самом начале работы алгоритма выполняться $\tilde {D} = D_{{\min }}^{{LO}}$, что может привести к значительному уменьшению времени работы алгоритма.

4. Случай, когда каждой индивидуальной ранжировке приписывается некоторый вес. Описанный метод построения агрегированной ранжировки легко переносится на случай, когда каждой индивидуальной ранжировке приписывается некоторый вес, отражающий ее относительную важность. Тогда вместо целевой функции $D(\rho )$ используется функция более общего вида:

т.е. учитывается относительная важность бинарных отношений ${{\rho }_{1}},{{\rho }_{2}},...,{{\rho }_{m}}$. При этом вместо матриц $P$, ${{P}^{{(1)}}}$, $P{\kern 1pt} *$ соответственно используем матрицы ${{\tilde {P}}^{{(1)}}} = {\text{||}}\tilde {p}_{{ij}}^{{(1)}}{\text{|}}{{{\text{|}}}_{{n \times n}}} = {\text{||}}m - {{\tilde {p}}_{{ij}}}{\text{|}}{{{\text{|}}}_{{n \times n}}}$, $\tilde {P}{\kern 1pt} * = {\text{||}}\tilde {p}_{{ij}}^{*}{\text{|}}{{{\text{|}}}_{{n \times n}}} = {\text{||}}\min \{ {{\tilde {p}}_{{ij}}},\tilde {p}_{{ij}}^{{(1)}}\} {\text{|}}{{{\text{|}}}_{{n \times n}}}$. После такой замены описанный выше метод ветвей и границ переносится на этот случай практически без изменений. Бинарное отношение $\tilde {\rho }$, с матрицей $R(\tilde {\rho }) = {\text{||}}{{\tilde {r}}_{{ij}}}{\text{|}}{{{\text{|}}}_{{n \times n}}}$, ${{\tilde {r}}_{{ij}}} \in \{ 0,{\text{1\} }}$, строится, исходя из ${{\rho }_{1}},{{\rho }_{2}},...,{{\rho }_{m}}$, по правилу: ${{\tilde {r}}_{{ij}}} = 1 \Leftrightarrow {{\tilde {p}}_{{ij}}} \geqslant m{\text{/}}2$, $i,j = \overline {1,n} $. Аналогично (2.2) выполняются равенства а все последующие рассуждения основываются только на этих равенствах.

5. Пример. Приведем примеры работы описанного алгоритма.

Группа из m = 9 лиц строго ранжирует варианты из $A = \{ {{a}_{1}},...,{{a}_{n}}\} $, где $n = 20$. Для простоты заменим обозначение варианта a_i числом i, т.е. $A = \{ 1,2...,20\} $. Пусть индивидуальные ранжировки имеют следующий вид:

В результате произведенных вычислений было выделено множество ${\text{Arg}}\mathop {\min }\limits_{\rho \in LO[n]} D(\rho ),$ состоящее из единственной ранжировки

В случае простого перебора пришлось бы перебрать 20! = 1.28047…$ \times {{10}^{{17}}}$ вариантов, т.е. крайне большое число. В результате применения описанного метода вычисления на компьютере Asus N73S (4-ядерный процессор Intel Core i7-2630QM, 2 ГГц) заняли 49 с. Программа написана на языке Python 3.8.3.

Были также подсчитаны значения D_min = $D(\tilde {\rho }) = \min \{ D(\rho )|\rho \subseteq A \times A\} $ = 1074, $D_{{\min }}^{{LO}}\, = \,\min \{ D(\rho )\,{\text{|}}\,\rho \, \in $ LO[n]} = 1124 $ = {{D}_{{\min }}} + 50$, т.е. $D_{{\min }}^{{LO}}$ превышает ${{D}_{{\min }}}$ всего на 4.88%. Кроме того, были просчитаны минимальные значения $D(\rho )$ на множестве $LO[n]$ при фиксированном наибольшем элементе a_i, $i = \overline {1,20} $. Полученные в результате значения, которые обозначены через $D_{{\min }}^{i}$, можно использовать для формирования весов альтернатив, определяемых, например, по формуле $R{{T}_{i}} = (D_{{\min }}^{i} - {{D}_{{\min }}}){\text{/}}(D_{{\min }}^{{LO}} - {{D}_{{\min }}})$,$i = \overline {1,20} $. В табл. 1 приведены данные для первых лидирующих (относительно линейного порядка $\lambda $) семи альтернатив.

Вычисления производились и для случаев с $n > 20$. Последовательно добавлялись новые альтернативы (включались в каждый из девяти линейных порядков случайным образом). Приведем численные результаты для примера с $n = 25$, $m = 9$. Запишем элементы исходных линейных порядков по возрастанию их предпочтительности:

1, 25, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 21, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24;

24, 22, 16, 25, 23, 15, 20, 19, 21, 18, 17, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1;

19, 14, 20, 24, 13, 12, 22, 23, 11, 25, 16, 17, 10, 9, 8, 7, 6, 21, 5, 4, 3, 2, 1, 15, 18;

18, 24, 13, 25, 21, 12, 23, 11, 16, 10, 9, 8, 7, 6, 20, 17, 22, 5, 4, 3, 2, 1, 15, 14, 19;

12, 20, 23, 17, 24, 22, 19, 11, 10, 9, 8, 7, 6, 5, 4, 3, 25, 2, 1, 15, 16, 21, 14, 13, 18;

20, 11, 22, 16, 23, 21, 10, 24, 18, 17, 9, 8, 7, 6, 5, 4, 3, 2, 1, 15, 14, 25, 13, 12, 19;

22, 19, 24, 23, 18, 17, 25, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 15, 21, 14, 16, 13, 12, 11, 20;

21, 18, 25, 19, 9, 20, 17, 8, 7, 6, 5, 4, 3, 2, 1, 22, 16, 15, 14, 23, 13, 12, 11, 24, 10;

8, 7, 6, 19, 5, 4, 3, 2, 20, 1, 15, 14, 24, 16, 13, 12, 22, 18, 17, 11, 10, 23, 9, 21, 25.

Количество пройденных вершин составляет 3 298 727.

В результате произведенных вычислений было выделено множество ${\text{Arg}}\mathop {\min }\limits_{\rho \in LO[n]} D(\rho )$, состоящее из трех ранжировок:

19, 20, 24, 22, 23, 25, 16, 18, 17, 11, 10, 9, 8, 7, 6, 21, 5, 4, 3, 2, 1, 15, 14, 13, 12;

19, 20, 24, 22, 25, 16, 23, 18, 17, 11, 10, 9, 8, 7, 6, 21, 5, 4, 3, 2, 1, 15, 14, 13, 12;

20, 24, 22, 25, 19, 16, 23, 18, 17, 11, 10, 9, 8, 7, 6, 21, 5, 4, 3, 2, 1, 15, 14, 13, 12.

Во всех трех найденных линейных порядках прослеживается одинаковый строгий порядок относительно 18 лидирующих альтернатив.

Результаты c временем расчетов $t(n)$, где $n = 20,...,26$, представлены в табл. 2. В процессе вычислений определялось также K(n) – количество пройденных вершин, приведенное в третьей строке. В последней строке приводится отношение $K(n){\text{/}}n!$, где $n!$ – количество вычислений целевой функции $D(\rho )$, которое бы потребовалось в случае использования полного перебора.

В связи с этим отметим, что для $n = 26$ при простом переборе пришлось бы рассматривать 26! = 403 291 461 126 605 635 584 000 000 = 4.03 × 10²⁶ вариантов, что невозможно для любого компьютера за любой мыслимый промежуток времени.

Работу приведенного алгоритма можно условно разбить на два этапа: вычисление матрицы P и дальнейшее применение метода ветвей и границ, базирующееся только на элементах этой матрицы. При этом на первом этапе применяется простая процедура, имеющая сложность порядка $O(m{{n}^{3}})$ (т.е. вклад числа экспертов имеет здесь линейный тип зависимости). Таким образом зависимость алгоритма от количества экспертов m несущественна. Увеличение m даже в несколько раз дает изменения общего времени счета на доли секунды.

Заключение. Применение метода ветвей и границ позволяет найти точное решение поставленной задачи, а в случае его не единственности – все множество решений. Предложенный алгоритм может использоваться и при предположении, что индивидуальные ранжировки учитываются с некоторыми коэффициентами относительной важности. Применение алгоритма при наложении на множество ранжировок некоторых дополнительных условий (например, при рассмотрении задачи с закрепленными концами) позволяет устанавливать относительные веса альтернатив или производить попарное сравнение любых двух альтернатив.