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

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

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

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

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

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

Базовый алгоритм [ править ]

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

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

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

c ← first ( P ), а  c ≠ Λ do,  если  верно ( P , c ), то  вывести ( P , c ) c ← next ( P , c ) end, пока

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

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

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

В криптографии [ править ]

Основная статья: Атака грубой силой

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

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

Ссылки [ править ]

  1. ^ «Объяснение алгоритмов грубой силы» . freeCodeCamp.org . 2020-01-06 . Проверено 11 апреля 2021 .
  2. ^ "Сложность перебора" . курсера . Проверено 14 июня 2018 .
  3. ^ "Есть ли в свободном доступе онлайн-стол для эндшпиля из 7 предметов?" . Обмен стеками .
  4. ^ "Ломоносовские финальные столы" . ChessOK .
  5. ^ Марк Бернетт, "Блокирующие Нападения Brute Force" Архивные 2016-12-03 на Wayback Machine , UVA Computer Science , 2007
  6. ^ Кристоф Паар; Ян Пельцль; Барт Пренил (2010). Понимание криптографии: Учебник для студентов и практиков . Springer. п. 7. ISBN 3-642-04100-0.

См. Также [ править ]

  • Алгоритм грубой силы для решения головоломок судоку.
  • Атака грубой силой
  • Обозначение Big O