Главная Промышленная автоматика.

ГЛАВА 10

Методы разработки алгоритмов

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

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

10.1. Алгоритмы „разделяй и властвуй"

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

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

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



Рис. 10.1. Исходное положение в головоломке "Ханойские башни"

Описанный выше алгоритм, конечно, правильный и, к тому же, весьма лаконичный, правда, нелегко понять, почему он "работает", да и вряд ли такой алгоритм быстро придет вам в голову. Попробуем вместо этого применить метод декомпозиции. Задачу перемешения п наименьших дисков со стержня А на стержень В можно представить себе состояшей из двух подзадач размера п - 1. Сначала нужно переместить п - 1 наименьших дисков со стержня А на стержень С, оставив на стержне А п-й наибольший диск. Затем этот диск нужно переместить с А на В. Потом следует переместить п - 1 дисков со стержня С на стержень В. Это перемешение га - 1 дисков выполняется путем рекурсивного применения указанного метода. Поскольку диски, участвуюшие в пере-мешениях, по размеру меньше тех, которые в перемешении не участвуют, не нужно задумываться над тем, что находится под перемешаемыми дисками на стержнях А, В или С. Хотя фактическое перемешение отдельных дисков не столь очевидно, а моделирование вручную выполнить непросто из-за образования стеков рекурсивных вызовов, с концептуальной точки зрения этот алгоритм все же довольно прост для понимания и доказательства его правильности (а если говорить о быстроте разработки, то ему вообше нет равных). Именно легкость разработки алгоритмов по методу декомпозиции обусловила огромную популярность этого метода; к тому же, во многих случаях эти алгоритмы оказываются более эффективными, чем алгоритмы, разработанные Традиционными методами.

Умножение длинных целочисленных значений

Рассмотрим задачу умножения двух л-битовых целых чисел X w Y. Вспомним, что алгоритм умножения га-битовых (или га-разрядных) целых чисел, изучаемый в средней школе, связан с вычислением п промежуточных произведений размера п и поэтому является алгоритмом О(л), если на каждом шаге выполняется лишь умножение или сложение одного бита или разряда. Один из вариантов метода декомпозиции применительно к умножению целых чисел заключается в разбиении каждого из чисел X и Y на. два целых числа по га/2 битов в каждом, как показано на рис. 10.2. (Для простоты в данном случае предполагается, что гаявляется степенью числа 2.)

1 А

1 В ,

1 С

\ D 1

X = А2"2 + В Г = С2"/ + D

Рис. 10.2. Разбиение п-битовых целых чисел на nJ2 битовые составляющие

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

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



Теперь произведение чисел X и Y можно записать в виде

XY = AC2+(AD+BC)2" + BD. (10.1)

Если будем вычислять произведение XY этим способом, нам придется выполнить четыре умножения (л/2)-битовых целых чисел (АС, AD, ЕС и BD), три сложения целых чисел, содержащих не более 2л битов, и два сдвига (умножение на 2" и 2"). Поскольку сложения и сдвиги требуют 0(п) шагов, можно составить следующее рекуррентное соотношение для Т(га) - общего количества операций с битами, требующегося для умножения га-битных целых чисел по формуле (10.1):

Т{Ц =1,

Т(п)=4Т(п/2) + сп. (10.2)

Используя рассуясдения, подобные приведенным в примере 9.4, можно обосновать в (10.2) значение константы с, равное 1. Тогда управляющая функция d(n) просто равняется п, и однородное и частное решения имеют порядок 0(л").

Если формула (10.1) используется для умножения целых чисел, асимптотическая эффективность будет, таким образом, не больше, чем при использовании метода, которому обучают в средней школе. Не следует, однако, забывать, что для уравнений типа (10.2) мы получаем асимптотическое улучшение в случае, если сокращается количество подзадач. Рассмотрим другую формулу для умножения чисел X и У:

XT = АС2" + 1(А- B)(D - С) +АС + BD]2"-b BD. (10.3)

Несмотря на то что формула (10.3) выглядит сложнее, чем (10.1), она требует лишь трех умножений (л/2)-битовых целых чисел (АС, BD и (A-B)(D-C)), шести сложений или вычитаний и двух сдвигов. Поскольку все эти операции, кроме умножений, выполняются за 0(га) шагов, время Т(п) для умножения л-битовых целых чисел в соответствии с (10.3) задается соотношениями

Т(1)= 1 ,

Т(п) = ЗТ(п/2) + СП . Их решением является Т(п) = 0(п°)= 0(га-*) .

В листинге 10.3 приведен полный код алгоритма, предусматривающий умножение как отрицательных, так и положительных целых чисел. Обратите внимание, что строки (8) - (И) выполняются путем копирования битов, а умножение на 2" и 2" в строке (16) - путем сдвига. Отметим такясе, что в строке (16) результату придается нужный знак.

Листинг 10.1. Алгфэитм умножения целых чисел мет>,компози1Ц1и

function mult ( X, Y, п: integer ) : integer;

{ Хи У - целые числа со знаком < 2". л - степень числа 2. Функция возвращает значение произведения XY }

s: integer; { содержит знак произведения XY } ml, т2, тЗ: integer; { содержат три произведения } А, В, С, D: integer; {содержат левые и правые половины X и Y} begin

(1) s:= sign(X) * sign (У) ;

(2) X:= abs (X) ;

(3) У; = abs(У) ; { теперь Хи У- положительные числа }

(4) if л = 1 then

(5) if (X = 1) and (Y = 1) then

(6) return (s)

else





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 [88] 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0038