Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
121
Добавлен:
28.03.2015
Размер:
1.16 Mб
Скачать

Глава XII

Алгоритмы

В предыдущих главах упоминались задачи теории гра­фов, имеющие важное практическое значение. Особый интерес для приложений представляют алгоритмические-аспекты таких задач. На практике важно уметь с помощью ЭВМ находить в графе наибольшее паросочетание и наи­большее независимое множество, строить гамильтоно» цикл или гамильтонову цепь, выделять связные или дву-связные компоненты и т. п. Иначе говоря, надо иметь соответствующие алгоритмы, а в конечном счете и про­граммы для ЭВМ.

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

Итак, под решением задачи «в алгоритмической поста­новке» мы будем понимать разработку и анализ соответ­ствующего алгоритма.

§ 72. Предварительные сведения

При анализе алгоритма решения какой-либо задачи: нас в первую очередь будет интересовать его трудоем­кость, под которой мы понимаем время выполнения соот­ветствующей программы на ЭВМ. Ясно, что этот показа­тель существенно зависит от типа используемой ЭВМ.

Чтобы сделать наши выводы о трудоемкости алгорит­мов в достаточной мере универсальными, будем считать, что все вычисления производятся на некой абстрактной вычислительной машине. Такая машина в состоянии вы­полнять арифметические операции, сравнения, пересыл­ки и операции условной и безусловной передачи управления. Эти операции считаются элементарными. Каждая из элементарных операций выполняется за единицу вре­мени и, следовательно, время работы алгоритма равно числу выполненных им элементарных операций.

Память абстрактной вычислительной машины состо­ит из неограниченного числа ячеек, имеющих адреса 1, 2, 3, ..., п, ... Ко всем ячейкам есть прямой доступ.

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

Алгоритмы можно описывать в терминах элементар­ных операций. Однако такая запись была бы перегруже­на непринципиальными деталями, заслоняющими основ­ные идеи алгоритма.

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

В записи алгоритма некоторые его фрагменты будут сопровождаться комментариями. Комментируемый фраг­мент может быть отдельным оператором или пунктом, а также группой последовательно расположенных операто­ров либо пунктов. Комментарии будем писать в квадрат­ных скобках и помещать в начале или в конце коммен­тируемого фрагмента.

Хотя мы и условились при описании алгоритмов не ограничивать себя каким-либо набором стандартных опе­раторов, все же два таких оператора будут использовать­ся постоянно. Во-первых — это оператор присваивания а: = В. В результате его выполнения переменная а полу­чает новое значение, равное В. Во-вторых — оператор-«конец», выполнение которого означает прекращение вы­числений.

Рассмотрим теперь представление информации в па­мяти машины. Всякую конечную последовательность эле­ментов произвольной природы будем называть спискомг а число элементов списка — его длиной. Элементами мо­гут быть числа, буквы алфавита, векторы, матрицы и-т. п. В той ситуации, когда каждый элемент списка S по­мещается в одной ячейке (например, является числом), этот список будем размещать в п последовательных ячей­ках памяти, где п — длина списка. Через S(k) будем обозначать kэлемент списка S. Аналогично список S длины п будем размещать в nd последовательных ячей­ках, если для размещения каждого его элемента доста­точно d ячеек. Такое представление списка обычно назы­вается последовательным, и ниже используется только-это представление.

Пусть А = \\Aij\\ — матрица порядка п и А` = (A11, A12, ..., A1n, A21, A22, ..., A2n, ..., An1, An2 ,..., Апп)—список ее элементов «по строкам». Принятый нами принцип «одно число — одна ячейка» означает, что матрица порядка п занимает п2 ячеек памяти.

Рассмотрим теперь представление графа G в памяти машины. Пусть VG = (v1, v2, ..., vn). Будем пользовать­ся тремя способами представления.

Первый — задание графа матрицей смежности. Если граф G взвешенный и w(x, у) обозначает вес ребра ху, то вместо матрицы смежности используется матрица весов W(G)=W. У этой матрицы Wjj= w(vi vj), если vivj EG. Если же vivj ¢ EG, то полагаем Wij = 0 или Wij = ∞ в зависимости от задачи, которую предстоит решить. Из сказанного выше о представлении матрицы в машине следует, что такой способ задания графа требует \G\2 ячеек памяти. В предыдущих главах веса предполагались неотрицательными. Теперь снимем это ограничение и бу­дем считать, что весами ребер могут быть любые вещест­венные числа.

Второй способ — задание графа списком ребер E =1, е2, ..., ет), где т = \EG\, ei EG. Поскольку реб­ро графа можно хранить, используя две ячейки (по одной на каждую концевую вершину), то для хранения все­го списка E достаточно ячеек. Если граф взвешенный, то под каждый элемент списка Е можно отвести три ячейки — две для ребра и одну для его веса, т. е. всего потребуется Зт ячеек.

И, наконец, последний способ, который будет исполь­зоваться,— представление графа списками смежности. При таком способе каждой вершине vi ставится в соот­ветствие список Nvi вершин, смежных с vi. Под этот спи­сок достаточно отвести deg vi + 1 ячеек — по одной на каждый элемент и одну ячейку для обозначения конца списка. Кроме того, формируется список N = (N1, N2, ..., Nn), где Ni — номер ячейки, в которой хранится пер­вый элемент списка Nvi. Следовательно, такой способ представления графа требует ∑(deg v + 1) + п =

v € vg

= 2m + 2п ячеек памяти. Если граф G взвешенный, то для каждой вершины vi, списка Nvi отводится дополни­тельно одна ячейка, содержащая число w(vi ,vj).

Хотя представление графа списком ребер является наиболее экономным «по памяти», оно имеет существен­ный недостаток. Чтобы определить, содержит ли граф данное ребро, надо просматривать поочередно элементы этого списка, а это может потребовать около элемен­тарных операций. Если же граф задан списками смежно­сти, вычислительные затраты составят не более п +• 1 та­ких операций. Представление графа матрицей смежности, требующее наибольших затрат памяти, обеспечивает, как принято говорить, «прямой доступ» к ребрам графа. Уз­нать, содержит ли граф ребро vivj можно, вычислив адрес k= in+j и сравнив М (k) с нулем, где М — мас­сив, в котором построчно размещена матрица смежности графа. Сказанное с очевидными изменениями переносит­ся на случай взвешенных и ориентированных графов.

Выбор того или иного задания графа зависит от кон­кретной задачи, которую предстоит решать.

Во всех рассматриваемых в этой главе задачах глав­ной частью исходной информации служит граф. Кроме этого, исходные данные могут включить номера одной или нескольких выделенных вершин. Если, например, за­дача состоит в отыскании цепи, соединяющей две задан­ные вершины графа, то помимо графа необходимо задать ломера этих двух вершин.

После того как всем исходным данным задачи присвоены конкретные значения и они размещены в памяти ЭВМ, будем называть их входом задачи. Размером (или длиною) входа считается число ячеек, занятых входом. При анализе алгоритма решения любой задачи нас в первую очередь будет интересовать зависимость времени его работы от размера задачи, т. е. от размера входа. Од­нако, как правило, это время зависит не только от размера входа, но и от других параметров задачи, т. е. время работы алгоритма на входах одинаковой длины может быть не одинаковым. Поясним сказанное на простейшем примере. Пусть элементами списка S = (s1, s2, ..., sm) яв­ляются натуральные числа и требуется определить, со­держит ли S число, кратное трем. Очевидный алгоритм решения этой простой задачи состоит в следующем: про­веряем поочередно делимость элементов списка S на 3 до тех пор, пока не встретится число sp, кратное трем, или же не будут проверены все элементы S. Время вы­полнения р таких проверок равно t = 2p (p делений и р изменений адреса). Следовательно, при неизменной дли­не входа т время работы алгоритма будет изменяться в пределах 2 ≤ t в зависимости от расположения под­ходящего элемента sp в списке S. Наихудшим, очевидно, будет случай, когда S не содержит чисел, кратных трем, либо когда sm — единственное такое число. Один из ос­новных подходов к определению понятия «трудоемкость алгоритма» ориентируется именно на такого рода наи­худший случай.

Определим трудоемкость (или сложность) алгоритма решения данной задачи как функцию f, ставящую в соот­ветствие каждому натуральному числу п время работы f(n) алгоритма в худшем случае на входах длины п. Ина­че говоря, f(n)—максимальное время работы алгоритма по всем входам данной задачи длины п. Анализ эффек­тивности каждого из представленных в последующих па­раграфах алгоритмов заключается в выяснении вопроса: как быстро растет функция f(n) с ростом п? При ответе на этот вопрос обычно используют O-символику.

Будем говорить, что неотрицательная функция f(n) не превосходит по порядку функцию g(n), если сущест­вует такая константа с, что f(n)< cg(n) для всех п 0; при этом будем писать f(n) = O(g(n)). Часто встречаю­щемуся далее выражению «трудоемкость (сложность) алгоритма есть (равна, составляет) O(g(n))» придается именно этот смысл. В частности, трудоемкость 0(1) означает, что время работы соответствующего алгоритма не зависит от длины входа. Иногда вместо «трудоем­кость алгоритма есть O(g(n))» будем говорить «алгоритм решает задачу за время O(g(n))».

Алгоритм с трудоемкостью О (п), где п — длина входа, называют линейным. Линейный алгоритм ограниченное (константой) число раз просматривает входную информа­цию и для подавляющего большинства «естественных» задач является неулучшаемым (по порядку) в смысле трудоемкости. Поэтому отыскание линейного алгоритма для некоторой задачи часто является своего рода «послед­ней» точкой» в ее алгоритмическом решении.

Алгоритм, сложность которого равна О(пс), где с — константа, называется полиномиальным. Особая роль полиномиальных алгоритмов выяснится в § 78. Здесь заме­тим, что все задачи, считающиеся трудными для алгорит­мического решения, не имеют в настоящее время полино­миальных алгоритмов. Более того, понятие «полиномиаль­ный алгоритм» является сейчас наиболее распространен­ной формализацией интуитивного представления об эф­фективном алгоритме. Эта формализация, как и любая другая, не свободна от недостатков. Так, например, едва ли кто решится назвать эффективным алгоритм, время работы которого на входе длины п составляет n100. Тем не менее отмеченный недостаток не столь серьезен, как это может показаться на первый взгляд. На практике дело обстоит таким образом, что появление полиномиального алгоритма решения какой-либо задачи приводит в конце концов к алгоритму, трудоемкость которого оценивается сверху полиномом небольшой степени. В большинстве случаев эта степень не превосходит трех и оценка, как правило, имеет один из следующих видов: О(п3), О(п2), О(п√n), O(nlogn), О(п).

Представленные в последующих параграфах алгорит­мы используют две важные структуры данных. Это — списки, в которых удаление элементов и включение но­вых элементов производится специальным образом.

Список S назовем стеком, если удаление и добавление элементов производится с одного конца. Выполнение этих операций осуществляется с помощью переменной t — адреса (указателя) первой ячейки, занятой последним элементом списка S. Если каждый элемент занимает d ячеек, то для удаления элемента из стека достаточно «передвинуть указатель», т. е. выполнить одну элемен­тарную операцию t := td. Включение какого-либо эле­мента а в стек S — это выполнение двух элементарных операций: t:— t + d, S(t):=a. Стек S пуст, если t<l, где l — адрес первой ячейки S.

Пусть, например, каждый элемент стека S = (s1, s2, s3 , s4 , s5) занимает одну ячейку. Рассмотрим последователь­ность операций (*, *, s7, s8, *, s9), где «*» означает уда­ление элемента из S, a «si»—добавление элемента si к S. Тогда S изменяется следующим образом: (s1, s2, s3 , s4), t = 4; (s1, s2, s3 ), t = 3; (s1, s2, s3 , s7), t = 4; (s1, s2, s3 , s7, s8), t = 5; (s1, s2, s3 , s7), t = 4; (s1, s2, s3 , s7, s9), t = 5.

Список Q называется очередью, если все удаления элементов из этого списка производятся с одного конца Q, а добавления — с другого. Эти операции выполняются с помощью двух указателей l и t. Переменная t имеет тот же смысл, что и в предыдущем случае, а переменная l — это адрес первой ячейки очереди Q. Удаление элемента заключается в выполнении операции l:=l + d, а добав­ление производится точно так же, как и в случае стека. Пусть, например, Q=(q1 , q2 , q3, q4, q5) и последователь­ность производимых над Q операций имеет вид (*, q6 , *, * , q7, *). Тогда результаты выполнения этих операций выглядят так: (q2 , q3, q4, q5), l = 2, t = 5; ( q2 , q3, q4, q5, q6 ) l = 2, t = 6; (q3, q4, q5, q6), l = 3, t = 6; (q4, q5, q6), l = 4, t =6; (q4 , q5 , q6,, q7), l = 4, t = 7; (q5 , q6 , q7), l = 5, t = 7.

Описывая алгоритмы, мы, как правило, не указываем в явном виде механизм изменения стека или очереди. Вместо этого просто пишем «занести х в стек S (в оче­редь Q или «исключить х из стека S (из очереди Q)». Очевидно, что каждая из перечисленных операций вы­полняется за время O(1).

Будем считать, наконец, что вершины графа G, к ко­торому применяется алгоритм, занумерованы числами 1, 2, ..., |G|. Это — имена вершин, и в процессе работы алгоритма они не меняются, хотя при этом вершинам мо­гут присваиваться и другие, дополнительные номера (метки).

Соседние файлы в папке Emelichev_V_A_Melnikov_O_I_Sarvanov_V_I_T