Трудоемкость алгоритмов

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

Рассмотрим наглядный пример. Пусть требуется найти кратчайший путь на графе из 30 вершин, в котором каждая вершина связана со всеми другими. Для решения этой задачи часто используют алгоритм Дейкстры, трудоемкость которого пропорциональна N², где N – количество вершин графа. В математике для этого случая принято обозначение O(N²).

Попробуем найти кратчайший путь перебором всевозможных путей, что проще всего реализуется поиском в глубину. Ограничимся для простоты только путями, включающими все вершины графа. Поскольку в промежутке между начальной и конечной вершинами могут в различном порядке находиться 28 вершин, то таких путей 28! Эта величина превышает 1029. Будем считать, что мы в состоянии находить и оценивать 109 путей в секунду (реально значительно меньше). Значит, нам потребуется 1020 секунд для просмотра всех путей. В сутках менее 105 секунд, а в году менее 500 суток, то есть поиск займет более 2´ 1012 лет. И это при том, что мы рассматривали только самые длинные по числу вершин пути! Нас не спасет даже компьютер, работающий в 1000 раз быстрее.

Можно возразить, что кратчайший путь не должен включать так много промежуточных вершин. Но термин " длина” в задачах поиска путей на графе используется в обобщенном смысле. Например, речь может идти о стоимости самолетных сообщений. Легко вообразить, что перелеты на короткое расстояние совершают маленькие самолеты, билеты на которые обходятся дешевле.

В первую очередь оценивают зависимость трудоемкости вычислений от размерности исходных данных N. Переборные алгоритмы имеют обычно экспоненциальную трудоемкость, то есть объем вычислений оценивается как O(Exp(N)). Такие алгоритмы реализуемы только при ограниченных значениях N. Полиномиальные алгоритмы имеют оценку O(NP), где P> 0.

Величина коэффициента пропорциональности отступает на второй план в тех случаях, когда размерность велика. Сравним, например, два алгоритма с трудоемкостью 0.1´ N2 и 100´ N. При N < 1000 первый алгоритм эффективнее. Но при N = 105 второй алгоритм в 100 раз быстрее первого.

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

Часто высокая скорость работы достигается путем использования рациональных структур данных. Так быстрый поиск информации в современных системах управления базами данных основан на Б-деревьях и хеш-таблицах.

Строки

Строки являются одной из самых распространенных структур данных. Битовые строки соответствуют числам. Строки цифр образуют телефонные номера, строки символов – слова. Из слов состоят фразы, из фраз – документы и книги.

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

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

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

Поставим сначала задачу в несколько упрощенном виде.

Поиск подстроки. Заданы две последовательности символов. Нужно определить все вхождения первой из них (назовем ее образец) во вторую (текст).

Ввод из файла INPUT.TXT. Первая строка файла является образцом и имеет длину от 1 до 255. Вторая строка является текстом и имеет длину от 1 до 2´ 109.

Вывод в файл OUTPUT.TXT. Вывести через пробел последовательность номеров позиций в тексте, начиная с которых в него входит образец. Нумерация начинается с 1. Если вхождений нет, вывести No.

Пример

Ввод

AA

AAABAA

Вывод

1 2 5

Из условия ясно, что образец можно запомнить в массиве символов, а текст – нельзя. Однако сначала для удобства предположим, что и образец, и текст хранятся в массивах P и T соответственно. Пусть M – длина образца, N – длина текста (M ≤ N).

Иногда требуется найти только первое вхождение образца. Дополнительным условием может быть отсутствие пересечений находимых подстрок текста.

Самое очевидное решение – сравнить образец с каждой из подстрок длины M, начинающихся в позициях 1, 2, …, N – M + 1. Такой алгоритм носит название последовательного или прямого [9]. Общее количество сравнений символов оценивается величиной O(M(N-M+1)). При заданных размерностях трудоемкость алгоритма допустима, но с ростом M и N быстро растет. Большинство сравнений в действительности лишнее. Например, если в каком-то многомегабайтном файле будет искаться последовательность длиной 100 Кб, то придется ждать очень долго.

Алгоритм Рабина [9] представляет собой модификацию линейного алгоритма. Он основан на весьма простой идее. Вырежем " окошечко" размером M и будем двигать его по тексту. Нас интересует, не совпадает ли слово в " окошечке" с заданным образцом. Сравнивать по всем буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины M. Тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в " окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам. Ошибка: источник перёкрестной ссылки не найден

Этот алгоритм выполняет линейный проход по образцу (M шагов) и линейный проход по всему тексту (N шагов), стало быть, общее время работы есть O(M+N). При этом мы не учитываем временную сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма. Тогда время работы алгоритма линейно зависит от размера строки и текста, значит, программа работает быстро. Вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые ”напоминают” образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будем использовать функциюHash, которая должна:

· легко вычисляться;

· как можно лучше различать несовпадающие строки;

Hash(T[i+1, i+m]) должна легко находиться по Hash(T[i, i+m-1]).

Во время поиска будем сравнивать Hash(P) с Hash(T[i, i+M-1]) для i от 1 до N-M+1 включительно. Если обнаруживаем совпадение, то проверяем посимвольно.

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

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

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

Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число C фиксировано, а S и T - два различных слова длины M. Тогда им соответствуют различные многочлены. Совпадение значений функции означает, что в точке X эти два различных многочлена совпадают, т.е. их разность обращается в 0. Разность есть многочлен степени M-1 и имеет не более M-1 корней. Таким образом, если M много меньше C, то случайному значению X мало шансов попасть в " неудачную" точку. Строго говоря, время работы всего алгоритма в целом, есть O(M+N+AMN), но значение константы Aдостаточно невелико, так что сложность работы почти линейная.

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

Алгоритм Кнута – Морриса – Пратта (КМП) [3, 9, 10] более полно использует информацию, полученную во время сканирования (алгоритм последовательного поиска ее просто выбрасывает). После сдвига образца по тексту стоит вести сравнение посимвольно. Если не совпал первый символ, нет смысла переходить к следующему. Хотелось бы сдвигать образец так, чтобы обеспечить совпадение максимального числа начальных символов образца и подстроки из «окошка». Оказывается, это можно обеспечить путем предварительного исследования образца. Будем следовать описанию алгоритма в [3], объясняя некоторые этапы.

Пусть в i-й позиции текста отмечено несовпадение с текущим символом образца, а в предыдущих j позициях символы текста и образца совпадают. Иными словами, Pj+1 ≠ Ti, а P1P2... Pj = Ti-jTi-j+1...Ti-1. На какое максимальное число позиций можно сдвинуть образец, не рискуя пропустить его вхождение в текст? Очевидно, нужно найти в позициях текста от i – j + 1 до i -1 максимальное совпадение с началом образца. Но поскольку текст в этих позициях совпадает с символами образца, то это эквивалентно нахождению самого длинного начала образца P1P2...Pk (1< k < j), которое повторяется в оставшейся части образца, т.е. P1P2...Pk = Ps+1Ps+2...Ps+k.

Если сдвинуть образец на s позиций, то мы обеспечим совпадение в позициях текста от i – j + s до i – j + s + k. Докажем, что полное совпадение может быть только в том случае, когда подстрока P1P2...Pk входит как в начало, так и в конец строки P1P2...Pj, т.е. s+k=j. Предположим обратное: после сдвига на s позиций образец полностью совпадает с подстрокой текста и s+k < j, как это показано на рисунке.

В силу полного совпадения, Ti-j+s+k = Pk+1, а поскольку Ti-j+s+k = Ps+k+1, то Ps+k+1 = Pk+1. Мы получили в позициях от 1 до jобразца повторение первых k + 1 начальных символов. Это противоречит выбору самого длинного начала из k символов.

Итак, подстрока P1P2…Pk входит как в начало, так и в конец строки P1P2...Pj. Сдвинем образец сразу на j - k позиций. Поскольку k < j, первые k символов образца и текущего " окошка” совпадут. Это состояние показано на следующем рисунке.

Если Pk+1 = Ti, то можно продолжить сравнение, начиная с символа Ti+1. Если же Pk+1≠ Ti, то снова будем находить самое длинное начало образца P1P2…Pr (1 < r < k), которое повторяется в последних позициях подстроки P1P2...Pk.

Эти свойства образца можно рассчитать заранее. Если для каждой позиции j образца известна максимальная длина f(j) < jначала образца, совпадающая с концом строки P1 P2…Pj, то возможен сдвиг образца вперед на j - f(j) позиций без последующего возврата назад. Отсутствие возвращений в тексте позволяет не запоминать его в массиве.

Функция f(j) называется функцией возвратов. Она показывает, к какому символу Pf(j) нужно возвратиться в образце, когда Pj+1 ≠ Ti. Это эквивалентно сдвигу образца вправо относительно текста на j - f(j) позиций и следующему сравнению Pf(j) с Ti.

Как вычислять функцию возвратов? Очевидно, f(1)=0. Пусть вычислены f(1), …, f(j-1) и f(j-1) = k. Если Pj = Pk+1, то конец строки P1P2...Pj совпадает с ее началом длины k+1, поэтому f(j) = k+1. Если Pj ≠ Pk+1, то «следующим концом» строки может быть подстрока P1P2…Pf(k) Pf(k)+1, поскольку именно P1P2... Pf(k) является самым длинным концом P1P2...Pk образца, совпадающим с его началом. Если и эта строка не годится, то следующей подстрокой может быть P1P2...Pf(f(k))+1 и т. д. Таким образом, или будет найдено начало длины r, при котором P1P2...Pr является концом P1P2…Pj, и тогда f(j) = r, либо такого начала найдено не будет, и тогда f(j) = 0.

Приведем пример. В первой строке содержится текст, во второй – образец, в третьей значения функции возврата

a b a c a b a с a b c a b a c a b a b b

a b a c a b a b

0 0 1 0 1 2 3 2

Ниже представлена последовательность сдвигов. Слева показана разность j - f(j), определяющая величину сдвига, а справа – позиция образца, с которой будет продолжено последующее сравнение с текстом

a b a c a b a a b a b a b a c a b a b b

a b a c a b a b

7-3=4 a b a c a b a b позиция 4

3-1=2 a b a c a b a b позиция 2

1-0=1 a b a c a b a b позиция 1

3-1=2 a b a c a b a b позиция 2

3-1=2 a b a c a b a b позиция 2

Представим образец массивом символов P, функцию возвратов целочисленным массивом F и опишем ее вычисления в следующем фрагменте программы:

k: =0;

F[1]: =0;

For i: =2 to M do

begin

While (k> 0) and (P[i]< > P[k+1]) do k: =F[k];

if P[i]=P[k+1] then k: =k+1;

F[i]: =k;

end;

Обозначим через w(i) количество выполнений тела цикла While при i = 2, 3, …, M. Каждое выполнений тела цикла Whileуменьшает значение k не меньше, чем на 1. Отсюда

F[i] ≤ F[i-1] – w(i) +1, то есть w(i) ≤ F[i-1] – F[i] + 1

Тогда после суммирования w(2) + w(3) +…+ w(M) ≤ M – 1. Общая трудоемкость построения функции возвратов составляет O(M).

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

Program SubString;

Var

P: array[1..255] of char;

F: array[1..255] of integer;

C: char; {очередной символ текста}

pp: integer; {текущая позиция в образце}

tp: integer; {текущая позиция в тексте}

Fin, Fout: text; {входной и выходной файлы}

Begin

{ввод образца, построение массива F:

значений функции возвратов}

pp: =0;

tp: =0;

While not eof(Fin) do

Begin

tp: =tp+1;

Read(Fin, C); {очередной символ текста}

While (pp> 0) and (P[pp+1]< > C) do

pp: =F[pp]; {следующее ‘начало-конец’}

if P[pp+1]=C then pp: =pp+1;

if pp = M then {совпал последний символ образца}

begin

Write(Fout, tp-M+1, ' ');

{позиция первого символа}

pp: =F[pp];

{подготовка к поиску следующего вхождения}

end;

End;

End.

Оценим количество сравнений символов. На каждом шаге внешнего цикла tp увеличивается на 1, а pp увеличивается на 1, а иногда уменьшается как минимум на 1 за счет присваивания F[pp]. Обозначим через b(tp) начальное значение pp при очередном значении tp, а через w(tp) – количество уменьшений pp при одной и той же позиции tp в тексте. Тогда b(tp) ≤ b(tp-1) – w(tp)+1 при tp > 1 или w(tp) ≤ b(tp-1) - b(tp)+1. Отсюда вычисление суммы значений w(i) имеет трудоемкость порядка N. Поскольку tpувеличивается N-1 раз, то общая трудоемкость алгоритма с учетом вычисления функции возвратов составляет O(M+N).

Алгоритм КМП обеспечивает во всех случаях линейную сложность, но не является самым эффективным алгоритмом.

Алгоритм Бойера – Мура [9] имеет нелинейную оценку трудоемкости в худшем случае, но в среднем работает быстрее. Здесь можно провести аналогию с широко известным алгоритмом быстрой сортировки Хоара [1, 3, 5, 7, 11], который имеет квадратичную трудоемкость на специально подобранных данных. Этот алгоритм считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.

Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На первом шаге мы строим таблицу смещений для искомого образца. Процесс построения таблицы будет описан ниже. Далее мы совмещаем начала строки и образца и начинаем проверку с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т. д. При несовпадении очередного символа величина сдвига определяется выражением L - K, где L – значение из таблицы смещений, а K – количество совпавших символов. После сдвига снова начинаем проверку с последнего символа.

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

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

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

Поясним все вышесказанное на простом примере. Пусть у нас есть алфавит из пяти символов: a, b, c, d, e и мы хотим найти вхождение образца abaad в строке abecdacbbdbabaad. Длина образца M = 5. Таблица смещений будет выглядеть так:

a b c d e

1 3 5 0 5

Начало поиска ведется с первой позиции:

a b e c d a c b b d b a b a a d

a b a a d

Последний символ образца совпадает с наложенным символом d строки, а предпоследний нет, то есть K =1. Из таблицы смещений для символа c строки находим L = 5. Сдвигаем образец вправо на L - K = 4 позиции:

a b e c d a c b b d b a b a a d

a b a a d

Последний символ образца не совпадает с символом b строки, значит K =0, а L = 3. Сдвигаем образец вправо на L - K = 3 позиции:

a b e c d a c b b d b a b a a d

a b a a d

Мы добились совпадения подчеркнутых символов. Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на одну позицию:

a b e c d a c b b d b a b a a d

a b a a d

Теперь в соответствии со смещением для символа b из таблицы сдвигаем образец на 3 позиции и получаем искомое вхождение образца:

a b e c d a c b b d b a b a a d

a b a a d

Для кодовой таблицы, состоящей из 256 символов, таблица смещений будет представлять собой массив целых чисел, индексы которого изменяются от 0 до 255 и соответствуют кодам символов. Имеется много модификаций описанного алгоритма [9, 10]. Некоторые из них строятся на основе использования теории конечных автоматов.

Эффективность алгоритма Бойера – Мура в среднем выше по сравнению с алгоритмом КМП, но существенно зависит от длины текста и длины образца. Так при длине строки до 10 символов он показывает себя хуже, даже чем последовательный поиск. Алгоритм КМП менее чувствителен к размерности текста и образца. Его можно использовать как универсальный, когда неизвестны длины строки и образца.

Алгоритм Рабина работает быстрее последовательного, но медленнее КМП, однако простота и малые трудозатраты на реализацию делают его привлекательным для использования в неспециальных программах.

Наихудший результаты показывает алгоритм последовательного поиска. Как и предполагалось, при увеличении длины образца и текста он работает во много раз медленнее остальных алгоритмов.

Мы рассматривали точное совпадение символов образца и текста. Существует много разновидностей неточного поиска [10]. Например, можно не учитывать окончаний слов, искать по нескольким образцам, допускать наличие символов, не принадлежащих образцу и т. п.

Графы

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

В настоящем разделе описываются методы исследования связности графов. Далее рассматриваются процедуры проверки ацикличности и топологической сортировки ориентированных графов. В конце раздела приводится ряд задач, которые не имеют выраженной " графовой” ориентации, но, тем не менее, сводятся к графам. Подобные графы иногда называют скрытыми или неявными.

Приведем некоторые определения.

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

Ориентированный граф связен, если связен неориентированный граф, получающийся путем удаления ориентации ребер.

Ориентированный граф сильно связен, если для каждой пары вершин существуют пути как из первой вершины во вторую, так и из второй вершины в первую.

Максимальный связный подграф называется связной компонентой графа. По аналогии, максимальный сильно связный подграф называется сильно связной компонентой графа.

Связность графа выявляется проще всего обычным поиском в глубину из произвольной начальной вершины. Посещаемые вершины помечаются с тем, чтобы повторно в них не заходить. Если в конце все вершины оказываются помеченными, то граф связен. Поскольку при поиске в глубину каждое ребро проходится только дважды, то общая трудоемкость этого метода составляет O(V+E), где V – количество вершин графа, а E – количество ребер.

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

Выделение сильно связных компонент происходит несколько сложнее. Пусть T – некоторая вершина ориентированного графа. Обозначим через R(T) множество вершин, достижимых из вершины T, а через Q(T) – множество вершин, из которых существует путь в вершину T. Оказывается, что пересечение множеств R(T) и Q(T) вместе с соответствующими дугами является множеством вершин графа, составляющим вместе с инцидентными им дугами сильно связную компоненту [4]. После пометки всех ее вершин можно находить следующие сильно связные компоненты.

Иногда недостаточно знать, что граф связен. Может возникнуть вопрос, насколько " сильно” связан граф. Например, в графе может существовать вершина, удаление которой вместе с инцидентными ей ребрами разъединяет оставшиеся вершины. Такая вершина называется точкой сочленения. Граф без точек сочленения называется двусвязным. Максимальный двусвязный подграф графа называется двусвязной компонентой.

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

Трудоемкость этого метода O(V2+VE). Существует алгоритм выделения точек сочленения и двусвязных компонент с трудоемкостью O(V+E) [1, 8].

Рассмотрим следующую задачу.

Жизнь на Марсе. При высадке на Марс было основано N поселений. Их координаты заданы. Каждое поселение равномерно расширялось во все стороны на L марсианских миль в месяц. Постепенно поселения начали сливаться друг с другом, получая общее название. Какое минимальное время с момента высадки потребуется для того, чтобы на Марсе осталось не более K поселений?

Будем рассматривать граф, соответствующий марсианским поселениям. Если нет совпадающих по координатам поселений, то сначала он состоит только из N вершин. Два поселения соприкоснутся в середине соединяющего их отрезка через время T=D/2L, где D – расстояние между поселениями. Назовем это событие встречей. Будем встречу поселений отмечать ребром графа.

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

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

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

Рекурсия. Имеется программа, состоящая из n процедур P1, P2, …, Pn. Пусть для каждой процедуры известны процедуры, которые она может вызывать. Процедура P называется потенциально рекурсивной, если существует такая последовательность процедур Q0, Q1, …, Qk, что Q0 = Qk = P, k ≥ 2 и для i = 1, …, k–1 процедура Qi-1 может вызвать процедуру Qi. Требуется определить для каждой из заданных процедур, является ли она потенциально рекурсивной.

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

Часто по смыслу задачи граф не должен иметь циклов.

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

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

Эта модель появилась в конце 50-х годов прошлого столетия и легла в основу направления " Сетевое планирование”. Таким образом, например, планировался американский проект пилотируемого полета на Луну. Иногда работам ставят в соответствие не вершины, а дуги графа. Каждый способ имеет свои достоинства и недостатки.

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

Если в графе есть цикл, содержащий некоторую вершину A, то при поиске в глубину с начальной вершиной V обязательно встретится дуга цикла, ведущая в A. С другой стороны, в графе может быть цикл, не содержащий вершины A и такой, что при поиске с начальной вершиной A он не найдется. Значит, для полного исследования графа можно запустить поиск в глубину с каждой вершиной в качестве начальной.

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

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

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

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

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

Нередко формулировка проблемы в терминах теории графов появляется не сразу. Рассмотрим следующую задачу.

Ременная передача. На плоскости расположены N валов. Заданы координаты их центров и радиусы. Некоторые валы связаны ременными передачами. Валы, имеющие общий центр вращения, жестко связаны, то есть имеют одинаковую угловую скорость. Задаваемая система геометрически правильная, то есть валы не пересекаются между собой, а валы, имеющие общий центр вращения, не могут быть соединены ремнем.

Вал с номером M вращается по часовой стрелке со скоростью 1000 оборотов в минуту. Требуется для каждого вала найти его угловую скорость. Необходимо отметить случай, когда заданная система противоречива, то есть на один вал передается вращение от разных источников с разными угловыми скоростями.

Для перехода к графу сопоставим вершинам валы, а ребрам - ременные передачи или жесткое сцепление. Тогда проводя поиск в ширину от начального вала можно рассчитать движение каждого вала.

В следующей задаче также можно использовать графы [11].

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

Вершинам ориентированного графа поставим в соответствие владельцев квартир. Если владельца A устраивает для обмена квартира (квартиры) владельца B, то в графе окажется дугаAB.

Учтем в описанном графе условия и пожелания нового клиента X. Простой обмен сводится к нахождению всех вершин, которые связаны с вершиной X взаимными дугами. Более сложные обмены обеспечивает поиск циклов X - C1 - C2 -…- CK – X. Предполагается, что клиент переедет в квартиру владельца C1, тот в свою очередь переедет в квартиру владельцаC2 и, в конце концов, владелец CK займет квартиру владельца X. Задача может быть существенно усложнена, если допустить, что возможны обмены квартиры на две других, которые могут принадлежать разным владельцам.

Рассмотрим еще одну задачу с применением графов.

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

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

Количество документов, на которые нельзя попасть по ссылкам, начиная с первого документа, можно определить с помощью матрицы достижимости. Эта матрица, называемая также транзитивным замыканием, легко получается с помощью алгоритма Уоршела [1, 11]. По матрице достижимости находится количество вершин, не достижимых из первой вершины.

Иногда в дополнение к графу, который следует из условий задачи, необходимо строить некий модифицированный граф. Рассмотрим подобную задачу.

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

Определенный агент добыл ценные сведения. Резидент решил получить информацию по двум независимым каналам. Требуется найти минимальный размер затрат резидента для оплаты передачи информации по двум цепочкам агентов, которые начинаются с удачливого агента и заканчиваются резидентом, не пересекаясь друг с другом.

Итак, требуется найти на ориентированном взвешенном графе два непересекающихся пути из начальной вершины A в конечную B наименьшей суммарной стоимости.

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

10 9

2 9

2 6 2 1

2 4

Пусть требуется найти два пути минимальной суммарной стоимости из вершины 1 в вершину 3.

Кратчайший путь 1-4-5-3 имеет стоимость 6. Следующим минимальным путем, не пересекающимся с первым, является путь 1-2-3 стоимости 19. Суммарная стоимость двух путей 25. Однако путь 1-5-6-3 стоимости 11 и 1-4-2-3 стоимости 13 имеют суммарную стоимость 24. Более того, путь 1-4-2-3 стоимости 13 и 1-5-3 стоимости 8 имеют суммарную стоимость 21.

Перебор всех путей и выбор лучшей пары из них бесперспективен. Для графа из 30 вершин, в котором все вершины связаны дугами, только количество путей с включением всех вершин равно 28!, что составляет более 1029. А если рассматривать все пути и перебирать пары путей?!

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

Дуга из некоторой первой пары вершин в какую-либо вторую пару при поиске двух путей из A в B описывается следующими правилами:

· в исходном графе есть дуга L, соединяющая одну из вершин первой пары с одной из вершин второй пары;

· две другие вершины из этих пар совпадают;

· два пути, восстановленные в исходном графе из второй пары в обратном направлении к паре вершин (A, A), где A - начальная вершина, не пересекаются;

· стоимостью дуги между парами вершин является стоимость дуги L.

В приведенном примере дуга (1, 1) - (1, 4) имеет стоимость 2, а дуга (2, 5) - (5, 6) – стоимость 9.

Задача сводится к нахождению кратчайшего пути в новом графе из вершины (A, A) в вершину (B, B), где A и B - начальная и конечная вершины исходного графа соответственно. Поскольку стоимости дуг положительны, то удобно применить алгоритм Дейкстры (поиск в ширину кратчайшего пути). В новом графе не более N2 вершин, поэтому общая трудоемкость алгоритма O(N4), что вполне допустимо для заданной в условии размерности графа.

В нашем примере кратчайшим путем будет (1, 1) - (1, 4) - (1, 2) - (2, 5) - (2, 3) - (3, 3) стоимости 21. По этому пути восстанавливаются два пути в исходном графе 1-4-2-3 – стоимости 13 и 1-5-3 – стоимости 8. Суммарная стоимость этих двух путей составляет указанную выше величину 21.

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