Поиск методом перебора
 | Эта статья нуждается в дополнительных ссылок для проверки . ( февраль 2008 г. ) |
В информатике перебор методом перебора или исчерпывающий поиск , также известный как генерация и тестирование , представляет собой очень общий метод решения проблем и алгоритмическую парадигму , которая состоит из систематической проверки всех возможных кандидатов на предмет того, удовлетворяет ли каждый кандидат условию задачи.
Алгоритм грубого перебора, который находит делители натурального числа n, перечисляет все целые числа от 1 до n и проверяет, делит ли каждое из них n без остатка. методом грубой силы При решении головоломки с восемью ферзями исследуются все возможные расположения 8 фигур на шахматной доске с 64 клетками и для каждого расположения проверяется, может ли каждая фигура (ферзя) атаковать любую другую. [1]
Хотя метод грубой силы легко реализовать и всегда найдет решение, если оно существует, затраты на реализацию пропорциональны количеству возможных решений, которое во многих практических задачах имеет тенденцию очень быстро расти по мере увеличения размера проблемы ( § Комбинаторный взрыв ). [2] Поэтому поиск методом грубой силы обычно используется, когда размер проблемы ограничен или когда существуют эвристики для конкретной проблемы , которые можно использовать для уменьшения набора возможных решений до управляемого размера. Метод также используется, когда простота реализации важнее скорости обработки.
Так обстоит дело, например, в критически важных приложениях, где любые ошибки в алгоритме могут иметь очень серьезные последствия, или при использовании компьютера для доказательства математической теоремы . Поиск методом грубой силы также полезен в качестве базового метода при сравнении других алгоритмов или метаэвристики . Действительно, поиск методом грубой силы можно рассматривать как простейшую метаэвристику . Поиск методом грубой силы не следует путать с обратным поиском , при котором большие наборы решений могут быть отброшены без явного перечисления (как в приведенном выше компьютерном решении задачи восьми ферзей из учебника). Метод перебора поиска элемента в таблице, а именно проверка всех записей последней последовательно, называется линейным поиском .
Реализация поиска методом перебора [ править ]
Основной алгоритм [ править ]
В порядке кандидата на P после текущего c .
- valid ( P , c ): проверьте, является ли кандидат c решением для P .
- вывод ( P , c ): используйте решение c из P в соответствии с приложением.
Следующая процедура также должна сообщить , больше нет кандидатов на экземпляр P. после текущего c когда Удобный способ сделать это — вернуть «нулевого кандидата», некоторое обычное значение данных Λ, которое отличается от любого реального кандидата. Аналогично, первая вообще нет кандидатов процедура должна вернуть Λ, если для экземпляра P . Тогда метод грубой силы выражается алгоритмом
c ← первый ( P )
в то время как c ≠ Λ do
, если действительно ( 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] (кроме одноразового блокнота ) злоумышленником, который не может воспользоваться какой-либо слабостью системы шифрования, которая в противном случае облегчила бы его или ее задачу.
Длина ключа , используемого при шифровании, определяет практическую возможность проведения атаки методом перебора, при этом более длинные ключи экспоненциально сложнее взломать, чем более короткие. Атаки грубой силы могут стать менее эффективными, если запутать данные, подлежащие кодированию, что затрудняет злоумышленнику распознавание того, что он взломал код. Одним из показателей надежности системы шифрования является то, сколько времени теоретически потребуется злоумышленнику, чтобы провести успешную атаку методом перебора.
Ссылки [ править ]
- ^ «Объяснение алгоритмов грубой силы» . freeCodeCamp.org . 06.01.2020 . Проверено 11 апреля 2021 г.
- ^ «Сложность перебора» . конечнора . Проверено 14 июня 2018 г.
- ^ «Есть ли в свободном доступе онлайн-таблица из 7 частей для эндшпиля?» . Обмен стеками .
- ^ «Таблицы эндшпиля Ломоносова» . Шахматы ОК . Архивировано из оригинала 6 апреля 2019 года.
- ^ Марк Бернетт, «Блокирование атак грубой силы». Архивировано 3 декабря 2016 г. в Wayback Machine , UVA Computer Science , 2007 г.
- ^ Кристоф Паар; Ян Пельцль; Барт Пренил (2010). Понимание криптографии: Учебник для студентов и практиков . Спрингер. п. 7. ISBN 3-642-04100-0 .