Алгоритм полного перебора — это алгоритм разрешения математических задач, который можно отнести к классу способов нахождения решения рассмотрением всех возможных вариантов.
Введение
Под полным перебором понимается методика разрешения задач математики путем рассмотрения всех возможных вариантов. Уровень сложности при полном переборе напрямую связан с количеством допустимых решений задачи. В случае, когда область решений огромна, время полного перебора может исчисляться десятками и даже сотнями лет, и при этом итоговый результат возможно ещё не будет найден. Все задачи класса NP (non-deterministic polynomial) могут быть решены при помощи полного перебора. В криптографии оценивается криптографическая стойкость шифрования на базе вычислительной сложности полного перебора. Например, криптостойкость шрифта будет на должном уровне, если нет методики его взлома, которая позволяет это сделать быстрее, чем путём полного перебора всего диапазона возможных ключей. Хакерские атаки в области криптографии, которые основаны на методике полного перебора, считаются наиболее универсальными, но при этом требуют максимальных временных затрат.
Метод исчерпывания
Методика исчерпывания на самом деле является целым классом разнообразных способов. Как правило, при постановке задачи предполагается перебор конечного количества возможных состояний конкретной системы логики для определения логической истинности выражения (утверждения) при помощи подробного анализа каждого из всех возможных состояний. Чтобы доказать утверждение, необходимо выполнить следующие действия:
- Доказать возможность исчерпания всех возможных в системе состояний. То есть необходимо увидеть, что все фактические состояния системы (к примеру, величина искомого логического выражения) будут соответствовать, по крайней мере, одному из подлежащих рассмотрению предполагаемых решений.
- Проверить все варианты доказать, что каждый анализируемый вариант может или не моет являться решением исходной задачи.
Применение алгоритма полного перебора
Хотя алгоритм полного перебора при решении большинства конкретных проблем (исключая взлом шифрования) практически не используется, существует несколько исключений. Например, в случаях, когда алгоритм полного перебора всё-таки окажется оптимальным или он является первым шагом в создании общего алгоритма, его применение будет оправданным.
В качестве примера, где полный перебор будет оптимальным методом, можно привести алгоритм оценки временного интервала выполнения вычислений цепочных произведений матриц, который не может быть ускорен по отношению к алгоритму, базирующемуся на способе «грубой силы». Такой алгоритм применяется при разрешении стандартной проблемы динамического программирования, а именно выборе приоритетов определения матричных произведений типа $A_1 A_2 A_3…A_n$. Начальная задача состоит в операции вычисления этого матричного произведения за минимальный временной интервал. Возможно просто выполнить последовательно это произведение. Так как произведение матриц считается ассоциативной операцией, то есть возможность вычислять произведение цепочек, делая произвольную выборку пары компонентов цепочки $(A_i A_{i+1}), i = 1…n-1$ и сделав её замену матрицей результата. Если данную операцию повторить $n – 1$ раз, то полученная результирующая матрица и станет итоговым результатом. Если при этом будет выбрана оптимальная очерёдность вычислений, то процесс может быть существенно ускорен. Решение возможно получить при помощи алгоритма полного перебора. Нужно проанализировать все допустимые последовательности выполнения операций и найти ту, которая при осуществлении умножений цепочки будет занимать самое маленькое количество скалярных произведений.
Разделяй и властвуй
Существует алгоритм быстрой сортировки, который базируется на принципе «разделяй и властвуй». В теории алгоритмов существует много общеизвестных направлений. Алгоритм полного перебора входит в их число. Практически, методом полного перебора можно пользоваться тогда, когда рассматривается дискретная детерминированная система, у которой все состояния возможно просто подвергнуть анализу.
Другой яркий пример базовой теории алгоритмов — это принцип «разделяй и властвуй». Его возможно использовать в случае, если систему можно разделить на некоторое количество подсистем, имеющих структуру аналогичную первоначальной системе. В этом случае подсистемы тоже возможно разделить, если они уже не имеют уровень тривиальных. В таких системах тривиальной считается изначально сформулированная задача. То есть можно сделать вывод, что выполнение методики «разделяй и властвуй» представляет собой рекурсивный процесс. С другой стороны, рекурсия, это не что иное, как одна из разновидностей полного перебора. Считается, что рекурсию возможно применять только для дискретных систем. Но это условие можно отнести не к набору состояний этой системы, а лишь к её субструктурному построению. Поочерёдный анализ всех уровней способен выдать полное решение задачи, которая была поставлена в отношении всей дискретной системы. Если сравнивать с другими задачами полного перебора, то характерной чертой рекурсивного способа можно считать то, что итоговый результат базируется не только на одну тривиальную подсистему. Как правило, решение основывается на анализе большого множества подсистем.
Атака методом «грубой силы»
В криптографии для взлома пароля применяется методика «грубой силы», которая базируется на алгоритме полного перебора. То есть подбор правильного пароля выполняется перебором всех допустимых версий ключа. Характерной чертой атаки методом «грубой силы» считается, что её можно использовать фактически против всех известных методов шифрования. Но следует заметить, что это лишь теоретическая возможность, так как часто она требует нереальных временных и ресурсных затрат.
