Odkrywca lub wynalazca | László Babai |
---|---|
Data odkrycia | 1979 |
Na początku | Algorytm Davisa-Putnama |
Najgorszy przypadek | |
---|---|
Najlepszy przypadek |
W informatyce , wykorzystując algorytm Las Vegas jest rodzajem probabilistycznej algorytmu , który zawsze daje prawidłowy wynik; jego losowość zapewnia średnio lepszą wydajność czasową. Jak sugeruje David Harel w swojej książce o algorytmach, podobnie jak Motvani i Raghavan, randomizowane szybkie sortowanie jest paradygmatycznym przykładem algorytmu z Las Vegas.
Kiedy problem rozwiązywany przez algorytm ma kilka rozwiązań, na tych samych danych, jak w przypadku sortowania tablicy zawierającej równoważne klucze, algorytm Las Vegas może zwrócić jedno lub drugie z tych rozwiązań i robi to w nieprzewidywalny sposób.
W tej sekcji wyjaśniamy przykład losowego szybkiego sortowania, który jest algorytmem z Las Vegas.
Algorytm randomizowanego szybkiego sortowania lub randomizowanego szybkiego sortowania polega na sortowaniu tablicy elementów za pomocą funkcji dziel i zwyciężaj :
Wynikiem jest tablica składająca się z pewnego rodzaju tablicy A, po której następuje wartość przestawna, po której następuje rodzaj tablicy B.
Losowość jest na poziomie wyboru osi. Rezultatem jest posortowana tablica, niezależnie od wyboru przestawnych, tzn. Wynik jest zawsze poprawny. Z drugiej strony czas realizacji zależy od tych wyborów. W rzeczywistości jest to rodzaj często używany w przypadku dużych tablic, ponieważ z empirycznego punktu widzenia daje dobre wyniki w złożoności czasowej. Na rysunkach po prawej stronie algorytm jest uruchamiany dwukrotnie na tej samej próbce; widzimy, że otrzymujemy posortowaną tablicę w obu przypadkach, podczas gdy przestawne są wybierane losowo.
Aby zasymulować wyrocznię, dokonujemy losowego wyboru osi, mając nadzieję, że często da nam ona oś obrotu znajdującą się niedaleko mediany.
Wersja szybkiego sortowania z Las Vegas losowo wybiera punkt zwrotny na liście do sortowania, pozostawiając resztę agorytmu bez zmian. Oto kod w języku Python :
def separation(liste, pivot, i): """Entrée : une liste, un pivot et la place du pivot dans la liste Sortie : une liste listePetit contenant les éléments de liste strictement plus petits que le pivot et une liste listeGrand contentant, à l'exception du pivot, les éléments plus grands que le pivot""" listePetit = [] listeGrand = [] for k in range(len(liste)): """Cela permet d'exclure le pivot""" if k != i: if liste[k] >= pivot : listeGrand.append(liste[k]) else : listePetit.append(liste[k]) return listePetit, listeGrand def quicksort(liste): """Entrée : une liste Sortie : une liste avec les mêmes éléments triés par l'algorithme de tri rapide randomisé""" n = len(liste) if n == 1: """Une liste à 1 élément est toujours triée""" return liste else: """Choix du pivot AU HASARD dans la liste""" i = randint(0, n - 1) pivot = liste[i] """On sépare en 2 listes de taille strictement plus petite que n car le pivot n'appartient à aucune des deux listes""" liste1, liste2 = separation(liste, pivot, i) """Le résultat est la concaténation des deux sous-listes auparavant triés, avec le pivot entre elles""" return quicksort(liste1) + [pivot] + quicksort(liste2)Biorąc pod uwagę Las Vegas algorytm , Luby, Sinclair i Zuckerman studiował jak zminimalizować czas oczekiwania wymagany do uzyskania A w odpowiedzi . W tym celu przyjmują strategię, która wskazuje, kiedy ponownie uruchomić algorytm. Oznaczamy przez T A (x) czas wykonania A na wejściu x; tym razem nie zawsze jest to samo, jest to zmienna losowa .
Biorąc pod uwagę A i dane wejściowe x, strategie, takie jak Luby i in. rozważ je, mają następującą postać:
Tak więc strategia S ma drugi składnik, mianowicie nieskończoną sekwencję liczb całkowitych, dzięki czemu możemy napisać strategię w postaci S ( A , t 1 , t 2 , ...). Strategia jest optymalna, jeśli minimalizuje oczekiwany czas jej wykonania na x dla ustalonego A. Luby i in. daje optymalną strategię postaci S ( A , t *, t *, ...), gdzie t * zależy od rozkładu prawdopodobieństwa T A (x). Obliczenie t * wymaga znajomości tego rozkładu. Zwracamy uwagę na przewidywany czas realizacji optymalnej strategii.
Jednak ogólnie rozkład prawdopodobieństwa T A (x) nie jest znany. Dlatego Luby i wsp. pokazuje istnienie tzw. strategii uniwersalnej , której oczekiwanie czasu realizacji nie odbiega zbytnio od oczekiwania strategii optymalnej, czyli jej oczekiwanie . Ta strategia to S ( A , 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 1, ...) i nie wymaga, ponieważ widać, brak wiedzy o rozkładzie T A (x).
Algorytm Las Vegas to algorytm probabilistyczny (wykorzystujący przypadek) , który zawsze zapewnia poprawny wynik. W ten sposób algorytm zawsze zwróci rozwiązanie postawionego problemu, ale jego czasowa złożoność nie jest przewidywalna. Dokonując dobrych wyborów w kluczowych punktach wykonania algorytmu, trzeba być w stanie wykazać, że ta złożoność jest niewielka.
Algorytmy te zostały nazwane przez Laszlo Babai w 1979 r. Przez metonimię z algorytmami Monte-Carlo. Trzecia rodzina algorytmów probabilistycznych zostanie nazwana algorytmami Atlantic City w odniesieniu do licznych gier hazardowych rozgrywanych w tych trzech miastach.
Te algorytmy Monte Carlo są probabilistyczne algorytmy wykorzystujące szansę powrotu najlepszą możliwą odpowiedź w ustalonym czasie. Złożoność czasowa jest zatem ustalona dla tych algorytmów. Jednak poprawność wyniku obarczona jest niepewnością.
Algorytmy Atlantic CityTe algorytmy Atlantic City (w) stara się jak najlepiej z dwóch poprzednich metod. Ten typ algorytmu prawie zawsze zwraca poprawny wynik w prawie zawsze ustalonym czasie. Niepewność polega zatem na złożoności czasowej i dokładności wyniku.
WniosekWyrażone inaczej: