Введение в алгоритм грубой силы
«Данные - это новая нефть», это новая мантра, управляющая мировой экономикой. Мы живем в цифровом мире, и каждый бизнес вращается вокруг данных, которые приводят к прибыли и помогают отраслям опередить своих конкурентов. Благодаря быстрой оцифровке, экспоненциальному росту бизнес-модели, основанной на приложениях, киберпреступность представляет собой постоянную угрозу. Одним из таких распространенных действий, которые выполняют хакеры, является грубая сила.
Brute Force - это метод проб и ошибок, при котором злоумышленники используют программы, чтобы опробовать различные комбинации для взлома любых веб-сайтов или систем. Они используют автоматизированное программное обеспечение для периодической генерации комбинаций идентификаторов пользователей и паролей до тех пор, пока они в конечном итоге не создадут правильную комбинацию.
Поиск грубой силы
Поиск методом грубой силы является наиболее распространенным алгоритмом поиска, поскольку он не требует каких-либо знаний в предметной области, все, что требуется, - это описание состояния, юридические операторы, начальное состояние и описание состояния цели. Он не улучшает производительность и полностью полагается на вычислительную мощность, чтобы опробовать возможные комбинации.
Алгоритм грубой силы ищет все позиции в тексте между 0 и нм, независимо от того, начинается ли вхождение шаблона там или нет. После каждой попытки он смещает шаблон вправо ровно на 1 позицию. Временная сложность этого алгоритма составляет O (m * n). так что если мы ищем n символов в строке из m символов, тогда потребуется n * m попыток.
Давайте рассмотрим классический пример коммивояжера, чтобы легко понять алгоритм.
Предположим, что продавец должен путешествовать по 10 различным городам в стране, и он хочет определить кратчайшие возможные маршруты из всех возможных комбинаций. Здесь алгоритм грубой силы просто вычисляет расстояние между всеми городами и выбирает самый короткий.
Другим примером является попытка взломать 5-значный пароль, тогда грубая сила может занять до 10 5 попыток взломать код.
Сортировка грубой силы
В методе сортировки методом грубой силы список данных сканируется несколько раз, чтобы найти наименьший элемент в списке. После каждой итерации по списку он заменяет наименьший элемент на вершину стека и начинает следующую итерацию со вторых наименьших данных в списке.
Вышеприведенное утверждение может быть записано в псевдокоде следующим образом.
Здесь проблема имеет размер n, а основная операция - тест if, где элементы данных сравниваются на каждой итерации. Разница между наихудшим и наилучшим случаем не будет, так как значение свопа всегда равно n-1.
Сопоставление грубой силы
Если все символы в шаблоне уникальны, то сопоставление строк грубой силы может быть применено со сложностью Big O (n). где n - длина строки. Сопоставление грубой силы Строка сравнивает шаблон с подстрокой текстового символа за символом, пока не получит несоответствующий символ. Как только обнаруживается несоответствие, оставшийся символ подстроки удаляется, и алгоритм переходит к следующей подстроке.
Приведенные ниже псевдокоды объясняют логику сопоставления строк. Здесь алгоритм пытается найти шаблон P (0… m-1) в тексте T (0… .n-1).
здесь наихудший случай был бы, когда переход на другую подстроку не производился до сравнения М Th .
Ближайшая пара
Постановка задачи: выяснить две ближайшие точки в наборе из n точек в двумерной декартовой плоскости. Существует n сценариев, в которых возникает эта проблема. Примером из реальной жизни может служить система управления воздушным движением, где вы должны следить за самолетами, летящими близко друг к другу, и вы должны определить минимальное безопасное расстояние, которое должны выдерживать эти самолеты.
Источник: Википедия
Алгоритм грубой силы вычисляет расстояние между каждым отдельным набором точек и возвращает индексы точки, для которой расстояние является наименьшим.
Грубая сила решает эту проблему с временной сложностью (O (n2)), где n - количество точек.
Ниже псевдокод использует алгоритм грубой силы, чтобы найти ближайшую точку.
Выпуклая оболочка
Постановка задачи : выпуклая оболочка - это наименьший многоугольник, содержащий все точки. Выпуклая оболочка множества s точки - это наименьший выпуклый многоугольник, содержащий s.
Выпуклая оболочка для этого набора точек представляет собой выпуклый многоугольник с вершинами в точках P1, P5, P6, P7, P3
Сегмент P1 и Pn набора из n точек является частью выпуклой оболочки тогда и только тогда, когда все остальные точки набора лежат внутри границы многоугольника, образованного отрезком линии.
Давайте свяжем это с резинкой,
Точка (x1, y1), (x2, y2) делает линию ax + by = c
Когда a = y2-y1, b = x2-x1 и c = x1 * y2 - x2 * y1 и делит плоскость на ax + на -c 0
Поэтому нам нужно проверить ax + by-c для других точек.
Грубая сила решает эту проблему с временной сложностью O (n 3 )
Исчерпывающий поиск
Для дискретных задач, в которых нет известного эффективного решения, становится необходимостью последовательно тестировать каждое возможное решение.
Исчерпывающий поиск - это деятельность, позволяющая систематически находить все возможные решения проблемы.
Давайте попробуем решить задачу коммивояжера (TSP), используя алгоритм полного поиска Brute.
Постановка задачи: есть n городов, по которым продавец должен путешествовать, он хочет найти кратчайший маршрут, который охватывает все города.
Мы рассматриваем Hamilton Circuit для решения этой проблемы. Если цепь существует, то любая точка может начинать вершины и заканчивать вершины. Как только начальные вершины выбраны, нам нужен только порядок для оставшихся вершин, т.е. n-1
Тогда будет (п-1)! Возможные комбинации и общая стоимость для расчета пути будут O (n). таким образом, общая сложность времени будет O (n!).
Вывод
Теперь, когда мы подошли к концу этого урока, я надеюсь, что вы, ребята, теперь получили четкое представление о том, что такое Brute Force. Мы также видели различные алгоритмы грубой силы, которые вы можете применять в своем приложении.
Рекомендуемые статьи
Это было руководство по алгоритму грубой силы. Здесь мы обсудили основные понятия алгоритма грубой силы. Вы также можете просмотреть наши другие предлагаемые статьи, чтобы узнать больше -
- Что такое алгоритм?
- Алгоритм Интервью Вопросы
- Введение в алгоритм
- Алгоритм в программировании