Wprowadzenie do algorytmu Brute Force
„Dane to nowa ropa” to nowa mantra rządząca światową gospodarką. Żyjemy w cyfrowym świecie, a każda firma obraca się wokół danych, które przekładają się na zyski i pomagają branżom wyprzedzać konkurencję. Dzięki szybkiej cyfryzacji, wykładniczemu wzrostowi modelu biznesowego opartego na aplikacjach, cyberprzestępczość stanowi stałe zagrożenie. Jednym z takich powszechnych działań hakerów jest brutalna siła.
Brute Force to metoda prób i błędów, w której atakujący używają programów do wypróbowania różnych kombinacji, aby włamać się na dowolne witryny lub systemy. Używają zautomatyzowanego oprogramowania do powtarzalnego generowania kombinacji identyfikatora użytkownika i hasła, aż ostatecznie wygeneruje odpowiednią kombinację.
Poszukiwania siłowe
Wyszukiwanie z użyciem siły brutalnej jest najczęstszym algorytmem wyszukiwania, ponieważ nie wymaga żadnej wiedzy w dziedzinie, wystarczy opis stanu, operatorzy prawni, stan początkowy i opis stanu celu. Nie poprawia wydajności i całkowicie polega na mocy obliczeniowej, aby wypróbować możliwe kombinacje.
Algorytm siły brutalnej przeszukuje wszystkie pozycje w tekście między 0 a nm, niezależnie od tego, czy wystąpienie wzorca zaczyna się tam, czy nie. Po każdej próbie przesuwa wzór w prawo o dokładnie 1 pozycję. Złożoność czasowa tego algorytmu wynosi O (m * n). więc jeśli szukamy n znaków w ciągu m znaków, to zajmie n * m prób.
Zobaczmy klasyczny przykład podróżującego sprzedawcy, który w prosty sposób rozumie algorytm.
Załóżmy, że sprzedawca musi przejechać 10 różnych miast w kraju i chce wyznaczyć możliwie najkrótsze trasy spośród wszystkich możliwych kombinacji. Tutaj algorytm brutalnej siły po prostu oblicza odległość między wszystkimi miastami i wybiera najkrótsze.
Innym przykładem jest próba złamania 5-cyfrowego hasła, a następnie brutalna siła może podjąć do 10 5 prób złamania kodu.
Sortowanie Brute Force
W technice sortowania z użyciem siły brutalnej lista danych jest skanowana wiele razy w celu znalezienia najmniejszego elementu na liście. Po każdej iteracji na liście zastępuje najmniejszy element na górze stosu i rozpoczyna następną iterację od drugich najmniejszych danych na liście.
Powyższe oświadczenie można zapisać pseudokodem w następujący sposób.
Tutaj problemem jest rozmiar „n”, a podstawową operacją jest test „jeśli”, w którym elementy danych są porównywane w każdej iteracji. Nie będzie różnicy między najgorszym i najlepszym przypadkiem, ponieważ liczba zamian to zawsze n-1.
Dopasowywanie strun Brute Force
Jeśli wszystkie znaki we wzorze są unikalne, wówczas można zastosować dopasowanie ciągu sił Brute ze złożonością Big O (n). gdzie n jest długością łańcucha. Brute force Dopasowywanie ciągów porównuje wzorzec z podciągiem tekstowym znak po znaku, dopóki nie uzyska niezgodnego znaku. Gdy tylko zostanie znalezione niedopasowanie, pozostały znak podłańcucha jest usuwany, a algorytm przechodzi do następnego podłańcucha.
Poniższe pseudo-kody wyjaśniają logikę dopasowywania łańcucha. Algorytm próbuje tutaj znaleźć wzór P (0… m-1) w tekście T (0… .n-1).
w tym przypadku najgorszym przypadkiem byłoby przejście do innego substratu dopiero po porównaniu M Th .
Najbliższa para
Problem: Aby znaleźć dwa najbliższe punkty w zbiorze n punktów w dwuwymiarowej płaszczyźnie kartezjańskiej. Istnieje n liczba scenariuszy, w których pojawia się ten problem. Przykładem może być system kontroli ruchu lotniczego, w którym musisz monitorować samoloty lecące blisko siebie i znaleźć najbezpieczniejszą minimalną odległość, jaką te samoloty powinny zachować.
Źródło: Wikipedia
Algorytm siły brutalnej oblicza odległość między każdym odrębnym zestawem punktów i zwraca indeks punktu, dla którego odległość jest najmniejsza.
Brutalna siła rozwiązuje ten problem ze złożonością czasową (O (n2)), gdzie n jest liczbą punktów.
Poniżej pseudo-kod wykorzystuje algorytm brutalnej siły, aby znaleźć najbliższy punkt.
Wypukły kadłub
Opis problemu : Wypukły kadłub jest najmniejszym wielokątem, który zawiera wszystkie punkty. Wypukły kadłub zestawu s punktu jest najmniejszym wypukłym wielokątem zawierającym s.
Wypukły kadłub dla tego zestawu punktów to wypukły wielokąt z wierzchołkami na P1, P5, P6, P7, P3
Segment linii P1 i Pn zbioru n punktów jest częścią wypukłego kadłuba wtedy i tylko wtedy, gdy wszystkie pozostałe punkty zbioru leżą w granicach wieloboku utworzonego przez segment linii.
Odwołajmy to do gumki,
Punkt (x1, y1), (x2, y2) tworzą linię ax + o = c
Gdy a = y2-y1, b = x2-x1 ic = x1 * y2 - x2 * y1 i dzieli płaszczyznę przez ax + by-c 0
Musimy więc sprawdzić ax + by-c dla innych punktów.
Brutalna siła rozwiązuje ten problem ze złożonością czasową O (n 3 )
Wyczerpujące wyszukiwanie
W przypadku problemów dyskretnych, w których nie ma znanego skutecznego rozwiązania, konieczne staje się testowanie każdego możliwego rozwiązania w sposób sekwencyjny.
Wyczerpujące wyszukiwanie to czynność polegająca na systematycznym wyszukiwaniu wszystkich możliwych rozwiązań problemu.
Spróbujmy rozwiązać problem Podróżującego sprzedawcy (TSP) za pomocą algorytmu brutalnego wyszukiwania wyczerpującego.
Opis problemu: Istnieje n miast, które sprzedawca musi podróżować, chce znaleźć najkrótszą trasę, która obejmuje wszystkie miasta.
Rozważamy obwód Hamilton w celu rozwiązania tego problemu. Jeśli obwód istnieje, dowolny punkt może rozpoczynać i kończyć wierzchołki. Po wybraniu wierzchołków początkowych potrzebujemy tylko kolejności dla pozostałych wierzchołków, tj. N-1
Wtedy byłoby (n-1)! Możliwe kombinacje i całkowity koszt obliczenia ścieżki to O (n). zatem całkowita złożoność czasowa wynosiłaby O (n!).
Wniosek
Teraz, kiedy osiągnęliśmy koniec tego samouczka, mam nadzieję, że macie już dobre pojęcie o tym, czym jest Brute Force. Widzieliśmy również różne algorytmy Brute force, które możesz zastosować w swojej aplikacji.
Polecane artykuły
To był przewodnik po algorytmie Brute Force. Omówiliśmy tutaj podstawowe pojęcia algorytmu Brute Force. Możesz także przejrzeć nasze inne sugerowane artykuły, aby dowiedzieć się więcej -
- Co to jest algorytm?
- Pytania do wywiadu algorytmicznego
- Wprowadzenie do algorytmu
- Algorytm w programowaniu