В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 59
Текст из файла (страница 59)
Один нз основных подходов к определению пошггия «трудоемкость алгоритма» ориентируется именно на такого рода наихудший случай. Определим трудоемкость (или слоя«ность) алгоритма решения данной задачи как функцию /, ставящую в соответствие каждому натуральному числу и время работы 1(п) алгоритма в худшем случае па входах длины и. Иначе говоря, 1'(и) — максимальное время работы алгоритма по всем входам данной задачи длины п. Анализ эффективности каждого из представленных в последующих параграфах алгоритмов заключается в выяснении вопроса: как быстро растет функция 1'(и) с ростом пу При ответе на этот вопрос обычно используют О-символику.
Будем говорить, что неотрицательная функция 1'(и) не превосходит по порядку функцию д(п), если существует такая константа с, что Яп) < сд(п) для всех и ~ О; при этом будем писать ((п)=0(у(п)). Часто встречающемуся далее выражению «трудоемкость (сложность) алгоритма есть (равна, составляет) 0(д(п))» придается именно этот смысл.
В частности, трудоемкость 0(1) означает, что время работы соответствующего алгоритма 21 в. м нмелкче» и яр. 321 не зависит от длины входа. Иногда вместо «трудоемкость алгоритма есть 0(у(п))» будем говорить «алгоритм решает задачу за время 0(а(н))». Ллгоритм с трудоемкостью 0(п), где п — длина входа, называют линейным. Линейный алгоритм ограниченное (константой) число раз просматривает входную информацию и для подавляющого большинства «естественных» задач является пеулучшаемым (по порядку) в смысле трудоемкости.
Поэтому отыскание линейного алгоритма для некоторой задачи часто является своего рода «последней точкой» в ое алгоритмическом решопии. Ллгорнтм, слоя«ность которого равна 0(п'), где с— константа, называется полиномиальным. Особая роль полнномиальпых алгоритмов выяснится в З 78.
Здесь заметим, что все задачи, считающиеся трудными для алгоритмического решения, пе имеют в настоящее время полиномнальных алгоритмов. Более того, понятие «полипомиальный алгоритм» является сейчас наиболее распространенной формализацией интуитивного представления об эффективном алгоритме. Эта формализация, как и любая другая, пе свободна от недостатков. Так, например, едва ли кто решится назвать эффективным алгоритм, время работы которого на входе длины п составляет и'«». Тем пе менее отмеченный недостаток пе столь серьезен, как зто может показаться на первый взгляд.
На практике дело обстоит таким образом, что появление полиномиального алгоритма решения какой-либо задачи приводит в конце копцов к алгоритму, трудоемкость которого оценивается сверху полиномом небольшой степени. В большинстве случаев зта степень не превосходит трех и оценка, как правило, имеет один из следующих видов: 0(п»), 0(п'), 0(нУп), 0(п )сап), 0(и). Представленные в последующих параграфах алгоритмы используют две важные структуры данных.
Это— списки, в которых удаление элементов и включение новых элементов производится специальным образом. Список Я назовем стеком, если удаление и добавление элементов производится с одного конца. Выполнение этих операций осуществляется с помощью переменной адреса (указателя) первой ячейки, занятой последним элементом списка Я. Если каждый элемент занимает г» ячеек, то для удаления элемента пз стека достаточно «передвинуть указатель», т.
е. выполнить одну элементарную операцию ~:=2 — «(. Включение какого-либо элемента а в стен Я вЂ” это выполнение двух элементарных 322 операций: ~:=~+3, о'(«):-а. Стек Я пуст, если ~<«, где ( — адрес первой ячейки Ю. Пусть, например, каждый элемент стека Я =(зп гг, гг, з«, з«) занимает одну ячейку. Рассмотрим последовательность операций (», ~, ап зг, », з»), где «+» означает удаление элемента из Я, а «г,» — добавление элемента з,к Я.
Тогда Я изменяется следующим образом: (зп гг, гг, г«), »=4; (гн зг, з»), ~ 3; (зп зг, зг, гт)»=4; (зп гг, зъ гт, гв), « = 5; (зп зг, зз, з»Л з = 4; (зн зг, зъ гп зг), » = 5. Список ч называется очередью, если все удаления элементов из этого списка производятся с одного конца ф а добавления — с другого. Эти операции выполняются с помощью двух указателей» и й Переменная» имеет тот же смысл, что и в предыдущем случае, а переменная 1— это адрес первой ячейки очереди Ч. Удаление элемента заключается в выполнении операции »:= ( + д, а добавление производится точно так же, как и в случае стека. Пусть, например, ч =(дн ог, о», о«, д») и последовательность производимых над Ч операций имеет вид (г, д«, », ", оп в).
Тогда реаультаты выполнения этих операций выглядят так: (дг, д», д«, д«), ( = 2, « = 5; (ог, дг, я«, д«), »=2, «=6; (д», д«, д«, д«), »=3, «=6; (д«, д«, д«), 4, «6; (7«, д«, д«, ут), (=4, «=7; (д», д«, дт), »=5, 8=7. Описывая алгоритмы, мы, как правило, не указываем в явном виде механизм изменения стека или очереди.
Вместо этого просто пишем «занести х в стек Я (в очередь ~)» или «исключить х из стека Я (из очереди Ч)». Очевидно, что каждая из перечисленных операций выполняется за время 0(1). Будем считать, наконец, что вершины графа 6, к которому применяется алгоритм, занумерованы числами 1, 2, ..., ! «!. Это — имена вершин, и в процессе работы алгоритма они не меняются, хотя при этом вершинам могут присваиваться н другие, дополнительные номера (метки). й 73.
Поиск в глубину В этом параграфе рассматривается один из методов обхода всех вершин и ребер графа. Этот метод, именуемый поиском е глубину (сокращенно ПГ), послужил основой для разработки ряда быстрых алгоритмов на графах. Один из таких алгоритмов — алгоритм выделения двусвязных компонент графа — приводится в з 74. 21* 323 Дадим вначале некоторые определения. Ориентированный граф Р=((т, А) назовем ориентированным деревом с корнем т ы '»т, если каждая его вершина достижима из т и основание графа Р— граф Р, — является деревом. В тех случаях, когда недоразумение исключено, ориентированное дерево с корнем г будем называть просто деревом.
Пусть 6 — неориоптирова>п>ый связный граф. В процессе поиска в глубину вершинам графа С присванваются номера (11Г-номера), а его ребра помечаются. В начале ребра не помечены, вершины не имеют ПГ-номеров. Начинаем с произвольной вершины и». Присваиваем ей ПГ-номер ПГ(и«) = 1 и выбираем произвольное ребро и»и>. Ребро изю помечается как «прямое», а вершина и> получает (из из) ПГ-номер ПГ(и>)= 2.
После этого переходим в вершину и>. Пусть в результате выполнения нескольких шагов этого процесса пришли в вершину х, и пусть >« — последний присвоенный ПГ-номер. Далее действуем в зависимости от ситуации следующим образом.
1. Имеется непомеченное ребро ху. Если у вершины у уже есть ПГ-номер, то ребро ху помечаем как «обратное» и продолжаем поиск непомеченного ребра, инцидептного вершине х. Если же вершина у ПГ-номера не имеет, то полагаем ПГ(у)= й+ 1, ребро ху помечаем как «прямое» и переходим в вершину у. Вершина у считается получившей свой ПГ-номер из вершины х. На следующем шаге будем просматривать ребра, инцидентные вершине у. 2. Все ребра, инцидентныо вершине х, помечены. В этом случае возвращаемся в вершину, из которой х получила свой ПГ-номер. Процесс закончится, когда все ребра будут помечены и произойдет возвращение в вершину ио. Описанный процесс можно реализовать так, чтобы время работы соответствующего алгоритма составляло о(Иа+ !Р~). Такой алгоритм (алгоритм,М>) мы сейчас рассмотрим.
Пусть граф 6 задан списками смежности, т. е. ˄— список вершин, инцидентных вершине и, и из — исходная вершина, с которой начинается поиск. В процессе работы алгоритма каждая вершина графа ровно один раз включается в список ~ и исключается из него. Вершина включается в этот список сразу после получения ПГ-номера, и исключается, как только произойдет возвращение нз этой вершины. Включение и исключение вершин производятся всегда с конца списка, т.
е. (> — стек. Результат 324 работы алгоритма — четыре списка ПГ, Г, Т и В: ПГ(п) — ПГ-номер вершины щ Е(и) — имя вершины, из которой вершина и получила свой ПГ-номер; Т и В— соответственпо списки ориентированных «прямых» и «обратных» ребер графа 6. Эти ребра получают ориентациго в процессе работы алгоритма,Мь Именно, если ребро ху помечается из вершины х как «прямое», то в Т заносится дуга (х, у), а если — как «обратное», то эта дуга заносится в В. Алгоритм .»»1 поиска в глубину в пеориентировапном свяаном графе. 1.
ПГ(п»):= 1, 0(1):= и«, Р(из):= О, Т:= 8, В:= З', й:= 1, р:= 1 [й — последний присвоенный ПГ-номер, р — указатель конца стека 0, т. е. (»(р) — имя последней вершины стена Я. 2. и:= 0(р) [и — исследуемая вершина). 3. Просматривая список Л'„, найти такую вершину и~, что ребро ии не помечено, и перейти к п. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
