Поиск грубой силы - Brute-force search

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

Алгоритм грубой силы , которая находит делители из более натурального числа п бы перечислить все целые числа от 1 до п, и проверить , является ли каждый из них делит п без остатка. Подход грубой силы для головоломки с восемью ферзями будет исследовать все возможные варианты расположения 8 фигур на 64-квадратной шахматной доске и проверять для каждого расположения, может ли каждая фигура (ферзь) атаковать любую другую.

Хотя поиск методом перебора прост в реализации и всегда найдет решение, если оно существует, затраты на реализацию пропорциональны количеству возможных решений, которое во многих практических задачах имеет тенденцию очень быстро расти по мере увеличения размера проблемы ( § Комбинаторный взрыв ). Следовательно, поиск методом перебора обычно используется, когда размер проблемы ограничен или когда есть эвристика для конкретной проблемы, которую можно использовать для сокращения набора возможных решений до управляемого размера. Метод также используется, когда простота реализации важнее скорости.

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

Реализация поиска методом перебора

Базовый алгоритм

Чтобы кандидат в P после текущего c .

  1. действительный ( P , C ): проверка ли кандидат с является решением для P .
  2. output ( P , c ): используйте решение c из P в соответствии с приложением.

Следующая процедура должна также сказать , когда нет больше кандидатов для экземпляра Р , после текущего с . Удобный способ сделать это - вернуть «нулевого кандидата», некоторое обычное значение данных Λ, которое отличается от любого реального кандидата. Точно так же первая процедура должна возвращать Λ, если для экземпляра P вообще нет кандидатов . Затем метод грубой силы выражается алгоритмом

cfirst(P)
while c ≠ Λ do
    if valid(P,c) then
        output(P, c)
    cnext(P, c)
end while

Например, при поиске делителей целого числа n данные экземпляра P - это число n . Вызов first ( n ) должен возвращать целое число 1, если n ≥ 1, или Λ в противном случае; вызов next ( n , c ) должен возвращать c + 1, если c < n , и Λ в противном случае; и valid ( n , c ) должен возвращать true тогда и только тогда, когда c является делителем n . (На самом деле, если мы выбираем Л быть п + 1, испытания п ≥ 1 и с < п излишни.) Алгоритм поиска перебора выше будет вызывать выход для каждого кандидата , который является решением данного экземпляра 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 фигур) считается неразрешимым из-за дополнительной комбинаторной сложности.

Ускорение поиска методом перебора

Один из способов ускорить алгоритм перебора состоит в том, чтобы уменьшить пространство поиска, то есть набор возможных решений, с помощью эвристики, специфичной для класса проблемы. Например, в задаче о восьми ферзях задача состоит в том, чтобы разместить восемь ферзей на стандартной шахматной доске так, чтобы ни один ферзь не атаковал другой. Поскольку каждый ферзь может быть помещен в любое из 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, пока число не превысит 1000000, что требует всего 2398 (= 1000000 ÷ 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. как правило, пространство поиска должно быть пронумеровано таким образом, чтобы следующий кандидат, скорее всего, был действителен, учитывая, что предыдущие испытания не проводились . Таким образом, если действительные решения могут быть «сгруппированы» в каком-то смысле, то каждый новый кандидат должен быть как можно дальше от предыдущих в том же смысле. Конечно, верно и обратное, если решения могут быть распределены более равномерно, чем ожидалось случайно.

Альтернативы поиску методом перебора

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

В криптографии

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

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

Рекомендации

Смотрите также