Lekcja 6. Metoda siłowa.¶
W niniejszej lekcji omówimy pokrótce, ilustrując to przykładami, tak zwaną metodę siłową.
Algorytm siłowy (z angielskiego - brute force) jest to taki algorytm, którego działanie można streścić następująco: polega on na sukcesywnym sprawdzaniu wszystkich możliwych kombinacji, w poszukiwaniu rozwiązania problemu. Algorytm taki, jest zazwyczaj nieoptymalny ale jednocześnie najprostszy w implementacji. Dla niektórych klas problemów, jest to również podejście, pod pewnymi warunkami, jedynie niezawodne. Co to oznacza? Stosując takie podejście w programowaniu, rozwiązujemy problem przez weryfikację i ocenę wszystkich wariantów postępowania. Gdybyśmy dysponowali, dowolnie długim czasem na poszukiwanie rozwiązania oraz zasobami sprzętowymi (na przykład nieskończenie dużą pamięcią operacyjną lub przestrzenią dyskową), to algorytm taki zakończy się zawsze powodzeniem. Nie bez powodu, algorytmy siłowe, bywają nazywane algorytmami naiwnymi.
W zasadzie, drogi czytelniku, zdarzyło Ci się już w trakcie tego kursu napotkać zagadnienia rozwiązane siłowo. Chociażby prosty kod, zaproponowany na początku Lekcji 2:
Tak, rozwiązanie tego problemu to algorytm siłowy. W wielu innych zadaniach i problemach przedstawionych na łamach tego kursu, intuicyjnie zastosowałeś w rozwiązaniu takie właśnie podejście. Bardzo często rozwiązania takie wymagają najmniej potocznego “kombinowania”, chociaż z matematyczną kombinatoryką, mają wiele wspólnego.
Zadajmy sobie trochę więcej trudu i, przeanalizujmy problem, polegający na generowaniu wszystkich możliwych haseł z zadanego zbioru znaków. Tak jak w poniższym przykładzie. Do dyspozycji mamy cztery znaki: A, b, C oraz d. Chcemy z tych znaków wygenerować wszystkie możliwe jedno, dwu, trzy i czteroelementowe, niepowtarzalne ciągi znaków. Algorytm siłowy, będzie polegał na sukcesywnym sprawdzaniu wszystkich kombinacji.
Analizując powyższy przykład, zapewne dojdziesz, do słusznego wniosku, że nie ma tu żadnego finezyjnego rozwiązania. Po prostu, program ten konsekwentnie generuje kolejne sekwencje.
Oczywiście tradycyjnie, możesz poeksperymentować z powyższym kodem. Nie polecamy Ci jednak byś przesadził z lista znaków oraz długością poszukiwanych ciągów (długością generowanych ciągów znaków, steruje się w tym kodzie za pośrednictwem argumentu funkcji xrange()). Dlaczego nie jest dobrze przesadzić? Prawdopodobnie, powyżej pewnych limitów, Twoja cierpliwość okaże się mniejsza niż ciekawość.
W analizie tego programu prawdopodobnie przyda Ci się, małe uzupełnienie dotyczące składni języka Python. Otóż, dopuszczalne są poniższe konstrukcje dotyczące tablic:
Można przy użyciu pętli for zapełniać w ten sposób listę elementami. Pamiętajmy, że dla danych typu str, możliwa jest operacja + (i+" dodawanie"). Dopuszczane jest również wszystko to co zostało powiedziane w lekcji 2 na temat wyciania sekwencji (przykład: i+j+k for i in lista1[::2] for j in lista2[::2] for k in lista3[::2]).
Po takiej uwadze, jaśniejszym powinny być kolejne iteracje działania programu, wyświetlmy, je modyfikując kod nieznacznie:
Jak widać, program konsekwentnie konstruuje rozwiązanie, na zasadzie “każdy z każdym”.
O związkach metody brute force, z kombinatoryką wspomniano nie bez przyczyny. Korzystając z kombinatoryki, spróbujmy policzyć ile jest możliwych takich haseł. Zagadnienie to jest sumą wariacji z powtórzeniami. Dla przypomnienia, wariację z powtórzeniami wykorzystujemy wtedy, gdy chcemy wiedzieć ile możemy stworzyć różnych układów k-elementowych, mając do dyspozycji n-elementów, przy czym kolejność elementów w układzie jest istotna, a elementy mogą się powtarzać.
Poprawność wyniku, uzyskanego metodą brutre force, można sprawdzić na przykład dodając do kodu instrukcje len(lista_kombinacji).
Generowanie ciągu znaków, tylko pozornie jest mało interesującym problemem. W świecie czarnych kapeluszy, hakerów czyhających na Twoje dane, algorytmy typu brute force są chlebem powszednim. Służą one na przykład do próby nielegalnego zdobycia hasła.
W ogólności metoda ta dobrze nadaje się do rozwiązywania wszelkich problemów kombinatorycznych, tam gdzie trudno jest opracować metody bardziej efektywne.
Zadanie 6.1
Opierając się na przykładzie pierwszym, spróbuj zaimplemenotować, przy użyciu metody siłowej, algorytm programu wypisującego wszystkie możliwe 4 elementowe ciągi spośród trzech różnych znaków przy założeniu, że drugi znak jest ustalony i wynosi x. Czy potrafisz narysować schemat blokowy takiego algorytmu?
Dyskusja na temat metody siłowej, jest dobrą okazją do podkreślania, że ten sam problem można rozwiązać na kilka sposobów. Prześledźmy to na klasycznym przykładzie. Postarajmy się dla danego przedziału liczbowego, znaleźć wszystkie liczby pierwsze (dla przypomnienia są to takie liczby, które mają tylko dwa dzielniki, jedynkę i samą siebie). Kod programu realzującego rozwiązanie siłowe zaimplementujemy w przy użyciu funkcji. Argumentem tej funkcji, jest koniec przedziału w którym poszukujemy liczb pierwszych. Początek przedziału jest ustalony i wynosi 1.
Program ten nie wyświetla znalezionych liczb pierwszych. By to zmienić i upewnić się, że program działa poprawnie, możesz zmodyfikować kod, usuwając komentarz w przedostatniej linii. Polecamy jednak by z oczywistych powodów zrobić to tylko dla małych zakresów (na przykład koniec < 100). Program ten, domyślnie, zwraca za to czas jego wykonania.
Zwróć uwagę na ten czas. Jest on obliczony przy użyciu modułu time używanego już w lekcji wcześniejszej. Czy można to zrobić bardziej optymalnie (szybciej)? Algorytmy siłowe, tak jak to zostało wspomniane nie są algorytmami optymalnymi. Niejednokrotnie, można znaleźć bardziej efektywne rozwiązania. W przypadku problemu znajdowania liczb pierwszych z zadanego przedziału, przykładem może być algorytm zwany sitem Erastotenesa. W implementacji tego algorytmu również posłużymy się funkcją, również jednoargumentową.
Opisać metodę tę możemy następująco: wypisuje się kolejno liczby naturalne od 2 do n. Liczba 2, pierwsza z wypisanych, jest liczbą pierwszą, pozostawia się ją i wykreśla wszystkie dalesze liczby podzielne przez 2, gdyż zgodnie z definicją, nie są to już liczby pierwsze. Po tej operacji, koeljną nie wykreśloną licznbą jest 3. Jest ona liczbą pierwszą, więc zostawia się ją ale wykreśla się wszystkie dalsze podzielne przez nią, a które nie zostały wykreślone jako podzielne przez 2. Schemat postępowania powtarza się dla kolejnych niewykreślonych liczb i powtarza w kolejnych iteracjach. Dojdzie się do momentu w którym w zadanym zbiorze pozostaną tylko liczby pierwsze.
Tu podobnie jak w metodzie siłowej, program domyślnie, nie wypisuje znalezionych liczb pierwszych. Podaje za to czas wykonania. Zwróć uwagę że czas wykonania tych dwóch programów, przy tym samym zakresie różni się o rzędy wielkości na niekorzyść metody siłowej. Zaletą z kolei tego podejścia, jest prostota implementacji. Kod algorytmu siłowego jest ideowo znacznie prostszy. Nie posiada żadnych pułapek.
Zadanie 6.2
Wnioskowanie o zysku czasowym algorytmu sita Erastotenesa, w porównaniu do algorytmu siłowego, mogłoby być poddane w wątpliwość dla pojedynczych testów. Czy potrafiłbyś, obronić tę tezę, przeprowadzając wielokrotne testy, analogiczne do zaproponowanych w sekcji Złożoność obliczeniowa z poprzedniej lekcji?
Przeszukiwanie sekwencji¶
Na początku tej lekcji zajęliśmy się problemem generowaniem ciągu znaków. W tej sekcji omówimy bardzo ważną klasę problemów. Zajmiemy się kwestią sprawdzania czy podany wzorzec (ang. pattern) jest elementem innego wzorca. W ogólności wzorcami tymi mogą być dowolne ciągi znaków, w tym w szczególności, na przykład sekwencje bitów, znaków ASCII, list, itp. Na potrzeby lekcji zawęzimy problem do następującego: chcemy sprawdzić czy w ciągu znaków o jakiejś długości znajduje się inny ciąg znaków o innej długości. Czyli na przykład: czy we frazie Mielonka i jajka zawarta jest fraza jajka. Omówmy jak realizowany jest algorytm siłowy oraz alternatywne dla niego, a ważne z punktu widzenia historii algorytmiki, alternatywne, subtelniejsze rozwiązania.
Gdzie znajduje zastosowanie przeszukiwanie sekwencji? Spotykamy się z nią bardzo często. W edytorach tekstu, w przeglądarkach internetowych, w menedżerach plików, wszędzie tam, gdzie mamy do czynienia z funkcją “szukaj”.
Algorytm siłowy przeszukiwania sekwencji¶
Zaimplementujmy metodę siłową w postaci funkcji. Pamiętajmy, że aby poszukiwanie wzorca reprezentowanego przez sekwencję P w tekście oznacoznym jako T miało sens, ilość znaków T > P o conajmniej jeden. Funkcja programu zawiera jedną pętlę for oraz jedną instrukcję while. Jeśli P zawarte jest w T to kod poniższego programu zwróci pozycję na której występuje ta zgodność.
Omawiany schemat postępowania jest najprostszym sposobem sprawdzenia czy zadany wzorzec znajduje się w tekście. Idea działania naiwnego algorytmu dla takiego zagadnienia, opiera się na porównywaniu odpowiednich znaków tekstu i wzorca. Porównanie to rozpoczyna się od pierwszej litery tekstu i wzorca. Jeśli znaki te są są zgodne to porównywany jest następny znak tekstu z następnym znakiem wzorca, itd. Natomiast, jeżeli dalej wystąpiła niezgodność dla dowolnej pozycji pomiędzy wzorcem a tekstem to algorytm rozpoczyna całą procedurę przeszukiwania od drugiego znaku tekstu i pierwszego znaku wzorca. Jeśli zostanie znaleziony cały szukany wzorzec, algorytm rozpoczyna przeszukiwanie od następnego znaku. Wzorzec jest zawsze „przesuwany” o jeden znak.
Zadanie 6.3
Zmodyfikuj powyższy kod tak by przeszukiwać czy we wzorcu T znajduje się odwrócony wzorzec P. Zaimplementuj funkcję błędu.
Przykład “mielonkowo - jajkowy”, prawdopodobnie nie jest zbyt klarowny. Przeanalizujmy zatem, krok po kroku, dużo prostszą konfigurację. Przyjmijmy za wzorzec P = "XYZ, a za tekst T = XYYYXYZ.
Zasada działania algorytmu siłowego poszukiwania wzorcu w tekście.
Jeśli zrozumieliśmy już w pełni zasadę działania tego algorytmu, spróbujmy wyłuskać jego wadę. Jest nią bardzo mała efektywność. Aby się o tym przekonać przeprowadzmy eksperyment myślowy: co się co się stanie jeśli spróbujemy, za jego pomocą, sprawdzić czy w tekście YYYYYYYYZ znajduje się wzorzec YYYZ. Nie jest trudno dojść do wniosku, że dla takiej konfiguracji proces przeszukiwania będzie trwał możliwie najdłużej. Już na samym początku okaże się, że niezgodność nieprzesuniętego wzorca względem tekstu, ujawni się dopiero przy czwartym znaku. Cały wzorzec zostanie przesunięty o jedną pozycję w prawo i znów jego niezgodność zostanie stwierdzona dopiero przy czwartym znaku. Dopiero kiedy wzorzec zostanie przesunięty na ostatnią możliwą pozycję względem tekstu, zostanie stwierdzona pełna zgodność.
Zadanie 6.4
Czy potrafisz pokusić się o oszacowanie złożoności obliczeniowej takiego algorytmu siłowego? Wykorzystaj do tego przykład z najmniej korzystną wzajemną konfiguracją ciągu znaków. Ile razy w takim wypadku będzie konieczny restart algorytmu, a ile w każdym cyklu będzie porównań znaków?
Algorytm niesiłowe przeszukiwania sekwencji¶
Istnieje wiele propozycji rozwiązania tego problemu, innych niż metodą siłową. Historia poszukiwania efektywniejszych, szybszych algorytmów dla takiej klasy problemów jest bogata, sięga lat 70 i 80 ubiegłego stulecia. Omówmy, pobieżnie alternatywne, historycznie ważne, dwa algorytmy poszukiwania wzorca w sekwencji. Poniższe kody programów, opierają się na kodach zaproponowanych w książce Data Structures & Algorithms in Python [TC], gdzie czytelnik znajdzie dokładną ich interpretację. Na potrzeby naszego kursu, przytoczone są w formie bardzo ważnych ciekawostek.
Algorytm Boyera i Moore’a¶
Pierwszym z nich jest algorytm Boyera i Moore’a. Algorytm ten opiera się na następujących pomysłach:
- porównywanie wzorca i tekstu można rozpocząć od ostatniego znaku,
- w sytuacji w której aktualnie porównywany znak tekstu nie znajduje się we wzorcu, możliwe jest przesunięcie wzorca w prawo o całą jego długość,
- a jeśli występuje to algorytm przesuwa wzorzec o tyle pozycji w prawo aby zgodne litery były na tej samej względem siebie pozycji.
Jeśli wzorzec istotnie jest częścią tekstu, to funkcja zawarta w poniższej implementacji tego algorytmu, zwróci pozycję w tekście, na której ów wzorzec się znajduje. Poeksperymentuj z tym kodem do woli.
Idea działania tego algorytmu analizowana na sucho wydaje się dość skomplikowane. Dla ułatwienia spróbujmy ja zwizualizować.
Przykład działania algorytmu Boyera i Moore’a.
Algorytm K-M-P¶
Drugim z algorytmów niesiłowych poszukiwania wzorca w tekście, jest algorytm zaproponowany niezależnie przez: Donalda Knutha we współpracy z Vaughanem Pratta oraz Jamesa Morrisa. Wadą podejścia naiwnego w rozwiązywaniu problemu poszukiwania wzorca jest jego czułość na konfigurację danych (patrz: komentarz pod opisem metody brute force wyszukiwania wzorca). W dużym skrócie, pomysł autorów tego rozwiązania, opiera się na tym, że znajomośc struktury tekstu, w którym wyszukujemy wzorca, może poleprzyć szybkość wyszukiwania. Poszukiwany wzorzec zawiera w sobie informację pozwalającą określić, gdzie powinna się zacząć kolejna próba dopasowania, pomijając ponowne porównywanie już dopasowanych znaków.
“Prosta” implementacja tego algorytmu zaprezentowana jest poniżej. Analizę tego kodu pozostawiamy wnikliwym, cierpliwym czytelnikom. Podobnnie jak dla algorytmu Boyera i Moore’a, kod tego algorytmu opiera się na funkcjach. Jedną z nich (znajdz_metoda_kmp())jest funkcja zwracająca pozycję zgodności wzorca z tekstem (o ile oczywiście takowa nastapi). Druga z funkcji (funkcja_bledu()) pozwala określić kolejne przesunięcia.
| [TC] | Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser, Data Structures and Algorithms in Python, Wiley 2013 |