К2. ПродолжитьЛ "fc - Q движение вверх? )

КЗ. Движение вниз

к>\, Mfc i = О или А; = 1, Ml > О

Рис. 87. Алгоритм Карпа для примера с лифтом.

А: = 1, И1 = О

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

Алгоритм Карпа (рис. 87) использует два следующих вспомогательных массива:

\<к<п\ число людей на этажах <к, стремящихся попасть на этажи >к\ dk, 1<к<п: число людей на этажах >к, стремящихся попасть на этажи <к.

Когда лифт пуст, мы всегда имеем - d+i при 1 < < п, поскольку на каждом этаже находится Ь человек. Количество людей, направляющихся с этажей {!,..., к} на этажи {к+1,... ,п}, должно быть равно числу людей, стремящихся переехать в обратном направлении. По определению и„ = di = 0.

Ясно, что лифт должен сделать, по крайней мере, \uk/m] рейсов с этажа к на этаж к + 1 при 1 < < п, так как только т пассажиров могут подняться за один рейс. Аналогично он должен сделать не менее [dk/m] рейсов с этажа fc на этаж fc - 1. Следовательно, лифту потребуется, по крайней мере.

{Ы/т] + \dk/m]) к=1

единиц времени при любом правильном графике работы. Карп обнаружил, что эта нижняя граница действительно достижима, если ui,...,Un-i ненулевые.

Теорема К. -Если u. > О при 1 < fc < п, то существует график работы лифта, при котором все люди доставляются на свои этажи за минимальное время (5).

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

К1. [Движение вверх.] Из Ь+т людей, которые находятся в данный момент в лифте и на этаже fc, только m человек, стремящихся на самый высокий этаж, попадает в лифт. Остальные остаются на этаже fc.

Пусть теперь в лифте находится и человек, стремящихся на этажи > fc, и d - на этажи < fc. (Если Uk < тп, окажется, что и = min(m, и;). Следовательно, можно увозить некоторых людей от их места назначения. Это - их жертва во имя общей пользы.) Уменьшить Uk на и, увеличить dk+i Had и затем увеличить fc на 1.

4. ПродолжитьЛ движение вниз? J

Этаж 8: - 25-25-58-88-

899 245 778 577

Этаж 7: - 19-f-18-\-58-f56-77-

889 124 677 556 Этаж 6: - 24 -/-24--44-/-44-56-66-

889 122 677 445 456 455

Этаж 5: - 89-/-77-\п-/-26-24-55-

778 122 266 244

Этаж 4: - 78 -/-66-Vi2-1(-44-

667 122

Этаж 3: - 13-/-13-К:23-33-

667 112 123 122

Этаж 2: - 67-f 03-01-\22 -

036 011 Этаж 1: - 36 -/-00-

000 ООО

Начало Конец

Рис. 88. Оптимальный способ перераспределения людей при помощи небольшого медленного лифта. (Каждый человек представлен номером этажа, на который он направляется.)

Чтобы проверить правильность этого алгоритма, заметим, что на шагах К1 и КЗ всегда поддерживается соответствие данных в массивах и и d в (4) текущему состоянию, если считать людей в лифте находящимися на текущем этаже к. Теперь можно доказать по индукции, что в начале каждого шага справедливы следующие соотношения между параметрами:

щ = при к <1 <п; (6)

щ - - m при 1 < / < fc; (7)

U/+1 = О, если U; = О и fc < / < п. (8)

КЗ. [Движение вниз.] Из Ь + тп людей, находящихся в данный момент в лифте или на этаже к, только тп человек, стремящихся на самый низкий этаж, попадает в лифт. Остальные остаются на этаже к.

Пусть теперь в лифте находится и человек, стремящихся на этажи > к, и d - на этажи < к. (Всегда оказывается, что и = О, а. d = т, т алгоритм описьшается здесь применительно к произвольны.м и и d, чтобы сделать доказательство несколько прозрачнее.) Уменьшить dk на d, увеличить Uk-i на и и затем уменьшить /с на 1.

К4. [Продолжить движение вниз?] Если fc > 1 и Uk-i > О, вернуться к шагу КЗ. Если /с = 1 и ui = О, закончить выполнение алгоритма (все люди доставлены на свои этажи, а тп "дополнительных" человек снова находятся в лифте). В противном случае вернуться к шагу К2.

На рис. 88 показан пример вьшолнения этого алгоритма для здания с девятью этажами, b = 2 и тп = 3. Заметим, что один из тех, кто стремится на шестой этаж, временно отдаляется от своего места назначения, несмотря на то что лифт проходит максимально близко к этому этажу. Идея проверки Uk-i на шаге К4 является, как мы увидим, решающим моментом для правильной работы алгоритма.

Этаж 9: - 45-;99-

899 458

Кроме того, в начале шага К1 в лифте или на этаже к находится min {ик,тп) человек, стремящихся на самые высокие этажи, среди всех людей на этажах < к, котбрью хотят попасть на этажи > fc. В начале шага КЗ в лифте или на этаже к находится min {dt;,m) человек, стремящихся попасть на самые низкие этажи, среди всех людей на этажах > fc, направляющихся на этажи < fc. Эти условия также можно проверить по индукции, если проследить, как мы попадаем на шаг К1 или КЗ (см. упр. 5).

Из сказанного выше следует, что замечания в скобках на шагах К1 и КЗ справедливы. После каждого выполнения шага К1, следовательно, [u/m] уменьшается на 1 и \dk+i Iтп \ остается без изменений. После каждого выполнения шага КЗ \dk/"г] уменьшается на 1 и [Ut i/m] остается неизменным. Значит, алгоритм должен завершиться за конечное число шагов, и после этого в силу (6) и (8) каждый человек должен оказаться на своем этаже.

Если Ufc = О, а Ufc+i > О, мы имеем "несвязную" ситуацию; лифт должен подняться до этажа fc 4-1, чтобы переместить людей вверх, хотя никому не нужно переезжать с этажей < fc на этажи > fc-Ы. Не поступаясь общностью, можно считать u„ i > 0. Тогда любой правильный график должен включать по крайней мере

2 niax(l,rufc/ml) (9)

\<к<п

движений, так как мы требуем, чтобы лифт вернулся на первый этаж. График, для которого достигается эта нижняя граница, несложно построить (см. упр. 4).

УПРАЖНЕНИЯ

1. [20] В методе пузырька Р-го порядка, который проанализирован в тексте раздела, используются только прямое чтение и перемотка. Можно .ли модифицировать алгоритм так, чтобы получить преимущества от обратного чтения?

2. [М26] Найдите явные выражения в замкнутом виде для чисел Xn и Ym , определенных в (3). [Указание. Проанализируйте решение уравнения 5.2.2-(19).]

3. [38] Существует ли метод сортировки с двумя лентами, основанный на сравнении ключей (а не на свойствах, представляющих эти ключи цифр), для которого в наихудшем случае при сортировке Л записей перемещение лент составляет 0{N log N)? [При быстрой сортировке это значение достигается в среднем, но не в наихудшем случае; в методе Хенни-Стирнза (см. рис. 86) оно равняется 0(A(logA)).]

4. [М25] В задаче о лифте предположим, что имеются индексы р я q, причем q> р + 2, Up > О, Uq > О и Up+i = = Uq-i = 0. Объясните, как составить график, требующий не более (9) единиц времени.

► 5. [M2S] Верно ли следующее утверждение? После шага К1 алгоритма теоремы К никто в лифте не стремится попасть на более низкий этаж, кроме тех, кто остался на этажах < к.

6. [МЗО] (Р. М. Карп.) Обобщите задачу о лифте (см. рис. 87) для случая, когда на этаже j первоначально находится bj пассажиров и на этаж j стремится попасть bj пассажиров при 1 < j < п. Покажите, что существует график работы, рассчитанный на 2Efc=i max(l, \uk/т], [dk+i/т]) единиц времени, причем на этаже j никогда не оказывается одновременно более max max(b ,-,b) пассажиров. [Указание. Введите, если необходимо, фиктивных людей, чтобы равенство bj - bj соблюдалось при всех j]

7. [М40] (Р. М. Карп.) Обобщите задачу из упр. 6, заменив линейный путь, который проходит лифт, сетью дорог, по которым можно ездить на автобусе, при условии, что