Полный перебор: метод решения задач в информатике.

Введение

Метод решения задач и алгоритмическая парадигма. Метод решения задач в информатике.

В информатике поиск с применением грубой силы, или исчерпывающий поиск, также известный как метод «сгенерировать и проверить», является очень общей техникой решения задач и алгоритмической парадигмой, заключающейся в систематической проверке всех возможных вариантов на соответствие условию задачи. Алгоритм грубой силы, находящий делители натурального числа n, перебирает все целые числа от 1 до n и проверяет, делится ли каждое из них на n без остатка. Применение подхода грубой силы к задаче о восьми ферзях предполагает рассмотрение всех возможных расстановок 8 фигур на шахматной доске 64x64 и для каждой расстановки проверку, может ли какая-либо фигура (ферзь) атаковать другую. Хотя поиск с применением грубой силы прост в реализации и всегда находит решение, если оно существует, стоимость реализации пропорциональна числу возможных решений, которое во многих практических задачах быстро растет с увеличением размера задачи (§Комбинаторный взрыв). Поэтому поиск грубой силы обычно используется, когда размер задачи ограничен, или когда существуют специфические эвристики, позволяющие сократить набор возможных решений до управляемого размера. Метод также применяется, когда простота реализации важнее скорости обработки. Это справедливо, например, для критически важных приложений, где любые ошибки в алгоритме могут иметь серьезные последствия, или при использовании компьютера для доказательства математической теоремы. Поиск грубой силы также полезен в качестве базового метода при оценке производительности других алгоритмов или метаэвристик. Фактически, поиск грубой силы можно рассматривать как простейшую метаэвристику. Поиск грубой силы не следует путать с методом перебора с возвратом (backtracking), при котором большие наборы решений могут быть отброшены без явного перечисления (как в типовом компьютерном решении задачи о восьми ферзях, описанном выше). Метод грубой силы для поиска элемента в таблице, а именно последовательная проверка всех элементов таблицы, называется линейным поиском.

In computer science, brute force search or exhaustive search, also known as generate and test, is a very general problem solving technique and algorithmic paradigm that consists of systematically checking all possible candidates for whether or not each candidate satisfies the problem's statement. A brute force algorithm that finds the divisors of a natural number n would enumerate all integers from 1 to n, and check whether each of them divides n without remainder. A brute force approach for the eight queens puzzle would examine all possible arrangements of 8 pieces on the 64 square chessboard and for each arrangement, check whether each (queen) piece can attack any other. While a brute force search is simple to implement and will always find a solution if it exists, implementation costs are proportional to the number of candidate solutionswhich in many practical problems tends to grow very quickly as the size of the problem increases (§Combinatorial explosion). Therefore, brute force search is typically used when the problem size is limited, or when there are problem specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than processing speed. This is the case, for example, in critical applications where any errors in the algorithm would have very serious consequences or when using a computer to prove a mathematical theorem. Brute force search is also useful as a baseline method when benchmarking other algorithms or metaheuristics. Indeed, brute force search can be viewed as the simplest metaheuristic. Brute force search should not be confused with backtracking, where large sets of solutions can be discarded without being explicitly enumerated (as in the textbook computer solution to the eight queens problem above). The brute force method for finding an item in a tablenamely, check all entries of the latter, sequentiallyis called linear search.

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

Основным недостатком метода грубой силы является то, что для многих реальных задач количество возможных вариантов становится непомерно большим. Например, если мы ищем делители числа, как описано выше, количество проверяемых кандидатов будет равно данному числу 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 до тех пор, пока число не превысит 1 000 000, что требует всего 2398 (= 1 000 000 ÷ 417) шагов и не требует проверок.

Переустройство пространства поиска

В приложениях, требующих только одного решения, а не всех решений, ожидаемое время выполнения поиска перебором часто будет зависеть от порядка, в котором тестируются кандидаты. Как правило, следует сначала проверять наиболее перспективных кандидатов. Например, при поиске собственного делителя случайного числа n, лучше перечислять кандидаты-делители в порядке возрастания, от 2 до n − 1, чем в обратном порядке, поскольку вероятность того, что n делится на c, равна 1/c. Более того, вероятность того, что кандидат является допустимым, часто зависит от результатов предыдущих неудачных попыток. Например, рассмотрим задачу поиска единицы в заданной 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. В более общем случае, пространство поиска следует перечислять таким образом, чтобы следующий кандидат был наиболее вероятным допустимым, учитывая, что предыдущие попытки не увенчались успехом. Таким образом, если допустимые решения, вероятно, будут "сгруппированы" в каком-то смысле, то каждый новый кандидат должен быть максимально удален от предыдущих в том же смысле. И наоборот, если решения, вероятно, будут распределены более равномерно, чем можно было бы ожидать случайно, то верно обратное.

Альтернативы обыска грубой силой

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

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

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