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

редактировать

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

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

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

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

Содержание

  • 1 Реализация поиска полным перебором
    • 1.1 Базовый алгоритм
  • 2 Комбинаторный взрыв
  • 3 Ускорение поиска методом перебора
  • 4 Изменение порядка в пространстве поиска
  • 5 Альтернативы поиску методом перебора
  • 6 В криптографии
  • 7 Ссылки
  • 8 См. Также

Реализация поиска полным перебором

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

В порядке кандидата для P после текущего c.

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

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

c ← first (P) while c ≠ Λ doifvalid (P, c) затем output (P, c) c ← next (P, c) end while

Например, при поиске делителей целое число n, данные экземпляра P - это число n. Вызов first (n) должен возвращать целое число 1, если n ≥ 1, или Λ в противном случае; вызов next (n, c) должен возвращать c + 1, если c < n, and Λ otherwise; and valid(n,c) should return true тогда и только тогда, когда c является делителем n. (Фактически, если мы выберем Λ равным n + 1, тесты n ≥ 1 и c < n are unnecessary.)The brute-force search algorithm above will call output for every candidate that is a solution to the given instance P. The algorithm is easily modified to stop after finding the first solution, or a specified number of solutions; or after testing a specified number of candidates, or after spending a given amount of CPU время.

Комбинаторный взрыв

Главный недостаток брутто Метод -force состоит в том, что для многих реальных задач количество естественных кандидатов недопустимо велико.Например, если мы ищем делители числа, как описано выше, количество проверенных кандидатов будет заданным числом n. Итак, если n имеет шестнадцать десятичных цифр, скажем, для поиска потребуется выполнить не менее 10 компьютерных инструкций, что займет несколько дней на типичном ПК. Если n - случайное 64- бит натуральное число, которое в среднем состоит примерно из 19 десятичных цифр, поиск займет около 10 лет. Такой резкий рост числа кандидатов по мере увеличения размера данных встречается во всех видах задач. Например, если мы ищем конкретную перестановку из 10 букв, тогда у нас есть 10! = 3 628 800 кандидатов для рассмотрения, которые обычный ПК может сгенерировать и протестировать менее чем за одну секунду. Однако добавление еще одной буквы - что увеличивает размер данных всего на 10% - умножит количество кандидатов на 11, увеличиваясь на 1000%. Для 20 букв количество кандидатов составляет 20 !, что составляет примерно 2,4 × 10 или 2,4 квинтиллион ; и поиск займет около 10 лет. Это нежелательное явление обычно называется комбинаторным взрывом или проклятием размерности.

. Одним из примеров случая, когда комбинаторная сложность приводит к пределу разрешимости, является решение шахмат. Шахматы - это не решаемая игра. В 2005 году все концовки шахматной партии с шестью или менее фигурами были решены с указанием результата каждой позиции при безупречной игре. Потребовалось еще десять лет, чтобы завершить основание стола, добавив еще одну шахматную фигуру, таким образом завершив основание стола из 7 частей. Добавление еще одной фигуры к шахматной концовке (таким образом, создавая базу из 8 частей) считается неразрешимым из-за дополнительной комбинаторной сложности.

Ускорение поиска методом грубой силы

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

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

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

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

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

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

Ссылки

См. Также

Последняя правка сделана 2021-05-13 03:12:03
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте