24. [22] (Ю. Л. Лолер (Е. L. Lawler).) Каково максимальное число сравнений, необходимых для следующего алгоритма слияния т элементов с п > т элементами? "Установить t <- [lg{n/m)\ и использовать алгоритм 5.2.4М для слияния Ai, А2, ..., Am с Вг», 2,2*, ..., В,.2«, где q = [n/2*J. Затем вставить каждый элемент Aj на свое место среди Вк"

► 25. [25] Предположим, что {xij) есть матрица m х п с неубывающими строками и столбцами: Xij < X(i+i)j при 1 < i < т и Xij < при 1 < j < и. Покажите, что М{т,п) есть минимальное число сравнений, необходимых для того, чтобы выяснить, присутствует ли данное число х в матрице, если все сравнения выполняются между х и некоторым элементом матрицы.

*5.3.3. Выбор с минимальным числом сравнений

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

История постановки и поиска решений этой проблемы восходит к занимательному (хотя и серьезному) эссе преподобного Ч. Л. Доджсона (С. L. Dodgson) о турнирах по теннису, появившемуся в St. Jamess Gazette 1 августа 1883 года (с. 5-6). Доджсон, который, разумеется, более известен как Льюис Кэррол, рассматривал несправедливые правила, по которым присуждались (и до сих пор присуждаются) призы в турнирах по теннису. Рассмотрим, например, рис. 39, на котором показана схема типичного турнира с выбыванием между 32 игроками, помеченными 01, 02,..., 32. В финале игрок 01 одерживает победу над игроком 05, поэтому ясно, что игрок 01 - чемпион и заслужил первый приз. Несправедливость проявляется в том, что игрок 05 обычно получает второй приз, хотя он может и не быть вторым по силе игроком. Выиграть второй приз можно, даже если играешь хуже половины игроков турнира. В самом деле, как заметил Доджсон, второй по силе игрок выигрывает второй приз в том и только том случае, если первоначально он и чемпион находились в противоположных частях турнирной таблицы; для турнира с 2" участниками это происходит с вероятностью 2"~7(2" 1)) так что почти в половине случаев второй приз получает не тот игрок! Если проигравшие в полуфинале (игроки 25 и 17 па рис. 39) соревнуются за третий приз, то весьма маловероятно, что третий по силе игрок получит третий приз.

Поэтому Доджсон решил найти такую схему турнира, которая правильно определяет второго и третьего по силе игроков в предположении, что соблюдается закон транзитивности. (Иначе говоря, если игрок А побеждает игрока В, а В побеждает С, то можно считать, что игрок А победит С.) Доджсон придумал процедуру, в которой проигравшим дается возможность сыграть еще несколько игр, пока не станет определенно известно, что они слабее других трех игроков. Пример схемы Доджсона приводится на рис. 40. Здесь изображена сетка игр дополнительного турнира; его следует провести вместе с турниром, схема которого показана на рис. 39. Доджсон попытался составить пары игроков, у которых до сих пор были равные результаты, и исключить матчи между игроками, побежденными одним и тем же участником. В таком конкретном примере игрок 16 проигрывает игроку 11, а игрок 13 проигрывает игроку 12 в первом туре; после того как игрок 16 проигрывает игроку 13 во втором туре, игрок 16 исключается, так как теперь известно, что он слабее игроков 11, 12 и 13. В третьем туре исключается встреча игроков 19 vl 21,

Чемпион = 0J

~1 05 i

25 I

-1 17

Тур 5 (Полуфинал) Г

Тур 4 Oi

Тур 3 01

Тур 2 01 03 02 04

Тур 1 01 07 03 10 02 08 04 09 25 28 26 27 29 32 30 31 05 15 06 Ц 11 16 12 13 17 24 20 23 18 19 21

29 I

05 I

11 i

17 1

-1 18

26 29 30 05 06 и 12 17 20 18 21

Рис. 39. Турнир между 32 игроками с выбыванием.

так как они оба были побеждены игроком 18, но нельзя автоматически исключить проигравшего во встрече игроков 19 и 21.

Было бы приятно сообщить, что схема турнира, предложенная Льюисом Кэрро-лом, оказалась оптимальной, но, к сожалению, это не так. Из записи в его дневнике от 23 июля 1883 года явствует, что он составил это эссе примерно за шесть часов и чувствовал, что, "поскольку [теннисный] сезон приближается к концу, будет лучше сделать так, чтобы оно [эссе] появилось побыстрее, чем чтобы оно было хорошо написано". В его процедуре делается больше сравнений, чем необходимо, и она не сформулирована достаточно четко, чтобы квалифицировать ее как алгоритм. С другой стороны, в ней имеются некоторые очень интересные аспекты, если судить с точки зрения параллельных вычислений. Предложенную схему можно считать отличной турнирной сеткой, поскольку Кэррол включил в нее несколько драматических эффектов; например, он определил, что два финалиста должны пропустить пятый тур и сыграть дополнительный .матч в турах 6 и 7. Однако организаторы турниров, по-видимому, сочли его предложение излишне логичным, и потому система Кэррола, скорее всего, никогда не испытывалась. Вместо этого практикуется метод "рассеивания" более сильных игроков, чтобы они попали в разные части дерева.

Тур 9 Тур 8 Тур 7 Тур 6

Тур 2

02 i

Тур 5 02 Тур 4 02 20

Третье место = 03

12 гЧ

Тур 3 so 21 12 19

02 i

06 06 27

Второе место = 02

02 i

07 29

~1 08

19 22 27 28 23 24 31 32 07 10 08 09

03 i

03 i

26 i.

11 11 18

г-1 03 04 26 30

-i 17

17 25

13 Ц 13 16 14 15

Рис. 40. Сетка теннисного турнира Льюиса Кэррола (в дополнение к сетке, представленной на рис. 39).

На математическом семинаре в 1929-1930 годах Гуго Штейнгауз (Hugo Stein-haus) сформулировал постановку задачи нахождения миньмалъного числа поединков, требуемых для определения первого и второго игроков в турнире, если всего

имеется n > 2 участников. В работе J. Schreier, Mathesis Polska 7 (1932), 154-160, приведена процедура, требующая самое большее п - 2 + [Ig п] матчей. В ней использован, по существу, тот же метод, что и на первых двух стадиях процесса, который мы назвали сортировкой посредством выбора из дерева (см. раздел 5.2.3, рис. 23), однако не выполняли дополнительных сравнений с -оо. В работе также утверждается, что п - 2 -f- [Ign] - наилучшее возможное значение, но приведенное доказательство было ошибочным, как и еще одна попытка доказательства, предпринятая в работе J. Slupecki, Colloquium Mathematicum 2 (1951), 286-290. Прошло 32 года, прежде чем С. С. Кислицыным было опубликовано правильное, хотя и очень сложное, доказательство [Сибирский математический журнал 5 (1964), 557-564].

Пусть Vt{n) обозначает минимальное число сравнений, требуемых для определения t-ro в порядке убывания элемента из п элементов, 1 < t < п, и пусть Wtin) равно наименьшему числу сравнений, необходимых для определения наибольшего, второго,... и t-ro элементов всех сразу. Вследствие симметрии имеем

Vt(n)=y„+i t(n), (1)

очевидно также, что

Vxin) = Wiin), (2)

Vtin) < Wtin), (3)

Wnin) = W„-iin) = Sin). (4)

Как следует из леммы 5.2.3М,

Viin) = n-1. (5)

Существует удивительно простое доказательство этого факта - каждый участник турнира, кроме чемпиона, должен проиграть, по крайней мере, одну игру! Обобщая эту идею и используя "соперника" как в разделе 5.3.2, можно без особого труда доказать теорему Шрейера-Кислицьша.

Теорема S. V-zin) = W-zin) = n - 2 -f [Ign] при n > 2.

Доказательство. Предположим, что в турнире, в котором после проведения некоторой заданной процедуры должен определиться второй игрок, участвуют п игроков и пусть Qj - число игроков, проигравших j или больше матчей. Общее число сыгранных матчей будет тогда равно 01+02+03-]----. Нельзя определить второго игрока,

не выявив заодно и чемпиона (см. упр. 2), поэтому из предыдущих рассуждений получаем oi = п - 1. Для завершения доказательства покажем, что всегда существует последовательность результатов матчей, которая приводит к 02 > [Ign] - 1. Предположим, что к конпу турнира чемпион сыграл р игр и победил р игроков; одним из них был второй по силе игрок, а остальные должны проиграть, по крайней мере, еще по одному разу, поэтому 02 > р - 1- Итак, можно завершить доказательство, построив соперника, предопределяющего результаты игр, таким образом, чтобы чемпиону пришлось сыграть еще хотя бы с [Ig п] другими участниками турнира.

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