В информатике перебор методом перебора или исчерпывающий поиск , также известный как генерация и тестирование , представляет собой очень общий метод решения проблем и алгоритмическую парадигму , которая состоит из систематической проверки всех возможных кандидатов на предмет того, удовлетворяет ли каждый кандидат условию задачи.
Алгоритм грубого перебора, который находит делители натурального числа n , перечисляет все целые числа от 1 до n и проверяет, делит ли каждое из них n без остатка. При решении головоломки с восемью ферзями методом грубой силы исследуются все возможные расположения 8 фигур на шахматной доске с 64 клетками и для каждого расположения проверяется, может ли каждая фигура (ферзя) атаковать любую другую. [1]
Хотя метод грубой силы легко реализовать и он всегда найдет решение, если оно существует, затраты на его реализацию пропорциональны количеству возможных решений, которое во многих практических задачах имеет тенденцию очень быстро расти по мере увеличения размера проблемы (§ Комбинаторный взрыв). [2] Таким образом, поиск методом перебора обычно используется, когда размер проблемы ограничен или когда существуют эвристики , специфичные для конкретной проблемы , которые можно использовать для уменьшения набора возможных решений до управляемого размера. Метод также используется, когда простота реализации важнее скорости обработки.
Так обстоит дело, например, в критических приложениях, где любые ошибки в алгоритме могут иметь очень серьезные последствия, или при использовании компьютера для доказательства математической теоремы . Поиск методом грубой силы также полезен в качестве базового метода при сравнении других алгоритмов или метаэвристики . Действительно, поиск методом грубой силы можно рассматривать как простейшую метаэвристику . Поиск методом грубой силы не следует путать с обратным поиском , при котором большие наборы решений могут быть отброшены без явного перечисления (как в приведенном выше компьютерном решении задачи восьми ферзей из учебника). Метод перебора поиска элемента в таблице, а именно проверка всех записей последней последовательно, называется линейным поиском .
В порядке кандидата на P после текущего c .
Следующая процедура также должна сообщить , когда после текущего c больше нет кандидатов на экземпляр P. Удобный способ сделать это — вернуть «нулевого кандидата», некоторое обычное значение данных Λ, которое отличается от любого реального кандидата. Аналогично, первая процедура должна вернуть Λ, если для экземпляра 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/ с . Более того, на вероятность того, что кандидат окажется действительным, часто влияют предыдущие неудачные испытания. Например, рассмотрим задачу поиска 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] (кроме одноразового блокнота ) злоумышленником, который не может воспользоваться какой-либо слабостью в системе шифрования, которая в противном случае облегчила бы его или ее задачу. .
Длина ключа , используемого при шифровании, определяет практическую возможность проведения атаки методом перебора, при этом более длинные ключи экспоненциально сложнее взломать, чем более короткие. Атаки грубой силы могут стать менее эффективными, если запутать данные, которые нужно закодировать, что затрудняет злоумышленнику распознавание того, что он взломал код. Одним из показателей надежности системы шифрования является то, сколько времени теоретически потребуется злоумышленнику, чтобы провести успешную атаку методом перебора.