Brute Force vs Exhaustive Search: разница и сравнение

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

Поиск осуществляется различными способами. Brute force и Exhaustion search — это два алгоритма поиска строк, используемые кодировщиками. Эти методы работают по принципу поиска каждого возможного решения.

Основные выводы

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

Brute Force против исчерпывающего поиска

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

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

Однако это интуитивно понятная стратегия, которая требует множества сравнений для решения проблемы.

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

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

Сравнительная таблица

Параметры сравнения	Поиск грубой силы	Исчерпывающий поиск
Тип поиска	Brute Force — неравномерный поиск.	Исчерпывающий — это равномерный поиск, потому что мы знаем, в каком направлении выполняется выборка.
Поисковые запросы	Brute Force предназначен для поиска по шаблону строки.	Алгоритм исчерпывающего поиска предназначен для получения перестановок, комбинаций и подмножеств.
Процедура	Алгоритм грубой силы ищет нужный шаблон, перемещаясь вправо в заданном тексте.	Алгоритм исчерпывающего поиска проверяет каждый узел, пока не достигнет последнего узла.
Время	Грубая сила — это трудоемкий метод.	Алгоритм исчерпывающего поиска занимает меньше времени по сравнению с ним.
Приложения	Алгоритм поиска грубой силы используется для размещения восьми ферзей на досках размером восемь на восемь.	Алгоритм полного перебора используется для решения задачи коммивояжера.

Что такое брутфорс-поиск?

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

В этом методе не используется сложная техника для нахождения решения.

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

Теперь процедура проста. Предположим, нам нужно найти строку PLANT.

Сопоставьте написание каждого слова в абзаце со строкой ЗАВОД. Двигайтесь вправо, если фраза в строке не совпадает. Если строка совпадает, наш поиск был успешным. Мы получили желаемые результаты.

Поэтому можно сказать, что это очень трудоемкий метод поиска, если длина текста больше. Хитрость вычисления количества сравнений заключается в умножении N x M, где N — длина текста, а M — длина строки.

Например,

Текст =10

Строка = ЗАВОД, поэтому размер строки = 5

Комбинации = NXM = 10 x 5 = 50

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

Что такое исчерпывающий поиск?

Полный поиск — это подмножество алгоритма поиска грубой силы, предназначенного для поиска комбинаций и перестановок. Этот алгоритм фокусируется на поиске каждого решения данной задачи, удовлетворяя всем ограничениям.

Поскольку исчерпывающий означает утомительный, эти виды поиска являются слепыми, но однородными. Стратегия направлена ​​либо на максимизацию, либо на минимизацию проблемы.

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

Задача коммивояжера состоит в том, что перед тем, как вернуться в исходную точку, коммивояжер должен посетить N городов (только один раз) по кратчайшему маршруту.

Здесь N — количество городов, а ограничения в этой задаче таковы:

1. По кратчайшему пути из города в город.
2. Посетите все города, прежде чем вернуться.
3. Посетите все города только один раз.

Например,

Есть пять городов: A, B, C, D и E. Начальный город выбирается с умом, применяя комбинации. Итак, чтобы все ограничения были выполнены.

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

Основные различия между полным перебором и исчерпывающим поиском

1. Алгоритм поиска Brute Force является неоднородным методом. С другой стороны, исчерпывающий алгоритм поиска является унифицированным методом.
2. Алгоритм поиска Brute Force — это метод поиска строки в тексте. Напротив, алгоритм исчерпывающего поиска ищет решение перестановок и комбинаций.
3. Техника грубой силы работает путем сопоставления всех букв в строке. Однако исчерпывающий поиск следует за процедурой проверки каждого узла блок-схемы до тех пор, пока ограничения не будут удовлетворены.
4. Метод грубой силы требует больше времени и применим, когда данных мало. С другой стороны, исчерпывающий алгоритм применим даже в сложных сценариях.
5. Поскольку в методе перебора используется метод грубой силы, он более популярен, чем полный перебор.

Рекомендации

1. https://ieeexplore.ieee.org/abstract/document/4640789/
2. https://link.springer.com/chapter/10.1007/3-540-44411-4_2

Последнее обновление: 13 июля 2023 г.