В информатике поиск методом полного перебора или исчерпывающий поиск , также известный как генерация и проверка , представляет собой очень общую методику решения проблем и алгоритмическую парадигму , которая заключается в систематической проверке всех возможных кандидатов на предмет того, удовлетворяет ли каждый из них условию задачи.
Алгоритм грубой силы, который находит делители натурального числа n, перечислит все целые числа от 1 до n и проверит, делит ли каждое из них n без остатка. Подход грубой силы для головоломки с восемью королевами рассмотрит все возможные расположения 8 фигур на 64-клеточной шахматной доске и для каждого расположения проверит, может ли каждая фигура (ферзь) атаковать любую другую. [1]
Хотя поиск методом грубой силы прост в реализации и всегда найдет решение, если оно существует, затраты на реализацию пропорциональны количеству возможных решений, которое во многих практических задачах имеет тенденцию очень быстро расти по мере увеличения размера задачи (§Комбинаторный взрыв). [2] Поэтому поиск методом грубой силы обычно используется, когда размер задачи ограничен или когда существуют эвристики , специфичные для задачи , которые можно использовать для сокращения набора возможных решений до управляемого размера. Этот метод также используется, когда простота реализации важнее скорости обработки.
Это имеет место, например, в критических приложениях, где любые ошибки в алгоритме могут иметь очень серьезные последствия, или при использовании компьютера для доказательства математической теоремы . Поиск методом грубой силы также полезен в качестве базового метода при сравнительном анализе других алгоритмов или метаэвристик . Действительно, поиск методом грубой силы можно рассматривать как простейшую метаэвристику . Поиск методом грубой силы не следует путать с поиском с возвратом , когда большие наборы решений могут быть отброшены без явного перечисления (как в компьютерном решении задачи о восьми королевах из учебника выше). Метод грубой силы для поиска элемента в таблице, а именно, проверка всех записей последней последовательно, называется линейным поиском .
По порядку кандидата на P после текущего c .
Следующая процедура также должна сообщать, когда больше нет кандидатов для экземпляра P , после текущего c . Удобный способ сделать это — вернуть «нулевого кандидата», некоторое условное значение данных Λ, которое отличается от любого реального кандидата. Аналогично первая процедура должна возвращать Λ, если вообще нет кандидатов для экземпляра P . Метод грубой силы затем выражается алгоритмом
c ← первый ( P ) пока c ≠ Λ сделать если допустимо ( P , c ) тогда вывести ( P , c ) c ← следующий ( P , c ) конец пока
Например, при поиске делителей целого числа n данные экземпляра P — это число n . Вызов first ( n ) должен возвращать целое число 1, если n ≥ 1, или Λ в противном случае; вызов next ( n , c ) должен возвращать c + 1, если c < n , и Λ в противном случае; и valid ( n , c ) должен возвращать true тогда и только тогда, когда c является делителем n . (На самом деле, если мы выберем Λ равным n + 1, проверки n ≥ 1 и c < n не нужны.) Алгоритм поиска методом перебора, приведенный выше, вызовет вывод для каждого кандидата, который является решением для данного экземпляра P . Алгоритм легко модифицируется для остановки после нахождения первого решения или указанного количества решений; или после проверки указанного количества кандидатов, или после затрат заданного количества процессорного времени.
Основным недостатком метода грубой силы является то, что для многих реальных задач число естественных кандидатов непозволительно велико. Например, если мы ищем делители числа, как описано выше, число проверенных кандидатов будет равно заданному числу n . Так, если n имеет шестнадцать десятичных цифр, скажем, поиск потребует выполнения не менее 10 15 компьютерных инструкций, что займет несколько дней на типичном ПК . Если n — случайное 64- битное натуральное число, которое в среднем имеет около 19 десятичных цифр, поиск займет около 10 лет. Этот резкий рост числа кандидатов по мере увеличения размера данных происходит во всех видах задач. Например, если мы ищем определенную перестановку из 10 букв, то у нас есть 10! = 3 628 800 кандидатов для рассмотрения, которые типичный ПК может сгенерировать и проверить менее чем за одну секунду. Однако добавление еще одной буквы — что составляет всего лишь 10% увеличения размера данных — умножит количество кандидатов на 11, увеличение на 1000%. Для 20 букв количество кандидатов составит 20!, что составляет около 2,4×10 18 или 2,4 квинтиллиона ; и поиск займет около 10 лет. Это нежелательное явление обычно называют комбинаторным взрывом , или проклятием размерности .
Одним из примеров случая, когда комбинаторная сложность приводит к пределу разрешимости, является решение шахмат . Шахматы — нерешаемая игра . В 2005 году были решены все окончания шахматных игр с шестью или менее фигурами, что показало результат каждой позиции при идеальной игре. Потребовалось еще десять лет, чтобы завершить базу таблицы с добавлением еще одной шахматной фигуры, тем самым завершив базу таблицы из 7 фигур. Добавление еще одной фигуры к окончанию шахмат (таким образом, создание базы таблицы из 8 фигур) считается неразрешимым из-за добавленной комбинаторной сложности. [3] [4]
Один из способов ускорить алгоритм грубой силы — это сократить пространство поиска, то есть набор возможных решений, используя эвристики, характерные для класса задач. Например, в задаче о восьми ферзях задача состоит в том, чтобы разместить восемь ферзей на стандартной шахматной доске так, чтобы ни один ферзь не атаковал другого. Поскольку каждый ферзь может быть размещен на любой из 64 клеток, в принципе, существует 64 · 8 = 281 474 976 710 656 возможностей для рассмотрения. Однако, поскольку все ферзи одинаковы, и никакие два ферзя не могут быть размещены на одной и той же клетке, кандидатами являются все возможные способы выбора набора из 8 клеток из всех 64 клеток; что означает 64 выбрать 8 = 64!/(56!*8!) = 4 426 165 368 возможных решений — около 1/60 000 предыдущей оценки. Далее, никакое расположение с двумя ферзями в одной строке или в одном столбце не может быть решением. Поэтому мы можем еще больше ограничить набор кандидатов этими расположениями.
Как показывает этот пример, небольшой анализ часто приводит к значительному сокращению числа возможных решений и может превратить неразрешимую проблему в тривиальную.
В некоторых случаях анализ может свести кандидатов к набору всех допустимых решений; то есть он может дать алгоритм, который напрямую перечисляет все желаемые решения (или находит одно решение, в зависимости от ситуации), не тратя время на тесты и генерацию недопустимых кандидатов. Например, для задачи «найти все целые числа от 1 до 1 000 000, которые делятся нацело на 417» наивное решение методом грубой силы сгенерирует все целые числа в диапазоне, проверяя каждое из них на делимость. Однако эту задачу можно решить гораздо эффективнее, начав с 417 и многократно добавляя 417, пока число не превысит 1 000 000 — что займет всего 2398 (= 1 000 000 ÷ 417) шагов и не будет никаких тестов.
В приложениях, требующих только одного решения, а не всех решений, ожидаемое время выполнения поиска методом грубой силы часто будет зависеть от порядка, в котором проверяются кандидаты. Как правило, сначала следует проверять наиболее перспективных кандидатов. Например, при поиске правильного делителя случайного числа n лучше перечислять кандидаты-делители в порядке возрастания, от 2 до n − 1 , чем наоборот, поскольку вероятность того, что n делится на c, равна 1/ c . Более того, вероятность того, что кандидат будет действителен, часто зависит от предыдущих неудачных попыток. Например, рассмотрим задачу поиска бита 1 в заданной 1000-битной строке P. В этом случае кандидатами на решения являются индексы от 1 до 1000, а кандидат c действителен, если P [ c ] = 1. Теперь предположим, что первый бит P с равной вероятностью может быть 0 или 1 , но каждый последующий бит равен предыдущему с вероятностью 90%. Если кандидаты перечислены в порядке возрастания, от 1 до 1000, число t кандидатов, проверенных до успеха, будет в среднем около 6. С другой стороны, если кандидаты перечислены в порядке 1, 11, 21, 31... 991, 2, 12, 22, 32 и т. д., ожидаемое значение t будет лишь немного больше 2. В более общем смысле, пространство поиска должно быть перечислено таким образом, чтобы следующий кандидат с наибольшей вероятностью был действительным, учитывая, что предыдущие попытки не были . Таким образом, если действительные решения, вероятно, будут «кластеризованы» в некотором смысле, то каждый новый кандидат должен быть как можно дальше от предыдущих, в том же смысле. Обратное справедливо, конечно, если решения, вероятно, будут распределены более равномерно, чем ожидалось случайно.
Существует множество других методов поиска, или метаэвристик, которые разработаны для использования различных видов частичных знаний, которые могут быть у кого-то о решении. Эвристики также могут использоваться для раннего отсечения частей поиска. Одним из примеров этого является принцип минимакса для поиска игровых деревьев, который исключает многие поддеревья на ранней стадии поиска. В некоторых областях, таких как анализ языка, такие методы, как анализ диаграмм , могут использовать ограничения в задаче, чтобы свести задачу экспоненциальной сложности к задаче полиномиальной сложности. Во многих случаях, таких как в задачах удовлетворения ограничений , можно значительно сократить пространство поиска с помощью распространения ограничений , которое эффективно реализовано в языках программирования ограничений . Пространство поиска для задач также можно сократить, заменив полную задачу упрощенной версией. Например, в компьютерных шахматах вместо вычисления полного минимаксного дерева всех возможных ходов для оставшейся части игры вычисляется более ограниченное дерево минимаксных возможностей, при этом дерево обрезается через определенное количество ходов, а остаток дерева аппроксимируется статической оценочной функцией .
В криптографии атака методом перебора подразумевает систематическую проверку всех возможных ключей до тех пор, пока не будет найден правильный ключ. [5] Теоретически эта стратегия может быть использована против любых зашифрованных данных [6] (за исключением одноразового блокнота ) злоумышленником, который не в состоянии воспользоваться какой-либо слабостью в системе шифрования, которая в противном случае облегчила бы его задачу.
Длина ключа, используемого в шифровании, определяет практическую осуществимость выполнения атаки методом перебора, причем более длинные ключи экспоненциально сложнее взломать, чем короткие. Атаки методом перебора можно сделать менее эффективными, запутав данные, которые должны быть закодированы, что затрудняет для злоумышленника определение того, что он взломал код. Одной из мер стойкости системы шифрования является то, сколько времени теоретически потребуется злоумышленнику, чтобы провести успешную атаку методом перебора.