Полный перебор

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

История и происхождение термина

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

В современном понимании термин «brute force» закрепился в середине XX века с развитием вычислительной техники. Первые компьютеры, такие как ENIAC (1945) и UNIVAC I (1951), использовали полный перебор для решения задач баллистики, криптографии и численного анализа. В 1970-х годах метод стал стандартным инструментом в криптоанализе, особенно при взломе шифров с короткими ключами, например, DES (Data Encryption Standard).

Классификация методов полного перебора

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

По способу перебора

• Систематический перебор — последовательное перечисление всех вариантов в определённом порядке (например, лексикографическом или числовом). Используется в задачах комбинаторики и оптимизации.
• Случайный перебор — генерация случайных кандидатов без гарантии полного охвата. Применяется в методах Монте-Карло и некоторых эвристических алгоритмах.
• Рекурсивный перебор — разбиение задачи на подзадачи с последующим перебором всех комбинаций (например, в алгоритмах поиска в глубину).

По области применения

• Криптографический перебор — атака на шифры путём перебора всех возможных ключей. Например, в 1997 году проект DESCHALL за 96 дней перебрал 72 квадриллиона ключей для взлома DES.
• Комбинаторный перебор — решение задач о коммивояжёре, рюкзаке, раскраске графа и других NP-полных задач.
• Поисковый перебор — в искусственном интеллекте для задач планирования и игр (например, перебор ходов в шахматах).

Характеристики и сложность

Основная характеристика полного перебора — временная сложность, которая обычно выражается как O(n^k) или O(k^n), где n — размер входных данных, k — константа. Например, для задачи о коммивояжёре с n городами количество возможных маршрутов равно (n-1)!/2, что растёт факториально. Для криптоанализа сложность определяется размером ключевого пространства: для 128-битного ключа AES необходимо перебрать 2^128 вариантов, что практически нереализуемо современными компьютерами.

Пространственная сложность полного перебора обычно невелика, так как алгоритм хранит только текущий кандидат и результат. Однако в рекурсивных реализациях может потребоваться стек вызовов глубиной O(n).

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

Применение в различных областях

Криптография и информационная безопасность

Полный перебор используется для атак на криптосистемы с малым ключевым пространством. Исторически известны случаи взлома шифров:

• Шифр Цезаря (I век до н. э.) — перебор 25 возможных сдвигов.
• Энигма (Вторая мировая война) — британские криптоаналитики под руководством Алана Тьюринга использовали электромеханические машины «Бомба» для частичного перебора настроек.
• DES (1977) — в 1998 году проект EFF построил компьютер «Deep Crack», который за 56 часов перебрал 2^56 ключей.
• MD5 (1991) — в 2004 году китайские учёные обнаружили коллизии, но полный перебор хешей остаётся теоретически возможным.

Современные алгоритмы (AES-256, RSA-2048) используют ключи такой длины, что полный перебор невозможен в обозримом будущем.

Комбинаторика и оптимизация

В задачах дискретной оптимизации полный перебор применяется для малых размерностей:

• Задача о рюкзаке — перебор всех подмножеств предметов (2^n вариантов) для нахождения максимальной стоимости.
• Задача коммивояжёра — точное решение для n ≤ 20 городов возможно за разумное время.
• Задача о раскраске графа — перебор всех раскрасок для проверки k-раскрашиваемости.

Искусственный интеллект и игры

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

• Шахматы — алгоритм минимакса с альфа-бета-отсечением сокращает перебор, но в эндшпилях с малым числом фигур (до 6) применяется полный перебор (базы эндшпилей).
• Го — до появления AlphaGo (2016) полный перебор был невозможен из-за огромного количества вариантов (10^170).
• Крестики-нолики — полный перебор 9! = 362 880 возможных партий гарантирует ничью при оптимальной игре.

Биоинформатика

В анализе последовательностей ДНК полный перебор применяется для поиска мотивов и выравнивания:

• Поиск подстрок — алгоритм Бойера-Мура и его модификации, но для коротких последовательностей (до 1000 символов) возможен прямой перебор.
• Сборка генома — метод «overlap-layout-consensus» использует перебор всех возможных перекрытий фрагментов.

Оптимизации и альтернативы

Для снижения вычислительной сложности полного перебора разработаны методы:

• Ветви и границы (branch and bound) — отсечение заведомо неоптимальных ветвей.
• Метод отжига (simulated annealing) — вероятностный поиск, не гарантирующий оптимальности.
• Генетические алгоритмы — эволюционный подход для больших пространств.
• Эвристики — использование правил для сокращения перебора (например, в криптоанализе — атаки по времени или по мощности).

В криптографии альтернативой полному перебору являются атаки на основе математических уязвимостей (например, факторизация RSA) или квантовые алгоритмы (алгоритм Гровера, дающий квадратичное ускорение).

Критика и ограничения

Основной недостаток полного перебора — вычислительная неэффективность для задач большого размера. Для NP-полных задач (например, задача выполнимости булевых формул) полный перебор остаётся единственным точным методом, но время его работы растёт экспоненциально. В криптографии полный перебор считается «грубой» атакой, которая может быть обнаружена системами мониторинга (например, по большому числу неудачных попыток входа).

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

Интересные факты

• В 2017 году группа исследователей из Университета Цюриха перебрала 2^40 (около 1 триллиона) вариантов для взлома 40-битного шифра RC4 за 3 дня на обычном компьютере.
• Алгоритм «решето Эратосфена» до сих пор используется для генерации простых чисел до 10^12, хотя для больших диапазонов применяются вероятностные тесты.
• В математике полный перебор применяется для доказательства теорем: например, в 1976 году Кеннет Аппель и Вольфганг Хакен доказали теорему о четырёх красках с помощью компьютерного перебора 1936 конфигураций.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ», 3-е издание, 2013.
• Шнайер Б. «Прикладная криптография», 2-е издание, 2002.
• Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи», 1982.
• Аппель К., Хакен В. «Every planar map is four colorable», 1976.
• DESCHALL Project, 1997.
• EFF DES Cracker, 1998.