Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
 Скачать 2.32 Mb.
|
|
получили два способа переливания, тратящие различное число операций. Возможно, существуют еще решения? Вообще, подобные задачи могут быть легко решены с помощью следующего наглядного инструмента. Рассмотрим прямоугольную матрицу с сеткой, как показано на рис. 2.7, а. Вертикальная сто- рона матрицы соответствует емкости в 3 л, горизонтальная — ем- 34 кости в 5 л (таким образом, числа легко могут быть обобщены). Координаты точек пересечения линий задают количество воды в двух сосудах. Если находимся в одном из узлов, то допустимой операцией является движение по любой линии до конца отрезка. Задав начальное и искомое конечное состояния, задача сведет- ся к поиску пути из одного узла сетки в другой. Для решений, приведенных на рис. 2.6, соответствующие им пути показаны на рис. 2.7, б и в. Если требуется найти не просто решение, а реше- ние, требующее минимальное число операций, можно представить сетку на рис. 2.7, а в виде направленного графа, и применить по- иск в ширину. Задача 2.5 (задача о 23 спичках ). Имеется 23 спички. Двое игроков по очереди берут от одной до трех спичек, проигрывает тот, кто берет последнюю спичку. Разработать стратегию игры. Решение. Эта задача представляет пример игры, для которой существует выигрышная стратегия, причем только для одного из игроков. Для нахождения этой стратегии попробуем применить метод отрабатывания назад. Наша цель — оставить противнику единственную спичку, тогда он проиграл. Но тогда нельзя допу- стить ситуации, при которой в момент хода противника остаются 2, 3 или 4 спички. В этом случае он всегда сможет взять соот- ветственно одну, две или три спички, и нам останется последняя, «проигрышная». С другой стороны, если при его ходе в игре оста- ются пять спичек, после любого его хода количество спичек со- ставит 2, 3 или 4, что гарантирует нам выигрыш. Тогда задача сводится к тому, что оставить противнику 5 спичек. Аналогичны- ми рассуждениями получаем, что оставлять для его хода 6, 7 или 8 спичек также нельзя. Продолжая этот ряд, получим рис. 2.8. Таким образом, для выигрыша необходимо всегда оставлять противнику 1, 5, . . ., 21, . . ., 4n + 1 спичку. Так как изначально спичек 23, то этой возможностью всегда обладает тот, кто ходит первым, взяв две спички. Рассмотренное решение, конечно, не означает, что первый иг- рок выигрывает всегда. Он выигрывает только в том случае, если следует данной стратегии. Если же он допустил ошибку или стра- 35 1 2 3 4 5 6 7 8 9 17 18 19 20 21 22 23 Д Д а Рис. 2.8. Задача о 23 спичках тегия ему незнакома, то второй игрок, зная стратегию выигрыша, может тут же перехватить инициативу и довести игру до победы. Изменение количества спичек также может поменять победителя — очевидно, что при 21 спичке (и вообще, любом количестве спи- чек, равном 4n + 1) выигрышная стратегия принадлежит игроку, который ходит вторым. Задача 2.6 (задача о греческом кресте). Двумя прямыми ли- ниями разрезать греческий крест (рис. 2.9) так, чтобы из полу- чившихся частей можно было сложить квадрат. Решение. Для решения этой задачи попробуем применить ме- тод частных целей. В качестве первой такой подзадачи выделим вопрос, какой площадью должен обладать получившийся квад- рат? Ясно, что площадь квадрата будет равна площади греческо- го креста. Как видно из рис. 2.9, греческий крест состоит из пяти малых квадратов. Примем сторону одного такого малого квадрата за 1. Тогда площадь креста и, следовательно, большого квадрата равна S = 5. Далее, отсюда получаем, что сторона большого квадрата, ко- торый должен получиться, составит l = √ 5. Таким образом, дву- мя прямыми линиями нужно отсечь в кресте фигуры со сторо- ной, равной l. Кроме этого, углы при этих сторонах должны быть прямыми (это означает, в частности, что две проводимые прямые должны быть перпендикулярны). Теперь следующая частная цель — выделить в греческом кресте отрезок длиной √ 5. Из сторон ма- лых квадратов можем выделять отрезки длины 1, 2, 3. Проводя 36 Рис. 2.9. Задача о греческом кресте 1 A B C 2 A B C D A B C D a) ) Рис. 2.10. Решение задачи о греческом кресте наклонные линии под заданным углом, можно отсекать отрезки известной длины. Для нашей задачи заметим, что l 2 = 5 = 1 + 4, т.е. квадрат l равен сумме квадратов чисел 1 и 2. Такое соот- ношение в рассматриваемой фигуре легко найти — рассмотрим треугольник ABC на рис. 2.10, а. Катеты этого прямоугольно- го треугольника равны 1 и 2, а гипотенуза по теореме Пифагора составит √ 5. Более того, легко можно показать, что линия, па- раллельная гипотенузе AC (например, отмеченная на рис. 2.10, а пунктиром), также будет отсекать отрезок длины √ 5. Пользуясь геометрическими свойствами получаемых фигур, дальнейшими рассуждениями можно показать, что две линии, параллельные гипотенузам соответствующих квадратов, перпен- дикулярны и отсекаемые ими части креста действительно могут образовать квадрат, рис. 2.10, б. Задача 2.7 (задача о легкой фальшивой монете). Имеется 25 монет, среди которых, возможно, находится одна фальшивая. Фаль- 37 шивая монета легче остальных, и в нашем распоряжении нахо- дятся весы с двумя чашками. Требуется определить фальшивую монету или установить, что фальшивых монет нет. Решение. Для решения этой задачей попробуем воспользо- ваться методом подъема вверх. Найдем некоторое решение, т.е. определим порядок взвешивания монет, а затем попробуем это ре- шение улучшить. Итак, попробуем разделить все множество монет на две части. Так как число монет нечетно, то получим две груп- пы по 12 монет и еще одна останется в запасе. Порядок взвешива- ния проиллюстрирован с помощью дерева на рис. 2.11. Каждый овал задает количество взвешиваемых монет на каждой чаше ве- сов, в кружке рядом с овалом отмечено, сколько остается монет. Квадратами с цифрой 1 помечена ситуация, когда фальшивую монету уже можно определить однозначно. Результатом первого взвешивания могут являться три случая. Во-первых, 12 монет на левой чаше весов оказываются легче 12 монет на правой чаше. Это означает, что фальшивая монета находится на левой чаше и в дальнейшем можно рассматривать только эти 12 монет. Если правая чаша оказывается легче, то под подозрением оказываются другие 12 монет. Если же чаши весов уравновешены, то фальши- вой может являться только единственная оставшаяся монета, и еще за одно взвешивание с любой из остальных 24 определяем ре- зультат (на этом шаге результатов взвешивания два, а не три, так как знаем какая монета точно правильная и для определенности можем положить ее на левую чашу весов). Далее, если остались 12 монет, снова поделим их на этот раз поровну, на две части по 6 монет и осуществим взвешивание. За- тем образуются группы из 3 монет, и наконец, из оставшихся трех взвешиваются любые две. Так как в этом случае уже точно извест- но, что фальшивая монета есть, то дополнительное взвешивание для оставшейся монеты не требуется. Схема на рис. 2.11 полностью симметрична, поэтому приве- дена не полностью. Эта схема требует в худшем случае четырех взвешиваний. Можно ли улучшить ее так, чтобы сократить число взвешиваний? В чем главный недостаток схемы? 38 {12}: {12} {6} : {6} < = > < > {3} : {3} < > {1} : {1} 1 1 < = > 1 {1} : {1} 1 1 < = > 1 {3} : {3} {6} : {6} 1 0 0 1 1 0 0 {1} : {1} 1 1 = > 0 Рис. 2.11. Задача о легкой фальшивой монете {9}: {9} {3} : {3} < = > < > {3} : {3} {3} : {3} {1} : {1} 1 1 < = > 1 < > {1} : {1} {1} : {1} {1} : {1} = {1} : {1} 1 = 7 3 1 1 3 1 1 1 3 Рис. 2.12. Другое решение задачи о легкой фальшивой монете 39 Можно легко увидеть, за счет чего может произойти улуч- шение. Дело в том, что любое взвешивание подразумевает три возможных результата: когда одна чаша весов легче, когда она тяжелее и когда весы уравновешены. Результат равенства весов используется только при первом и последних взвешиваниях и то для поиска среди двух или трех оставшихся монет. Главным на- шим принципом было делить все или почти все монеты на две части, что практически исключило из дерева взвешиваний подде- ревья, соответствующие равенству на весах. Те же самые выводы можно получить с другой стороны. У нас 25 монет и существует 26 возможных исходов. Эти исходы являются листьями дерева взвешиваний. Число исходов-листьев уменьшено быть не может, но чтобы уменьшить число взвешива- ний нужно, чтобы дерево больше росло «вширь», чем «вглубь», т.е. имело меньше уровней. Для этого нужно увеличить размер- ность этого дерева. Так как более чем троичным дерево взвеши- ваний быть не может, нужно приблизить его максимально близко к полному троичному дереву, а для этого монеты необходимо де- лить на три примерно равные части. Попробуем применить этот подход. Разделим все монеты на группы по 9, 9 и 7 монет. Схема взвешиваний показана на рис. 2.12. Видно, что проведенные рас- суждения действительно позволили улучшить решение: теперь в худшем случае требуется только три взвешивания. Причем ясно, что еще лучше решение быть не может, так как для того, чтобы тернарное дерево имело 26 листьев, оно должно иметь как мини- мум 3 уровня. Задача 2.8 (задача о белых и черных шарах ). В корзине на- ходятся n шаров белого либо черного цвета. Шары вынимаются из корзины вслепую, по два шара за раз. В зависимости от цвета вытащенных шаров предпринимаются следующие действия: белый и черный: белый возвращается в корзину; оба белые: в корзину добавляется черный шар; оба черные: один черный шар возвращается в корзину. 40 Рис. 2.13. Задача о белых и черных шарах Требуется определить, какой цвет будет у последнего, остав- шегося в корзине шара. Решение. Эта задача очень легко может быть решена с помо- щью отрабатывания назад. Во-первых, отметим, что на каждом шаге вне зависимости от цветов из корзины два шара убирают- ся и добавляется один. Таким образом, на каждом шаге число шаров уменьшается на единицу. Далее предположим, что в кор- зине у нас остался единственный шар: либо белого, либо черного цвета. Предположим, что шар — белый. По условию задачи это может произойти в единственном случае: когда на предыдущем шаге в корзине находились черный и белый шары. Теперь если в корзине у нас два шара разного цвета, то еще шагом раньше в корзине было три шара, из которых либо один был белый и к нему добавился черный — это возможно, когда были вынуты два шара одинакового цвета или был черный, и добавлен был белый — в том случае, если вынуты шары разного цвета. Все эти варианты сводятся всего к двум возможностям: в корзине три шара белого цвета либо один белый и два черных. Эти рассуждения можно продолжать и дальше — получаемые комбинации шаров показаны на рис. 2.13. Точно так же строим рассуждения и для предположения о том, что последний шар яв- ляется черным. Схем, приведенных на рис. 2.13, достаточно, что- бы заметить закономерность: любая начальная комбинация, со- держащая нечетное число белых шаров, приводит нас к белому 41 Рис. 2.14. Задача о покрытии шахматной доски шару, любая же комбинация, содержащее четное число белых ша- ров, должна закончиться оставшимся черным шаром. Попробуем обосновать эту догадку. Как уже говорили, на каждом шаге об- щее количество шаров в корзине уменьшается на 1. Однако по условиям задачи (см. схему в прямоугольной рамке на рис. 2.13) в результате хода количество черных шаров может либо умень- шиться на 1 (если вытащены два черных шара), либо увеличиться на 1 (если вытащены два белых шара), либо остаться неизменным. Количество же белых шаров остается неизменным либо уменьша- ется на два. Таким образом, четность количества белых шаров в корзине при любых начальных условиях остается неизменной, четность же черных шаров нарушается при каждом изменении их количества. Тогда, очевидно, если количество белых шаров нечетно — по- следний белый шар никогда не сможет быть вытащен из корзины и останется последним. Если же их четное число — то рано или поздно все белые шары будут вынуты и последняя их пара бу- дет заменена на черный шар. После этого все оставшиеся шары в корзине будут черными, и белых не будет добавляться. Задача 2.9 (задача о покрытии шахматной доски). Можно ли костяшками домино покрыть шахматную доску размером 8 × 8, у которой удалены два угловых поля на одной диагонали? Одна костяшка домино покрывает два поля доски. 42 Решение. Доска, удовлетворяющая условию задачи, изобра- жена на рис. 2.14. Для этой задачи можно применить метод част- ных целей. Легко заметить, что костяшка домино всегда покры- вает одно белое и одно черное поле. Таким образом, общее ко- личество белых и черных полей, покрытых костяшками домино, всегда одинаково. Далее для доски 8 × 8 угловые клетки, лежащие на одной диа- гонали, всегда имеют одинаковый цвет. Удалив два поля одного цвета, сделали количество белых и черных полей неравным — и, следовательно, невозможным покрытие всей доски. 2.3. Рекурсия При создании или описании разного рода алгоритмов часто можно заметить, что решение той или иной задачи может быть выражено как комбинация или модификация решений той же за- дачи (или другой, но с известным решением), с другими входны- ми данными, другой размерностью, дополнительными условиями и т.п. Выявление подобных закономерностей позволяет либо най- ти решение данной задачи через решения уже известных задач, либо получить дополнительную информацию о «структуре» ре- шаемой проблемы, ее свойствах, и эта информация может быть использована при разработке алгоритмов решения. Одним из слу- чаев такой закономерности является возможность описать задачу с помощью рекурсивной последовательности действий, или, про- ще говоря, рекурсии. Определение 2.4 Рекурсивный алгоритм — решение задачи в ходе выполнения обращающееся само к себе. Одна и та же задача может быть решена как с применением рекурсии, так и без нее. Вообще, любой рекурсивный алгоритм может быть описан нерекурсивно, но не наоборот. Рекурсия ча- сто является удобным алгоритмическим решением задачи, одна- ко не всегда удачна с точки зрения реализации встроенными ме- тодами рекурсии на языке программирования: при рекурсивном 43 вызове функции требуется сохранение значений всех локальных переменных, точки возврата, что может привести к переполнению выделенной программе памяти даже при формально корректной записи алгоритма и реализации. Рекурсивный алгоритм обязательно должен содержать две ча- сти: 1. Шаг рекурсии. Указание, каким образом производится ре- курсивный вызов. 2. База рекурсии. Условие выхода из рекурсии. Распространенной ошибкой является отсутствие базы рекур- сии — это приводит к зацикливанию алгоритма или его некор- ректному завершению. Далее рассмотрим несколько задач, кото- рые могут быть решены с помощью рекурсии. Задача 2.10 (вычисление факториала). Вычислить значение функции факториала f (n) = n! от целого неотрицательного числа n n! = n(n − 1)(n − 2) · . . . · 2 · 1. (2.1) Решение. Пусть у нас имеется некоторый алгоритм P , кото- рый для данного числа n «умеет» вычислять значение фактори- ала, P (n) = n! Из определения факториала (2.1) легко заметить, что P (n) = nP (n − 1). Аналогично можно получить, что P (n − 1) = (n − 1)P (n − 2), P (n − 2) = (n − 2)P (n − 3) и т.д. В общем случае P (i) = iP (i − 1), i > 0. (2.2) Выражение (2.2) задает шаг рекурсии. Для любой размерно- сти задачи i указываем способ решения, используя задачу с дру- гой (меньшей) размерностью. Решая задачу для входного аргу- мента i, предполагаем, что умеем решать задачу для входного 44 A B C Рис. 2.15. Ханойская башня аргумента i − 1. Для того чтобы рекурсия завершилась необходи- мо задать базу рекурсии. В данном случае ее легко задать, зная значение факториала при минимальных i P (0) = 1. (2.3) Соотношения (2.2) и (2.3) полностью определяют рекурсивный алгоритм вычисления факториала P (i) = iP (i − 1), i > 0, P (0) = 1. Выражения (2.2) и (2.3) задают рекуррентное уравнение. Очевид- но, ту же задачу можно решить и без применения рекурсии, с помощью цикла, меняя значения переменной i от 1 до n. Задача 2.11 (Ханойская башня). На стержне A покоятся n дисков разного диаметра, расположенных по убыванию размера: самый большой диск лежит нижним, самый маленький — верх- ним. Требуется переложить все диски на свободный (пустой) стер- жень B, пользуясь вспомогательным свободным стержнем C так, чтобы ни в какой момент времени диск большего диаметра не на- ходился выше диска с меньшим диаметром. Условие задачи про- иллюстрировано рис. 2.15. Решение. Решение данной задачи состоит в нахождении отве- тов на целый ряд вопросов. Первый — разрешима ли эта задача вообще? Второй — если задача разрешима, существует ли некая 45 оптимальная стратегия перекладывания дисков, при которой чис- ло действий (перекладываний) будет минимально? Как зависит время решения задачи от числа дисков? Доказательство существования решения проведем конструк- тивно, т.е. показав способ перекладывания дисков (возможно, не- оптимальный), который даст решение при любой размерности за- дачи. Обозначим через P (n, x, y, z) способ перекладывания n дис- ков со стержня x на стержень y через промежуточной стержень z. Тогда P (n, A, B, C) = P (n − 1, A, C, B), P (1, A, B, C), P (n − 1, C, B, A), (2.4) т.е. сначала n − 1 диск перекладываются на промежуточный стер- жень C, потом единственный (самый большой) диск со стержня A перемещается на стержень B, после чего n − 1 дисков перемеща- ются со стержня C на итоговый стержень B. Получаем рекурсию: свели решение задачи к этой же задаче с меньшей размерностью. Чтобы уметь решать задачу с меньшей размерностью, снова нуж- на база рекурсии. При n = 1 один диск просто сразу переклады- вается со стержня A на стержень B. Два диска можно легко пе- реложить, используя стержень C (см. рис. 2.16). Пользуясь этими схемами, можно переложить любое большее количество дисков. На самом деле, последовательность действий, предложенная в (2.4), является логичной и естественно следующей из условия задачи. Действительно, в какой-то момент времени необходимо переложить на стержень B самый нижний диск. Так как он явля- ется и самым большим, стержень B в этот момент должен быть пуст. Значит все n − 1 дисков должны лежать на стержне C, при- чем опять же в порядке уменьшения диаметров по условию зада- чи. Оценим сложность предложенной процедуры. Пусть T (n) — число перемещений n дисков с одного стержня на любой другой. Из (2.4) получаем T (n) = 2T (n − 1) + T (1). (2.5) Оценка времени выполнения (2.5) является как достаточной, так 46 Рис. 2.16. Решение Ханойской башни для двух и трех дисков 47 и необходимой. Достаточность следует из того, что процедура (2.4), имеющая сложность (2.5), решает задачу, т.е. она решает- ся не более, чем за T (n) шагов. Необходимость уже рассмотрена: в какой-то момент нужно переместить нижний диск и для этого выполнить T (n−1) предварительных, и столько же последующих перемещений. Необходимое и достаточное число перемещений для любого n можно вычислить, пользуясь формулой (2.5), и учитывая началь- ные условия T (i) = 2T (i − 1) + 1, i > 0, 0, i = 0. (2.6) Неудобство выражения (2.6) заключается в том, что для вычис- ления T (100) необходимо вначале вычислить T (99), T (98) и т.д. В (2.6) снова, как и в задаче нахождения факториала, имеем рекур- рентное уравнение. Рекуррентное уравнение может быть решено, т.е. выражено в «замкнутой» форме, позволяющей находить i-й член последовательности без поиска предыдущих. Решение урав- нения (2.6) довольно просто находится из нескольких частных случаев. Действительно, заметим, что из (2.6) T (0) = 0, T (1) = 1, T (2) = 3, T (3) = 7, T (4) = 15, Легко видеть, что получаемые числа на 1 меньше соответству- ющих степеней двойки T (n) = 2 n − 1. (2.7) Конечно, пока что это только догадка, гипотеза, но эту гипотезу можно попробовать доказать, например с помощью математиче- ской индукции. 48 Далеко не всегда, глядя на первые несколько элементов по- следовательности, можно «угадать» правило, по которому могут быть найдены последующие элементы этой последовательности. Далеко не всегда такие догадки оказываются правильными и в любом случае они должны быть доказаны. Однако в данном слу- чае предположение (2.7) действительно верно. Таким образом, для нахождения T (100) достаточно вычислить T (100) = 2 100 − 1. Задача о Ханойской башне имеет экспоненциальную сложность T (n) = O(2 n ). Это одна из немногих задач, в которой доказа- но, что ее нельзя решить менее чем за экспоненциальное число шагов. Задача 2.12 (задача о числе разбиений). Найти число спосо- бов, какими можно разбить целое положительное число N на сум- му целых положительных чисел N = n 1 + n 2 + . . . + n m , n i > 0. Решение. Условимся, что не будем различать разбиения, отли- чающиеся только перестановкой слагаемых. Таким образом, раз- биения 4 + 2 и 2 + 4 числа 6 будем считать одним и тем же раз- биением. Тогда все возможные разбиения числа 6 приведены в табл. 2.3. Таблица 2.3. Таблица разбиений числа 6 1 6 = 6 2 6 = 5 + 1 3 6 = 4 + 2 4 6 = 4 + 1 + 1 5 6 = 3 + 3 6 6 = 3 + 2 + 1 7 6 = 3 + 1 + 1 + 1 8 6 = 2 + 2 + 2 9 6 = 2 + 2 + 1 + 1 10 6 = 2 + 1 + 1 + 1 + 1 11 6 = 1 + 1 + 1 + 1 + 1 + 1 49 Обозначим через P (N ) количество разбиений числа N . Оче- видно (и это можно видеть в табл. 2.3), число разбиений можно сводить к числу разбиений слагаемых, входящих в уже учтенные суммы. Итак, ясно, что из разбиения 5 + 1 (вторая строка таб- лицы) можно получить другие разбиения числа 6, находя их из разбиений числа 5. Таким образом, в данной задаче также можно использовать рекурсивные вызовы. Пусть имеем какое-то разбиение и в нем максимальное сла- гаемое M , т.е. n i ≤ M . Обозначим через Q(N, M ) количество разбиений числа N слагаемыми, не превышающими M . Если в разбиении есть слагаемое, точно равное M , можно вычесть его из N , и далее искать разбиение числа N − M . Если в разбиении нет слагаемых больших или равных M , можно считать, что на самом деле ищем Q(N, M − 1). Тогда записываем шаг рекурсии как выражение Q(N, M ) = Q(N, M − 1) + Q(N − M, M ). (2.8) Очевидно, что искомое число P (N ) может быть выражено как P (N ) = Q(N, N ). Далее, на первом шаге всегда можно учесть тривиальное разбиение N = N и получить Q(N, N ) = Q(N, N − 1) + 1. Из определения Q(N, M ) следует, что Q(N, M ) = Q(N, N ), если N < M . Добавив базу рекурсии, получим следующий набор выражений: P (N ) = Q(N, N ), (2.9) Q(N, M ) = Q(N, M − 1) + Q(N − M, M ), M < N, (2.10) Q(N, M ) = Q(N, N − 1) + 1, M = N, (2.11) Q(N, M ) = Q(N, N ), M > N, (2.12) Q(1, M ) = 1, (2.13) Q(N, 1) = 1. (2.14) 50 Попробуем применить полученные рекурсивные выражения для вычисления P (6). Тогда P (6) = Q(6, 6) = 1 + Q(6, 5) = в силу (2.9) и (2.11) = 1 + Q(6, 4) + Q(1, 5) = в силу (2.10) = 2 + Q(6, 3) + Q(2, 4) = в силу (2.10) и (2.13) = 2 + Q(6, 2) + Q(3, 3) + Q(2, 2) = = 4 + Q(6, 1) + Q(4, 2) + Q(3, 2) + Q(2, 1) = = 6 + Q(4, 1) + Q(2, 2) + Q(3, 1) + Q(1, 2) = = 10 + Q(2, 1) = 11. Полученный результат совпадает с приведенным в табл. 2.3. 2.4. Методы декомпозиции и композиции В подразд. 2.2 и 2.3 рассмотрены методы, которые могут быть использованы при разработке алгоритмов, и приведены примеры задач. В этом подразделе определим еще два подхода, называемых декомпозицией и композицией. Определение 2.5 Декомпозиция — метод решения задач, основанный на раз- биении исходной задачи на подзадачи того же типа, но меньшей размерности. Определение 2.6 Композиция — метод решения задач, основанный на постро- ении решения из уже известных решений подзадач того же типа и меньшей размерности. Отметим, что в обоих подходах подразумевается работа с одно- типными задачами, отличающимися только размерностью, в от- личие от метода частных целей, где в качестве целей могут вы- ступать задачи произвольной природы. В качестве иллюстрации метода декомпозиции приведем одно из возможных решений за- дачи умножения целых чисел. 51 Задача 2.13 (быстрое умножение чисел). Пусть U и V — це- лые n-разрядные числа, тогда U = (u n−1 , . . . , u 0 ), u i ∈ 0, 1, V = (v n−1 , . . . , v 0 ), v i ∈ 0, 1. Требуется вычислить произведение чисел U V . Решение. Данная задача представляет собой проблему постро- ения так называемых «быстрых» алгоритмов, когда уже известен некоторый стандартный способ решения, и требуется найти дру- гое решение, обладающее меньшей сложностью. Поэтому в усло- вии задачи подразумевается не просто найти результат умноже- ния двух чисел, а сделать это с помощью алгоритма, выигрыва- ющего по сложности у некоторого стандартного метода. Для процедуры умножения таким стандартным методом явля- ется умножение в столбик, т.е. умножение разрядов одного числа на все разряды другого, и потом сумма полученных результатов. Так как перемножаем каждый из n разрядов одного числа на все n разрядов другого числа, сложность такого умножения в столбик составляет O(n 2 ). Попробуем применить для задачи умножения метод декомпо- зиции. Разобьем каждое из чисел на две части по n/2 бит. Пусть U = [a, b], где a = (u n−1 , . . . , u n/2 ), и b = (u n/2−1 , . . . , u 0 ). Ана- логично V = [c, d], где c = (v n−1 , . . . , v n/2 ) и d = (v n/2−1 , . . . , v 0 ). Тогда U = a · 2 n/2 + b, V = c · 2 n/2 + d, где умножение на степень двойки 2 n/2 производится с помощью побитового сдвига на n/2 позиций влево. Тогда U V = (a · 2 n/2 + b)(c · 2 n/2 + d) = = ac · 2 n + (ad + bc) · 2 n/2 + bd. (2.15) В выражении (2.15) использовано три сложения, два сдвига и че- тыре умножения n/2-разрядных чисел. Сложность обычного сло- жения в столбик n-разрядных чисел составляет O(n), такой же мы можно считать и сложность побитового сдвига. Обозначим 52 сложность умножения n-разрядных чисел за T (n), тогда T (n) = 4T (n/2) + 5O(n) или, если умножение чисел меньшей разрядности выполнять в столбик, т.е. T (n/2) = O(n 2 /4) получим T (n) = 4O(n 2 /4) + 5O(n) ≡ O(n 2 ) + 5O(n). По сравнению с изначальной сложностью T (n) = O(n 2 ) не только не выигрываем, но и проигрываем, добавив лишние пять опера- ций. Оказывается, выигрыш можно получить, воспользовавшись небольшим трюком, предложенным Карацубой и Виноградом. C помощью некоторых переобозначений и простой группировкой сла- гаемых в (2.15) можно получить x = ac, y = bd, z = (a + b)(c + d), U V = x · 2 n + (z − x − y) · 2 n/2 + y. (2.16) На этот раз в (2.16) содержится три n/2-разрядных умножения, шесть сложений и два сдвига. Запишем это T (n) = 3T (n/2) + kn, (2.17) где k — некоторая константа, которая учитывает все побочные действия со сложностью O(n), на общий порядок сложности сла- гаемое kn не будет влиять, если только сложность всех остальных составляющих алгоритма также не станет эквивалентна или про- ще линейной сложности. Снова, как в рассматривавшихся задачах, в качестве оценки сложности получили рекуррентное уравнение (2.17). Как и рань- ше, просто угадаем решение этого уравнения, доказав догадку с помощью математической индукции. 53 Итак, предположим, что T (n) = 3T (n/2) + kn = n log 2 3 − 2kn. Наше предположение легко доказывается по индукции. Предпо- ложим, что T (n) = 3T (n/2) + kn = 3 (n/2) log 2 3 − 2kn/2 + kn верно, тогда, раскрывая скобки, получим T (n) = n log 2 3 − 2kn, что и требовалось доказать. Таким образом, применение декомпозиции позволяет добиться уменьшения сложности умножения с O(n 2 ) до O(n 1.6 ). Существу- ют и другие способы быстрого умножения чисел, важно помнить, что в быстрых алгоритмах оценивается асимптотика сложности. В реальной ситуации коэффициенты, отбрасываемые и не учи- тываемые в асимптотическом анализе, могут сыграть решающую роль. Другим примером является задача, решение которой может быть основано на методе композиции. Задача 2.14 (коды, сохраняющие разность). Для заданных це- лых чисел L, 2n, t построить отображение множества целых чисел i ∈ {0, . . ., L − 1} в двоичные векторы {a i } длины 2n такое, что 1. d(a i , a j ) = |i − j|, если |i − j| ≤ t, 2. d(a i , a j ) > t, если |i − j| > t. Решение. Отображение, которое требуется построить по усло- вию задачи, уже рассматривалось. Определение 1.5 и называ- лось кодами, сохраняющими разность. Ранее использовались ко- ды, сохраняющие разность для экономного хранения информа- ции в задаче сравнения объекта с эталонным. Использование ко- да, сохраняющего разности, позволило обеспечить выигрыш по 54 сложности по сравнению с традиционными алгоритмами реше- ния указанной задачи. Однако не обсуждался вопрос о постро- ении (N, n, t)-кодов, сохраняющих разности. Приведен был при- мер (8, 4, 1)-кода, оставив вопрос о том, какие значения могут принимать величины N , n, t. Задача построения кодов с боль- шими значениями N является трудной, а вопрос о максимизации N при фиксированных значениях n и t остается открытым. В дальнейшем применим метод композиции для того, чтобы на базе имеющихся (N, n, t)- и (M, n, t)-кодов получить (L, 2n, t)-код, где L > M + N . Пусть A 1 , A 2 , . . ., A N — слова (N, n, t)-кода A, а B 1 , B 2 , . . ., B M — слова (M, n, t)-кода B. Произведем композицию слов этих кодов по следующему правилу: A 1 B 1 , A 1 B 2 , . . . , A 1 B M , A 2 B M , A 3 B M , . . . , A N B M , A N B M −1 , A N B M −2 , . . . , A N B 1 , A N −1 B 1 , A N −2 B 1 , . . . , A t B 1 , (2.18) где A i B j — последовательность длины 2n, составленная из n сим- волов слова A i и n символов слова B j Композиция (2.18) составлена следующим образом: по очереди фиксировали слова кода A и B и последовательно приписывали слова кода B и A соответственно. Нетрудно видеть, что при таком выписывании слова A i B j сохраняют разности, не превышающие t. Выписывание слов в коде (2.18) заканчивается словом A t B 1 , так как следующее слово A t−1 B 1 , номер которого отличается от номера слова A 1 B 1 в последовательности (2.18) более, чем на t, отличается от слова A 1 B 1 в t−1 позициях и значит не может быть словом кода, сохраняющего до t. Составлена композиция двух кодов, сохраняющих разности. Оценим теперь число слов в полученном (L, 2n, t)-коде. Положим, что осуществляем композицию двух одинаковых кодов длины n, сохраняющих разности до t. Число слов в этом коде обозначим че- рез R(n). Тогда число слов в полученном с помощью композиции коде равно R(2n) и может быть оценено сверху неравенством R(2n) < 4R(n). (2.19) 55 Функция R(n), удовлетворяющая неравенству (2.19), не пре- вышает функцию, которая при увеличении аргумента вдвое уве- личивается в 4 раза: R(n) < cn 2 , (2.20) где c — некоторая константа, которая определяется из параметров начального кода. В коде (2.18) сохраняется большое число разностей, больших, чем t, поэтому можно попробовать улучшить полученный код. Произведем другую композицию кодов A и B. Будем использо- вать следующее правило композиции: A 1 B 1 , A 1 B 2 , . . . , A 1 B M , A 2 B M , A 3 B M , . . . , A t+1 B M , A t+2 B M , A t+2 B M −1 , . . . , A t+2 B 1 , A t+3 B 1 , A t+4 B 1 , . . . , A 2t+2 B 1 , A 2t+3 B 1 , A 2t+3 B 2 , . . . , A 2t+3 B M , A 2t+4 B M , A 2t+5 B M , . . . , A 3t+3 B M , (2.21) Например, будем строить композицию двух одинаковых (5, 3, 1)- кодов A 1 = B 1 = 000, A 2 = B 2 = 001, A 3 = B 3 = 011, A 4 = B 4 = 111, A 5 = B 5 = 110. Тогда с помощью (2.21) получим (17, 6, 1)-код 000 000 011 110 110 000 000 001 011 111 110 001 000 011 011 011 110 011 000 111 011 001 110 111 000 110 011 000 110 110 001 110 111 000 56 В каждой строке в коде (2.21) записано (M + t) слов, а число строк в (2.21) равно N/(t + 1) . Оценим полученную декомпози- цию, используя один (R(n), n, t)-код. Тогда R(2n) = (R(n) + t) × R(n)/(t + 1) > 1 t + 1 R 2 (n). (2.22) Функция R(n), удовлетворяющая (2.22) — это функция, кото- рая при увеличении аргумента вдвое растет, как квадрат: R(n) = c · 2 αn , (2.23) где c, α — некоторые константы. Величину c можно определить, подставив функцию (2.23) в уравнение (2.22) c · 2 2αn = 1 t + 1 (c · 2 αn ) 2 , откуда c = (t + 1), и R(n) = (t + 1)2 αn Константа α определяется из параметров исходного кода. Возьмем в качестве исходного кода (8, 4, 1)-код, приведенный в подразд. 1.2. Тогда R(4) = (1 + 1)2 4α = 8, откуда α = 1/2, и R(n) = 2 · 2 n/2 Таким образом, получили новую композицию, существенно бо- лее эффективную, чем заданную правилом (2.18). 2.5. Эвристические алгоритмы Рассмотрим подкласс алгоритмов, которые, хотя и не всегда дают оптимальное решение, тем не менее широко используются на практике. 57 Определение 2.7 Эвристический алгоритм — основанный на опыте или неких интуитивных предположениях метод решения задачи, дающий, как правило, хороший результат. Данное определение эвристического алгоритма содержит мно- го неконкретных понятий и в этом заключается особенность эв- ристики. Эвристическими могут называться и алгоритмы, кото- рые не могут быть полностью проанализированы, не доказана их сложность или оптимальность, но из опыта или из общих рассуж- дений и предположений известно, что они дают хорошее прибли- жение к требуемому результату. Что считать хорошим результа- том, зависит от конкретной задачи, условий и ограничений. Подразумевается, что эвристический алгоритм обладает не- большой, реализуемой сложностью, и это компенсирует возмож- ную неточность результата. К примеру, для задачи коммивояже- ра, которую рассматривали в подразд. 2.1, предложен способ ре- шения «полным перебором», имеющий сложность порядка O(n!). С помощью этого метода всегда находим оптимальный путь, пла- тя за это большой трудоемкостью, которая явно нереализуема уже на величинах n порядка нескольких десятков. В то же время легко указать эвристический способ нахожде- ния маршрута, не обязательно оптимального (можно построить примеры, когда этот способ не будет находить кратчайший объ- езд), но, как правило, достаточно короткого. Этот способ назы- вается «правилом ближайшего соседа» и, как следует из назва- ния, заключается в том, чтобы из каждого города все время вы- езжать в ближайший непосещенный город. Такие методы называ- ются иногда «жадными», так как они всегда выбирают локаль- ный оптимум, стараясь достичь глобального. Очевидно, слож- ность правила ближайшего соседа составляет O(n 2 ) (для каждо- го из n городов нужно выбрать выезд минимальной стоимости из n − 1 направлений), что значительно меньше, чем сложность пол- ного перебора. Для этого примера метод ближайшего соседа дает объезд ABCDA со стоимостью 15, т.е. в данном случае получен- ный объезд совпадает с оптимальным. Однако можно привести 58 примеры, в которых применение данного метода будет неопти- мально. Для следующей задачи также может быть получен про- стой эвристический алгоритм. Задача 2.15 (задача о расписании процессоров). Пусть нам да- ны n параллельных (одинаковых по производительности) процес- соров P 1 , P 2 , . . ., P n , и m заданий I 1 , I 2 , . . . , I m , где время выпол- нения каждого задания на любом из процессоров известно и со- ставляет T 1 , T 2 , . . . , T m . Требуется составить расписание, распре- деляющее задания по процессорам так, чтобы время выполнения всех заданий было минимальным. Решение. Можно легко видеть, что различные расписания приводят к различному времени выполнения всех задач. Рассмот- рим пример для трех процессоров P 1 , P 2 , P 3 и четырех заданий I 1 , I 2 , I 3 , I 4 со временем выполнения T 1 = 10, T 2 = 8, T 3 = 2, T 4 = 3. Предположим, что задания стоят в очереди, при этом освободив- шийся процессор берет первое задание в очереди для обработки. Если одновременно свободны несколько процессоров, они берут задания в порядке своих номеров. Таким образом, расписание может быть задано просто после- довательностью заданий I j 1 , . . . , I j m , и, следовательно, можно за- дать m! различных расписаний. Например, подавая задания в по- рядке I 4 , I 3 , I 2 , I 1 , т.е. первый процессор берет четвертое зада- ние, второй — третье и т.д., получим время выполнения, равное 12 (рис. 2.17, а). Очевидно, такое расписание неоптимально: пока одним процессором обрабатывается задание со временем выпол- нения 10, остальные два успеют обработать оставшиеся задания (рис. 2.17, б ). Расписание, изображенное на рис. 2.17, б, является оптимальным, так как время обработки всех заданий не может быть меньше, чем время обработки самого трудоемкого задания. Расписание на рис. 2.17, б дает именно такое время, т.е. — 10. Однако для перебора всех возможных расписаний, как и в за- даче коммивояжера, требуется решать задачу экспоненциальной сложности. Эвристический подход, который сформулируем, весь- ма прост: будем считать расписанием последовательность I j 1 , I j 2 , . . ., I j m такую, что T j 1 ≤ T j 2 ≤ . . . ≤ T j m , отсортированную по 59 10 8 3 2 12 T T T P 1 P 2 P 3 I 1 , I 2 , I 3 , I 4 I 1 I 2 I 3 I 4 10 8 2 3 10 T T T P 1 P 2 P 3 I 1 I 2 I 4 I 3 I 3 , I 4 , I 2 , I 1 а) ) Рис. 2.17. Задача о расписании процессоров: а – произвольное расписание; б – оптимальное расписание 60 10 8 2 3 10 T T T P 1 P 2 P 3 I 1 I 2 I 4 I 3 I 3 , I 4 , I 2 , I 1 Рис. 2.18. Эвристическое расписание 5 5 5 12 T T T P 1 P 2 P 3 4 4 4 3 5 5 5 11 T T T P 1 P 2 P 3 4 4 4 3 а) ) Рис. 2.19. Проигрыш эвристического алгоритма: а – эвристи- ческое расписание; б – оптимальное расписание времени обработки. Такое расписание изображено на рис. 2.18. В данном случае время обработки расписания, полученного эври- стическим путем, снова совпадает с оптимальным и дает общее время обработки — 10. Однако легко указать пример, для которого эвристическое рас- писание не даст оптимального решения. Такой пример приведен на рис. 2.19. Можно доказать, что если обозначить через T 0 оптимальное время обработки, а через T э — полученное с помощью описанного 61 эвристического алгоритма, то T э /T 0 ≤ 4/3. Таким образом, не только сформулирован эвристический алго- ритм, но и в некотором смысле оценена его эффективность отно- сительно оптимального, т.е. получена оценка максимального про- игрыша. 2.6. Контрольные задачи 1. Какое наименьшее количество клеток нужно вырезать из доски 8 × 8, чтобы в оставшейся части нельзя было разме- стить ни одной фигуры вида 2. Из 30 спичек двое игроков берут по очереди по своему усмот- рению от 1 до 3 спичек. Проигрывает тот, кто берет послед- нюю спичку. Разработать алгоритм игры первого игрока. 3. Имеется квадратная таблица, заполнения числами. Допу- стимы операции, состоящие в изменении знака всех чисел в столбце или строке. Можно ли добиться того, чтобы сумма во всех строках и столбцах преобразованной таблицы стала неотрицательной? 4. У каждого члена клуба не более, чем два врага. Разделить клуб на три компании так, чтобы ни в одной компании не было врагов. |