Сложность алгоритмов перебора

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

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

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

Применяя метод перебора, эту задачу можно решать так: перебрать все пары точек из N данных и определить номера тех точек, расстояние между которыми наибольшее (наибольший модуль разности координат). Такой полный перебор реализуется через два вложенных цикла:

Numberl:=1;

Number2:=2;

fori:=l toN do

forj:= i+1toN do

ifAbs(X[i] - X[j]) > Abs(X[Numberl] - X[Number2])

Then

Begin

Number l:=i ;

Number 2:=j

end;

Но очевидно, что такое решение задачи нерационально. Здесь каждая пара точек будет просматриваться дважды, например при i - 1, j = 2 и i = 2, j=1. Для случая N = 100 циклы повторят выполнение 100 • 100 = 10 000 раз.

Выполнение программы ускорится, если исключить повторения. Исключить также следует и совпадения значений i и j. Для исключения повторений нужно в предыдущей программе изменить начало внутреннего цикла с 1 на i + 1. Программа примет вид:

Numberl:=1;

Number2:=2;

fori:=ltoN do

forj:=i + 1to N do

ifAbs(X[i] - X[j]) >Abs(X[Numberl] - X[Number2])

Then

Begin

Numberl:=i ;

Number2:=j

end;

В таком алгоритме число повторений цикла будет равно N(N - 1)/2. При N = 100 получается 4950. Рассмотренный вариант алгоритма назовем перебором без повторений.

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

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

fori := 1toNdo

forj := i + 1toNdo

fork := j + 1to N do

ifX[i] + X[j] + X[k] = 10

thenwriteln(X[i], X[j], X[k]);

А теперь представьте, что из массивах требуется выбрать всевозможные группы чисел, сумма которых равна десяти. Количество чисел в группах может быть любым — от 1 до N. В этом случае количество вариантов перебора резко возрастает, а сам алгоритм становится нетривиальным.

Казалось бы, ну и что? Компьютер работает быстро! И все же посчитаем. Число различных групп из N объектов (включая пустую) составляет 2^N. При N = 100 это будет 2¹⁰⁰ ≈ 10³⁰. Компьютер, работающий со скоростью миллиард операций в секунду, будет осуществлять такой перебор приблизительно 10 лет. Даже исключение перестановочных повторений не сделает такой переборный алгоритм практически осуществимым.

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

Впечатляющим примером решения фундаментальной математической проблемы методом поиска является Проект GIMPS (Great Internet Mersenne Prime Search), направленный на поиск простых чисел Мерсенна — последовательности чисел, подчиняющихся закону 2^p-1, где р – простое число. В ноябре 2001 года в рамках данного проекта было найдено число Мерсенна, содержащее в своей десятичной записи более 4 млн цифр. Десятки тысяч компьютеров по всему миру, отдавая часть своих вычислительных ресурсов, работали над этой задачей два с половиной года.

Коротко о главном

В программировании используются два критерия сложности алгоритма: объемная сложность и временная сложность.

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

Временная сложность связана с количеством операций, выполняемых процессором в течение работы программы; количество операций пропорционально времени выполнения программы.

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

Задача перебора: из множества данных, хранящихся в памяти компьютера, требуется выбрать нужные данные, удовлетворяющие определенным условиям (критериям).

Временная сложность полного перебора может привести к превышению разумного времени выполнения программы на компьютере.

Оптимизация алгоритма перебора состоит в исключении анализа бесперспективных вариантов.

Вопросы и задания

1. Почему временная сложность алгоритма зависит от его объемной сложности?

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

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