Перебор вариантов в информатике — это способ решения различных задач, который относится методикам поиска решения путем рассмотрения всех возможных вариантов.
Введение
Задачи, которые связаны с проблемами нахождения информации, представляют собой большой класс задач, относящийся к сфере информатики и программирования. В общем случае, проблема поиска может быть сведена к следующей формулировке: из находящейся в памяти электронной вычислительной машины информации, требуется извлечь необходимые данные, которые удовлетворяют заданным критериям (условиям). К примеру, среди множества задач можно выбрать проблему поиска наибольшего числового параметра в наборе числовых данных, поиск необходимого текста в информационных данных и тому подобное. Поисковые операции такого типа выполняются путём последовательного обращения ко всем компонентам структурированных данных и осуществления их анализа на предмет совпадения с условиями поискового запроса.
Если при переборе рассматриваются все структурные компоненты, то такой вариант считается полным перебором. Вариант полного перебора считается перебором в «лоб» и, что очевидно, почти никогда не бывает оптимальным (самым лучшим).
Алгоритм перебора без повторений
Возьмём следующий случай. Есть одномерный массив Х, в котором задаются координаты N точек, располагающихся на вещественной числовой оси. Все точки имею свои номера. Эта нумерация должна соответствовать их расположению в массиве Х. Необходимо, найти номер точки, которая имеет максимальное удаление от начальной координаты. То есть в этой задаче необходимо определить номер самого большого по модулю компонента в массиве Х. В такой постановке задачи, возможно решение полным перебором компонентов одномерного массива посредством одной циклической процедуры.
Другая задача с теми же исходными данными, но необходимо найти две точки, расположенные на максимальном расстоянии друг от друга. Если разрешать эту задачу полным перебором, то нужно пересмотреть модули разности координат между всеми парами точек и найти номера тех, где этот модуль максимален. Этот метод может быть реализован двумя вложенными циклами, но, понятно, что такой метод не будет оптимальным. В нём все пары точек будут проверяться два раза. То есть при i=1, j=2 и наоборот i=2, j=1. Если число N=100, то вложенные циклы необходимо повторить 100х100=10000 раз. Работа этого алгоритма может быть ускорена исключением повторений. Необходимо также не рассматривать совпадающие значения I и j. В таком случае число повторов цикла вложений при N=100 будет равняться 4950. Такой тип алгоритма называется перебором без повторения.
Безусловно, такая задача имеет и другие методы решения, но мы делаем акцент именно на алгоритме перебора вариантов. Но если точки расположены не на прямой, а в плоскости или даже в пространстве, то найти альтернативу этому алгоритму крайне сложно.
Рассмотрим ещё одну задачу. Необходимо найти три числа без повторов, у которых суммарное значение равняется десяти, из заданного массива Х. В таком варианте в алгоритм надо включить три вложенных цикла. У внутренних циклов будет переменная длина.
Fоr I:=l Tо N Dо
Fоr J:=I+1 Tо N Dо
Fоr К:=J+1 Tо N Dо
If Х[I]+Х[J]+Х[К]=10
Тhen Writе Ln(Х[I],Х[J],Х[К]);
А далее предположим, что необходимо из массива Х подобрать все числовые наборы, с суммарным весом равным десяти. В наборах (группах) чисел может быть от одного до N чисел. Это вызовет резкое увеличение числа вариантов перебора и алгоритм превращается в далеко не тривиальный. Количество разных наборов из N объектов (в том числе пустых) составит 2N. Опуская промежуточные подсчёты, резюмируем, что если компьютер способен выполнять миллиард операций в секунду, то для перебора всех возможных вариантов ему потребуется около десяти лет непрерывной работы. Если избавится от повторных обращений, то всё равно выполнение перебора вариантов останется фактически нереальным. Направление, которое позволит решать такие задачи, заключается в поиске методов отсева из множества переборов заведомо неверных, согласно заданным условиям, вариантов.
Алгоритм перебора с возвратом
Существует так называемая задача лабиринта. Есть лабиринт, необходимо найти выход из него. Перемещения по лабиринту возможны лишь в двух направлениях, а именно разрешены только горизонтальные и вертикальные перемещения. Чтобы сформировать программу, позволяющую выполнить решение этой задачи, надо разрешить две проблемы:
- Выбрать способ организации данных.
- Выбрать способ построения алгоритма.
Для информационных данных о структуре лабиринта можно выбрать квадратную матрицу LAB с символьной организацией и размером N x N, причём N обязательно нечётное число, чтобы иметь центральную точку. На профиль лабиринта необходимо наложить сетку таким образом, чтобы в каждой ячейке сетки была или стенка, или возможность прохода. В матрице отражено наполнение сетки. Компоненты, которые соответствуют проходу, обозначаются пробелом, а наличие стенки обозначим символом М. Маршрут продвижения по лабиринту обозначается знаками плюс (+). Исходными данными являются профиль лабиринта. В итоге необходимо получить маршруты выхода из центра лабиринта. Другое название алгоритма перебора с возвратом, метод проб. Основные моменты алгоритма следующие:
- Из любой текущей точки маршрута видны вероятные направления продвижения в одной и той же очерёдности. Просматривание клеток выполняется против часовой стрелки, очередной шаг выполняется в первую, найденную не занятую клетку по соседству. На клетку, куда произведён шаг, ставится крестик.
- В случае отсутствия пути из текущей клетки (тупик), необходимо вернуться на шаг назад и испробовать другие направления продвижения из текущей точки. При этом оставленная клетка помечается знаком пробел и больше не используется.
- В случае, когда следующая клетка, куда выполнен шаг, оказывается на границе лабиринта (это выход), то запоминается как сформированный весь маршрут движения. Для того, чтобы вывести весь маршрут на печать, выполняется процедура PRINTLAB.
