Въведение в алгоритма на грубата сила
„Данните са новата петрол“ това е новата мантра, която управлява световната икономика. Ние живеем в дигиталния свят и всеки бизнес се върти около данни, които се превръщат в печалби и помагат на индустриите да изпреварят конкуренцията си. С бързата дигитализация, експоненциалното увеличаване на бизнес модела, базиран на приложението, киберпрестъпленията са постоянна заплаха. Една такава често срещана дейност, която хакерите извършват, е грубата сила.
Brute Force е пробен и грешен подход, при който нападателите използват програми, за да изпробват различни комбинации, за да пробият във всеки уебсайт или система. Те използват автоматизиран софтуер за многократно генериране на комбинации от потребителски идентификатор и пароли, докато в крайна сметка не генерират правилната комбинация.
Търсене на груба сила
Търсене на груба сила е най-разпространеният алгоритъм за търсене, тъй като не изисква никакви познания в областта на домейните, всичко, което се изисква, е описание на състоянието, легални оператори, първоначалното състояние и описанието на състояние на целта. Той не подобрява производителността и напълно разчита на изчислителната мощ, за да изпробва възможни комбинации.
Алгоритъмът на грубата сила търси всички позиции в текста между 0 и nm независимо дали появата на шаблона започва там или не. След всеки опит той измества шаблона надясно с точно 1 позиция. Временната сложност на този алгоритъм е O (m * n). така че ако търсим n символа в низ от m символи, тогава ще са необходими n * m опити.
Нека видим класически пример на пътуващ продавач, за да разберем алгоритъма по лесен начин.
Да предположим, че един продавач трябва да измине 10 различни града в дадена страна и той иска да определи най-кратките възможни маршрути от всички възможни комбинации. Тук алгоритъмът на грубата сила просто изчислява разстоянието между всички градове и избира най-краткото.
Друг пример е да направите опит за счупване на 5-цифрената парола, тогава грубата сила може да отнеме до 10 5 опита за пробиване на кода.
Сортиране на груба сила
В техниката на сортиране на груба сила списъкът с данни се сканира многократно, за да се намери най-малкият елемент в списъка. След всяка итерация над списъка, той замества най-малкия елемент в горната част на стека и стартира следващата итерация от вторите най-малки данни в списъка.
Горното твърдение може да бъде написано в псевдо-код, както следва.
Тук проблемът е в размер "n" и основната операция е "ако" тест, където данните се сравняват при всяка итерация. Няма да има разлика между най-лошия и най-добрия случай, тъй като no swap винаги е n-1.
Брута сила съвпадение на низ
Ако всички символи в шаблона са уникални, тогава съвпадението на нивата на груба сила може да се приложи със сложността на Big O (n). където n е дължината на низа. Brute force Сравнението на низове сравнява шаблона с подреждането на текстов знак по символ, докато не получи несъответстващ символ. Щом бъде открито несъответствие, останалият символ на подреда се отпада и алгоритъмът преминава към следващата подреда.
По-долу псевдо кодовете обясняват логиката на съвпадение на низове. Тук алгоритъмът се опитва да търси модел на P (0… m-1) в текста T (0… .n-1).
тук най-лошият случай би бил, когато преминаването към друга подреда не се направи до сравнението на M Th .
Най-близка двойка
Определяне на проблем: За да откриете двете най-близки точки в набор от n точки в двумерната декартова равнина. Има n брой сценарии, при които възниква този проблем. Пример от реалния живот би бил в система за контрол на въздушното движение, където трябва да наблюдавате самолетите, летящи близо един до друг и трябва да откриете най-безопасното минимално разстояние, което тези самолети трябва да издържат.
Източник: Wikipedia
Алгоритъмът на грубата сила изчислява разстоянието между всеки отделен набор от точки и връща индексите на точката, за която разстоянието е най-малко.
Груба сила решава този проблем с времевата сложност на (O (n2)), където n е броят на точките.
По-долу псевдокодът използва алгоритъма на грубата сила, за да намери най-близката точка.
Изпъкнал корпус
Изложение на проблема : Изпъкнал корпус е най-малкият многоъгълник, който съдържа всички точки. Изпъкналият корпус на множество s на точката е най-малкият изпъкнал многоъгълник, съдържащ s.
Изпъкналият корпус за този набор от точки е изпъкналият многоъгълник с върхове при P1, P5, P6, P7, P3
Линеен сегмент P1 и Pn от набор от n точки е част от изпъкналия корпус, ако и само ако всички останали точки на множеството се намират вътре в границата на многоъгълника, образувана от линейния сегмент.
Нека да го свържем с гумената лента,
Точка (x1, y1), (x2, y2) прави линията ax + от = c
Когато a = y2-y1, b = x2-x1 и c = x1 * y2 - x2 * y1 и раздели равнината на ax + by-c 0
Така че трябва да проверим ax + by-c за останалите точки.
Груба сила решава този проблем с времевата сложност на O (n 3 )
Изчерпателно търсене
За дискретни проблеми, при които не е известно ефективно решение, се налага да се тестват всяко възможно решение последователно.
Изчерпателното търсене е дейност за намиране на всички възможни решения на проблем по систематичен начин.
Нека се опитаме да разрешим Проблема на продавача на пътници (TSP), използвайки изчерпателен алгоритъм за търсене на Brute.
Изложение на проблема: Има n градове, които продавачът трябва да пътува, той иска да намери най-краткия маршрут, който обхваща всички градове.
Обмисляме веригата Хамилтън да разреши този проблем. Ако съществува верига, тогава всяка точка може да стартира върхове и крайни върхове. След като стартовите върхове са избрани, тогава ни е необходим само редът за останалите върхове, т.е. n-1
Тогава ще има (n-1)! Възможните комбинации и общите разходи за изчисляване на пътя ще бъдат O (n). по този начин общата времева сложност ще бъде O (n!).
заключение
Сега, когато стигнахме до края на този урок, надявам се, момчета, сега да имате добра представа за това какво е Brute Force. Също така видяхме различни алгоритъм на Brute force, които можете да приложите във вашето приложение.
Препоръчителни статии
Това е ръководство за алгоритма на Brute Force. Тук обсъдихме основните понятия от алгоритма на грубата сила. Можете да разгледате и другите ни предложени статии, за да научите повече -
- Какво е алгоритъм?
- Въпроси за интервю за алгоритъм
- Въведение в алгоритъма
- Алгоритъм в програмирането