Введение (стр. 1 )

Введение

В данном пособии приводятся дополнительные материалы по дисциплине “Структуры и алгоритмы обработки данных”, которые не изучались в основном курсе и редко упоминаются в других учебных курсах. Ряд задач носит олимпиадный характер, но значение рассматриваемых подходов шире. Практика показывает, что студенты значительно лучше преуспевают в технике программирования, а не в разработке рациональных алгоритмов. Общими недостатками является неумение оценить объем вычислений, сравнить различные подходы к решению задачи, выбрать подходящие структуры данных, провести полное и грамотное тестирование программы.

Основными показателями эффективности являются трудоемкость алгоритмов и затраты оперативной памяти при их программной реализации. В первую очередь оценивают зависимость этих показателей от размерности исходных данных N. В математике пропорциональность какого-либо показателя величине F(N) принято обозначать O(F(N)).

Часто рациональные структуры данных позволяют без особых затруднений обойтись затратами памяти O(N). В этом случае основное внимание уделяют оценке трудоемкости.

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

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

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

Это не так. Рассмотрим наглядный пример. Пусть требуется найти кратчайший путь между двумя заданными вершинами на графе из 30 вершин, каждая из которых связана со всеми другими. Такой граф трудно считать большим. Как известно из начальной части курса [15], для решения этой задачи часто используют алгоритм Дейкстры, трудоемкость которого имеет оценку O(N2).

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

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

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

Во всех задачах исходные данные задаются в файле INPUT. TXT, а результат выводится в файл OUTPUT. TXT. Если в некоторой строке этих файлов несколько элементов, представленных более чем одним символом, то они разделяются пробелами. На одном тесте время работы не должно превышать 2 секунд, а затраты оперативной памяти 64 мегабайтов. Изменение этих условий оговаривается специально.

Размерность исходных данных во многих постановках задач рассчитана на применение 32-разрядной среды, такой как Delphi или Virtual Pascal. Рекомендуется сразу ориентироваться на максимальную размерность данных. Например, стоит применять быструю сортировку массивов,  не злоупотреблять последовательным поиском данных и т. п. В С++ программная реализация может значительно упроститься путем использования библиотеки шаблонов STL.

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

1. Перебор с возвратом

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

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

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

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

Первое правило говорит о том, как расширить исследуемый путь, если это возможно, а второе правило – о том, как выходить из тупика.

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

В  общем случае решение задачи состоит из вектора (a1, a2, … ) конечной, но не определенной длины, удовлетворяющего некоторым ограничениям. Каждое ai является элементом конечного линейно упорядоченного множества Ai. При полном переборе должны рассматриваться элементы множества A1× A2 × …× Ai  для  i = 1, 2,…Здесь символ ‘×’ обозначает декартовое произведение множеств.

В качестве исходного частичного решения выбирается пустой вектор ( ) и на основе имеющихся ограничений выясняется, какие элементы из A1 являются кандидатами в a1; обозначим это подмножество через S1. В качестве a1 выбирается первый элемент множества S1. В результате получается частичное решение (a1). Далее в соответствии с ограничениями и выбранным элементом a1 выбирается элемент a2 из множества S2  и т. д. Если на шаге k частичное решение (a1, a2, …, ak-1) не представляет возможностей для выбора элемента ak, то выбирается новый элемент ak-1. Если ak-1 выбрать нельзя, возвращаемся еще дальше и выбирается новый элемент ak-2  и т. д.

Этот процесс удобно описать с помощью дерева.

Начало

Выборы для a1 

Выборы для a2 

при данном a1 

Выборы для a3

при данных a1 и a2

………………….

Обход дерева в порядке сверху вниз соответствует схеме поиска с возвратом.

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

Распространенным примером применения перебора с возвратом является задача о восьми ферзях [1]. Требуется расставить на шахматной доске 8 ферзей так, чтобы они не атаковали один другого. Иными словами, они должны стоять на разных горизонталях, вертикалях и диагоналях.

В каждой строке должен находиться ровно один ферзь, поэтому решение можно представить вектором (a1, a2, …, a8), в котором ai – номер столбца ферзя из строки с номером i. Более того, в каждом столбце должен быть ровно один ферзь, поэтому ai ≠ aj при i ≠ j. Наконец, поскольку ферзи не должны атаковать друг друга по диагонали, то необходимо выполнение условия  |ai - aj| ≠ |i-j| , если i ≠ j.

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

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

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

Program Ferzi;

{ Расстановка N ферзей на доске N×N, не бьющих друг друга.

  Выдача в файл out. txt. Количество вариантов по размеру доски:

  для  1 – 1,  для  2 – 0,  для  3 – 0,  для  4 – 2,  для  5 - 10