6.33. Задача ранжирования

Рассмотрим задачу ранжирования элементов некоторого множества

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

1. Любое лицо побеждает любое другое, либо терпит поражение от него.

2. Отношение сможет победить» — транзитивно.

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

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

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

Для решения задачи Штейнгауз [84] предложил следующую процедуру. В первый момент сравнить два любых элемента. Затем в общем случае после полного ранжирования подмножества из элементов взять любой элемент и сравнить его со средним из уже проранжированных элементов (с любым из средних, если четно). В зависимости от исхода этого сравнения сравнить со средним элементом подмножества элементов, имеющих более высокий или менее высокий ранг по отношению к элементу, участвовавшему при первом сравнении. Так, последовательными дихотомиями точно устанавливается ранг элемента в совокупности элемента.

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

Пусть в качестве примера мы проранжировали элементы а истинный ранг находится между Последовательность выполняемых сравнений показана дугами и на рис. 6.75. Сравниваемые элементы обозначены своими индексами. Таким образом, элемент сравнивается с

Рис. 6.75.

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

и не менее

сравнений.

Форд и Джонсон [23] предложили более эффективный способ ранжирования, основанный на методе Штейнгауза. Пусть нужно проранжировать или элементов. Образуем непересекающихся пар и сравним эти пары. Возьмем элементов, выбранных в процессе этих сравнений (т. е. элементы с максимальными рангами из исходных) и проранжируем их по методу Штейнгауза.

На рис. 6.76, взятом из работы [23], представлены результаты ранжирования для случая множества, состоящего из 19 элементов. На первом этапе сравнения было отобрано элементов в порядке убывания рангов Девять вершин, расположенных ниже

названных, соответствуют элементам, отброшенном на первом этапе, причем каждая вершина располагается под соответствующим отобранным элементом (крайний левый элемент вообще не участвовал в сравнении на первом этапе). Так как 10 элементов множества уже проранжировано, остается найти ранги остальных девяти. Для этой цели использовалась процедура Штейнгауза. Порядок ранжирования элементов показан на рис. 6.76 числами без скобок. Этот порядок выбран с учетом минимизации максимального требуемого числа сравнений. Числа в скобках указывают максимальное число сравнений при определении ранга соответствующего элемента.

Рис. 6.76.

В работе [23] показано, что такой метод требует (при элементах) не более сравнений, где

причем

Известно, что для а также для или 21. Оптимальность процедуры в общем случае не доказана.

Упражнение 6.33. (см. скан)

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

Рис. 6.77.

Последовательность вершин 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 11, 12, 13, 14, 15 определяет гамильтоиов путь. Хорошей процедурой ранжирования будет та, которая позволит найти гамильтоиов путь при минимальном числе вводимых в граф дуг.

ЛИТЕРАТУРА

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)