Wyszukiwanie siłowe - Brute-force search

W informatyce , poszukiwaniu brute-force lub wyczerpujących poszukiwaniach , znany także jako generowanie i badania , jest bardzo ogólny rozwiązywania problemów techniki i algorytmicznych paradygmat , który składa się z systematycznie wyliczanie wszystkich możliwych kandydatów do roztworu i sprawdzenie, czy każdy spełnia kandydujących oświadczeniem problemem jest .

Algorytm siłowy, który znajduje dzielniki liczby naturalnej n , wyliczyłby wszystkie liczby całkowite od 1 do n i sprawdziłby, czy każda z nich dzieli n bez reszty. Podejście brutalnej siły dla układanki z ośmioma damami zbadałoby wszystkie możliwe układy 8 pionów na 64-kwadratowej szachownicy i dla każdego układu sprawdzałoby, czy każda (hetmanowa) figura może atakować inną.

Chociaż przeszukiwanie siłowe jest proste do wdrożenia i zawsze znajdzie rozwiązanie, jeśli takie istnieje, koszty wdrożenia są proporcjonalne do liczby możliwych rozwiązań - co w wielu praktycznych problemach ma tendencję do bardzo szybkiego wzrostu wraz ze wzrostem rozmiaru problemu ( § Eksplozja kombinatoryczna ). Dlatego wyszukiwanie brute-force jest zwykle używane, gdy rozmiar problemu jest ograniczony lub gdy istnieją heurystyki specyficzne dla problemu , których można użyć do zredukowania zestawu rozwiązań kandydujących do rozmiaru umożliwiającego zarządzanie. Metodę stosuje się również wtedy, gdy prostota implementacji jest ważniejsza niż szybkość.

Dzieje się tak na przykład w krytycznych zastosowaniach, w których jakiekolwiek błędy w algorytmie miałyby bardzo poważne konsekwencje lub w przypadku korzystania z komputera do udowodnienia twierdzenia matematycznego . Przeszukiwanie siłowe jest również przydatne jako metoda odniesienia przy porównywaniu innych algorytmów lub metaheurystyki . Rzeczywiście, wyszukiwanie siłowe może być postrzegane jako najprostsza metaheurystyka . Brute force search nie powinno być mylone z backtrackingiem , w którym duże zestawy rozwiązań można odrzucić bez wyliczania ich wprost (jak w podręczniku komputerowym rozwiązaniu problemu ośmiu królowych powyżej). Metoda brute-force znajdowania pozycji w tabeli - mianowicie sekwencyjne sprawdzanie wszystkich wpisów tej ostatniej - nazywa się przeszukiwaniem liniowym .

Wdrażanie przeszukiwania siłowego

Podstawowy algorytm

W kolejności kandydat na P po obecnym c .

  1. ważność ( p , c ) Sprawdź, czy kandydujący C jest rozwiązaniem dla P .
  2. wyjście ( P , c ): użyj rozwiązania c z P stosownie do zastosowania.

Następna procedura musi też powiedzieć, kiedy nie ma więcej kandydatów na przykład P , po bieżącym jednej C . Wygodnym sposobem jest zwrócenie „kandydata zerowego”, pewnej konwencjonalnej wartości danych Λ, która różni się od każdego prawdziwego kandydata. Podobnie pierwsza procedura powinna powrócić X, jeżeli nie ma w ogóle kandydatów na przykład P . Metoda brutalnej siły jest następnie wyrażana przez algorytm

cfirst(P)
while c ≠ Λ do
    if valid(P,c) then
        output(P, c)
    cnext(P, c)
end while

Na przykład, szukając dzielników liczby całkowitej n , danymi instancji P jest liczba n . Wywołanie first ( n ) powinno zwrócić liczbę całkowitą 1, jeśli n ≥ 1, lub Λ w przeciwnym razie; wywołanie next ( n , c ) powinno zwrócić c + 1, jeśli c < n , i Λ w przeciwnym razie; a valid ( n , c ) powinno zwracać prawdę wtedy i tylko wtedy, gdy c jest dzielnikiem liczby n . (W rzeczywistości, jeśli wyboru X się n + 1, testy n ≥ 1 c < n to konieczne). Określenie siłowych wyszukiwania algorytm powyżej wywoła wyjściowe dla każdego kandydata, który stanowi roztwór do danej instancji P . Algorytm można łatwo zmodyfikować, aby zatrzymać się po znalezieniu pierwszego rozwiązania lub określonej liczby rozwiązań; lub po przetestowaniu określonej liczby kandydatów lub po spędzeniu określonej ilości czasu procesora .

Eksplozja kombinatoryczna

Główną wadą metody brutalnej siły jest to, że w przypadku wielu rzeczywistych problemów liczba naturalnych kandydatów jest zbyt duża. Na przykład, jeśli szukamy dzielników liczby, jak opisano powyżej, liczba testowanych kandydatów będzie podana jako liczba n . Więc jeśli n ma szesnaście cyfr dziesiętnych, powiedzmy, wyszukiwanie będzie wymagało wykonania co najmniej 10 15 instrukcji komputerowych, co zajmie kilka dni na typowym komputerze . Jeśli n jest losową 64- bitową liczbą naturalną, która ma średnio około 19 cyfr dziesiętnych, poszukiwanie zajmie około 10 lat. Ten gwałtowny wzrost liczby kandydatów, wraz ze wzrostem ilości danych, pojawia się przy różnego rodzaju problemach. Na przykład, jeśli szukamy konkretnego przestawienia 10 liter, to mamy 10! = 3 628 800 kandydatów do rozważenia, które typowy komputer PC może wygenerować i przetestować w czasie krótszym niż jedna sekunda. Jednak dodanie jeszcze jednej litery - co oznacza tylko 10% wzrost rozmiaru danych - pomnoży liczbę kandydatów przez 11, co oznacza wzrost o 1000%. W przypadku 20 liter liczba kandydatów wynosi 20!, Czyli około 2,4 × 10 18 lub 2,4 tryliona ; a poszukiwania potrwają około 10 lat. To niepożądane zjawisko jest powszechnie nazywane eksplozją kombinatoryczną lub przekleństwem wymiarowości .

Jednym z przykładów przypadku, w którym złożoność kombinatoryczna prowadzi do granicy rozwiązalności, jest układanie szachów . Szachy nie są grą rozwiązaną . W 2005 roku wszystkie szachy zakończone sześcioma lub mniej figurami zostały rozwiązane, pokazując wynik każdej pozycji, jeśli rozegrano idealnie. Uzupełnienie podstawy stołu o jeszcze jedną figurę szachową zajęło dziesięć lat, tworząc w ten sposób siedmioczęściową podstawę stołu. Dodanie jeszcze jednej figury do zakończenia szachowego (w ten sposób utworzenie 8-częściowej podstawy stołu) jest uważane za nierealne ze względu na dodatkową złożoność kombinatoryczną.

Przyspieszenie wyszukiwania brutalnej siły

Jednym ze sposobów przyspieszenia algorytmu brutalnej siły jest zmniejszenie przestrzeni poszukiwań, czyli zbioru rozwiązań kandydujących, poprzez zastosowanie heurystyki specyficznej dla klasy problemu. Na przykład w przypadku problemu z ośmioma hetmanami wyzwaniem jest umieszczenie ośmiu hetmanów na standardowej szachownicy tak, aby żadna hetman nie atakowała żadnej innej. Ponieważ każda królowa może być umieszczona na dowolnym z 64 pól, w zasadzie jest 64 8 = 281 474 976 710 656 możliwości do rozważenia. Jednakże, ponieważ wszystkie hetmany są takie same i nie można umieścić dwóch hetmanów na tym samym kwadracie, wszyscy kandydaci mają możliwość wyboru zestawu 8 kwadratów z zestawu wszystkich 64 kwadratów; co oznacza 64 wybierz 8 = 64! / (56! * 8!) = 4 426 165 368 kandydatów - około 1/60 000 poprzedniego oszacowania. Ponadto żaden układ z dwiema królowymi w tym samym rzędzie lub tej samej kolumnie nie może być rozwiązaniem. Dlatego możemy dodatkowo ograniczyć zbiór kandydatów do tych ustaleń.

Jak pokazuje ten przykład, odrobina analizy często prowadzi do radykalnego zmniejszenia liczby proponowanych rozwiązań i może zmienić trudny do rozwiązania problem w trywialny.

W niektórych przypadkach analiza może sprowadzić kandydatów do zbioru wszystkich ważnych rozwiązań; to znaczy, może dać algorytm, który bezpośrednio wyliczy wszystkie pożądane rozwiązania (lub znajdzie jedno rozwiązanie, jeśli jest to właściwe), bez tracenia czasu na testy i generowanie nieprawidłowych kandydatów. Na przykład w przypadku zadania „znajdź wszystkie liczby całkowite od 1 do 1 000 000, które są równo podzielne przez 417”, naiwne rozwiązanie brutalnej siły wygeneruje wszystkie liczby całkowite z zakresu, sprawdzając każdą z nich pod kątem podzielności. Jednak problem ten można rozwiązać znacznie skuteczniej, zaczynając od 417 i wielokrotnie dodając 417, aż liczba przekroczy 1000000 - co wymaga tylko 2398 (= 1000000 ÷ 417) kroków i żadnych testów.

Zmiana kolejności przestrzeni wyszukiwania

W aplikacjach, które wymagają tylko jednego rozwiązania, a nie wszystkich rozwiązań, przewidywany czas trwania wyszukiwania brutalnego często zależy od kolejności, w jakiej kandydaci są testowani. Z reguły najpierw należy przetestować najbardziej obiecujących kandydatów. Na przykład, szukając właściwego dzielnika liczby losowej n , lepiej jest wyliczyć kandydujące dzielniki w kolejności rosnącej, od 2 do n - 1 , niż odwrotnie - ponieważ prawdopodobieństwo, że n jest podzielne przez c, wynosi 1 / c . Co więcej, na prawdopodobieństwo, że kandydat będzie ważny, często wpływają poprzednie zakończone niepowodzeniem próby. Na przykład, rozważmy problem ze znalezieniem 1 bitu w danym 1000-bitowy ciąg P . W tym przypadku rozwiązaniami kandydującymi są indeksy od 1 do 1000, a kandydat c jest ważny, jeśli P [ c ] = 1 . Teraz przypuśćmy, że pierwszy bit P ma równe prawdopodobieństwo równe 0 lub 1 , ale każdy następny bit jest równy poprzedniemu z prawdopodobieństwem 90%. Jeśli kandydaci zostaną wyliczeni w kolejności rosnącej, od 1 do 1000, liczba t kandydatów zbadanych przed sukcesem będzie wynosiła średnio około 6. Z drugiej strony, jeśli kandydaci zostaną wyliczeni w kolejności 1,11,21,31 ... 991,2,12,22,32 itd., Oczekiwana wartość t będzie tylko trochę większa niż 2. ogólnie przestrzeń poszukiwań powinna być wyliczona w taki sposób, aby następny kandydat był najprawdopodobniej ważny, biorąc pod uwagę, że poprzednie próby nie były . Więc jeśli prawidłowe rozwiązania mogą być w pewnym sensie „zgrupowane”, to każdy nowy kandydat powinien być tak daleki od poprzednich, jak to tylko możliwe, w tym samym sensie. Odwrotna sytuacja ma miejsce, oczywiście, jeśli istnieje prawdopodobieństwo, że rozwiązania zostaną rozłożone bardziej równomiernie, niż można by się spodziewać przez przypadek.

Alternatywy dla wyszukiwania siłowego

Istnieje wiele innych metod wyszukiwania lub metaheurystyki, które mają na celu wykorzystanie różnego rodzaju częściowej wiedzy, jaką można mieć na temat rozwiązania. Heurystyki mogą być również używane do wczesnego odcinania części wyszukiwania. Jednym z przykładów jest zasada minimax przy przeszukiwaniu drzew gry, która eliminuje wiele poddrzew na wczesnym etapie wyszukiwania. W niektórych dziedzinach, takich jak analiza języka, techniki takie jak analiza wykresów mogą wykorzystywać ograniczenia w problemie, aby zredukować wykładniczy problem złożoności do problemu złożoności wielomianowej. W wielu przypadkach, takich jak problemy z spełnieniem ograniczeń , można radykalnie zmniejszyć przestrzeń wyszukiwania za pomocą propagacji ograniczeń , która jest skutecznie zaimplementowana w językach programowania z ograniczeniami . Przestrzeń wyszukiwania problemów można również zmniejszyć, zastępując pełny problem wersją uproszczoną. Na przykład w szachach komputerowych zamiast obliczać pełne drzewo minimaksów wszystkich możliwych ruchów do końca gry, obliczane jest bardziej ograniczone drzewo możliwości minimaksu, przy czym drzewo jest przycinane przy określonej liczbie ruchów, a reszta drzewa jest aproksymowane przez statyczną funkcję oceny .

W kryptografii

W kryptografii , A atak brute-force wymaga systematycznego sprawdzania wszystkich możliwych kluczy , aż zostanie znaleziony poprawny klucz. Strategia ta może być teoretycznie zastosowana przeciwko jakimkolwiek zaszyfrowanym danym (z wyjątkiem jednorazowej podkładki ) przez atakującego, który nie jest w stanie wykorzystać żadnej słabości systemu szyfrowania, która w innym przypadku ułatwiłaby jego zadanie.

Klucz długość używany w szyfrowaniu określa praktyczne możliwości przeprowadzenia ataku brute force, z dłuższymi kluczami wykładniczo trudniejsze do złamania niż krótsze. Ataki siłowe mogą być mniej skuteczne poprzez zaciemnianie danych do zaszyfrowania, co utrudnia atakującemu rozpoznanie, kiedy złamał kod. Jednym z mierników siły systemu szyfrującego jest to, ile czasu teoretycznie zajmie atakującemu przeprowadzenie skutecznego ataku brutalnej siły przeciwko niemu.

Bibliografia

Zobacz też