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

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

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

Форма есть деспотизм внутренней идеи, не дающий материи разбегаться. Разрывая узы этого естественного деспотизма, явление гибнет ([2], с. 75).

Итак,

История (задача) первая (о королях и дорогах)

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

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

Комиссия, созданная специально для решения этой задачи, решила заменить имеющиеся грунтовые дороги, состояние которых резко ухудшалось в дождливую погоду, дорогами более высокого качества, мощенными камнем. Для воплощения принятого решения было необходимо рассчитать минимальные затраты на строительство. Полевые изыскания, проведенные с учетом рельефа местности, почв и растительности, позволили определить наименьшую стоимость строительства каждой дороги, соединяющей любые два поселения (таковых оказалось ровно п (л - 1)/2, где п - число всех населенных пунктов королевства). Подсчеты показали, что общая сумма, требуемая для строительства всех дорог, весьма обременительна для бюджета, и председатель комиссии уже был почти готов идти с невеселым докладом к королю, но тут один из ее членов предложил построить всего лишь п - 1 дорог, причем так, что, перемещаясь только по ним, можно было попасть из каждого поселения в любое другое. Более того, эти дороги можно было выбрать таким образом, чтобы, обеспечивая свободные перемещения из одного населенного пункта в другой, их прокладка привела к минимально возможным финансовым затратам.

(Вспомним предбальный осмотр королем своих владений в старом кинофильме Золушка .)

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

История (задача) вторая (вновь о королях и дорогах)

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

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

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

История (задача) третья

(о Василисе Премудрой и ее мамках-няньках)

Помните детскую сказку Царевна-лягушка , в которой отец Ивана-царевича приказал за единую ночь соткать ему шелковый ковер ? Вышла Василиса Премудрая на красное крыльцо и закричала громким голосом: Мамки-няньки! Собирайтесь, снаряжайтесь шелковый ковер ткать - чтобы таков был, на каком я сиживала у родного моего батюшки! ... Наутро проснулся Иван-царевич, ковер давно готов: изукрашен златом-серебром, хитрыми узорами... ([3], с. 22).

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

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

История (задача) четвертая (о зрелищах и хлебе)

И вновь мы оказываемся в королевстве. Сегодня там большой праздник, даже два. На двух самых больших площадях столичного города приуроченные к празднику притягательные зрелища - сначала казнь злодея (очень интересно посмотреть, как он будет выглядеть на плахе), а затем выступление заезжих артистов (факиры, говорящие лошади, волосатые женщины и тому подобные веселости). Ясно, что толпа, не до конца удовлетворенная лицезрением кровавого зрелища, после его завершения разом хлынет на второе, тоже интересное. Будет давка (как часто случалось такое, и не только в этом королевстве). Можно ли ее избежать? Вообще говоря, можно, но только королевским спецслужбам