W algorytmiki , A Monte Carlo algorytm jest randomizowane algorytm którego czas wykonania jest deterministyczny, ale wynik, który może być nieprawidłowe z pewnym prawdopodobieństwem (zwykle minimalne). Innymi słowy, algorytm Monte-Carlo to algorytm wykorzystujący źródło przypadku, którego czas obliczeń jest znany od początku (nie jest zaskoczeniem co do czasu trwania obliczeń), jednak jego wynik może nie być odpowiedź na postawiony problem, ale jest to bardzo rzadki przypadek. Zaletą takich algorytmów jest małe prawdopodobieństwo awarii i szybkość.
Dwa inne typy algorytmów probabilistycznych to rodzina algorytmów Las Vegas i rodzina algorytmów Atlantic City (en) . Algorytmy Las Vegas pobierają losowy czas wykonania, ale nadal zapewniają poprawną odpowiedź. Algorytmy Atlantic City dają prawdopodobnie poprawną odpowiedź w prawdopodobnie krótkim czasie. Algorytm Monte-Carlo można przekształcić w algorytm Las Vegas, jeśli istnieje procedura umożliwiająca weryfikację poprawności wyniku. Rzeczywiście, wystarczy uruchomić algorytm Monte-Carlo, dopóki nie da poprawnej odpowiedzi.
Nawiasem mówiąc, kwalifikator Monte-Carlo odnosi się do Księstwa Monako i jego słynnego kasyna Casino de Monte-Carlo , mekki gier losowych.
Algorytm Monte-Carlo ma dwie cechy: po pierwsze jest randomizowany , to znaczy wykorzystuje do obliczeń zagrożenie, po drugie czas jego wykonania jest deterministyczny. Jej losowy charakter przejawia się w wyniku, który może być błędny z pewnym prawdopodobieństwem (zwykle minimalnym), ale który można rygorystycznie określić ilościowo.
Test pierwszości Solovaya-Strassena to test, który określa, czy dana liczba jest liczbą pierwszą . Zawsze odpowiada prawda dla liczb pierwszych, podczas gdy dla liczb złożonych (tj. Innych niż pierwsze) odpowiada fałsz z prawdopodobieństwem co najmniej ½, a prawda z prawdopodobieństwem co najwyżej ½. Zatem fałszywe odpowiedzi algorytmu są poprawne, podczas gdy prawdziwe odpowiedzi są losowe; innymi słowy algorytm jest nastawiony na fałsz.
O ile odpowiedź zwrócona przez deterministyczny algorytm jest zawsze poprawna, nie ma to miejsca w przypadku algorytmów Monte-Carlo, co może mieć miejsce tylko w przypadku błędu systematycznego. Przypuśćmy, że jest to kwestia rozwiązania problemu decyzyjnego, mówi się, że algorytmy te są albo bezstronne, albo nastawione na fałsz lub tendencyjne w kierunku prawdy. Algorytm Monte-Carlo z nastawieniem fałszywie jest zawsze poprawny, gdy zwraca fałsz ; algorytm nastawiony na prawdę jest zawsze poprawny, gdy zwraca prawdę . Co do bezstronnych algorytmów Monte-Carlo, ich odpowiedź (prawda lub fałsz) będzie niepoprawna lub poprawna z pewnym ograniczonym prawdopodobieństwem.
W języku angielskim mówimy o błędzie jednostronnym i błędzie dwustronnym .
Biorąc pod uwagę tendencyjny algorytm Monte Carlo, jego prawdopodobieństwo niepowodzenia można zmniejszyć (i zwiększyć prawdopodobieństwo sukcesu), wykonując go k razy. Rozważmy ponownie algorytm Solovaya-Strassena, który jest nastawiony na fałsz. Możemy go wykonać kilka razy, zwracając prawdę, jeśli odpowiada prawdzie podczas k kroków iteracji i fałsz w przeciwnym razie. Tak więc, jeśli liczba jest liczbą pierwszą, to odpowiedź jest naprawdę poprawna, a jeśli liczba jest złożona, to odpowiedź jest poprawna, ze zwiększonym prawdopodobieństwem co najmniej 1− (1 - ½) k = 1−2 −k .
W przypadku bezstronnych algorytmów decyzyjnych Monte Carlo prawdopodobieństwo błędu można również zmniejszyć, wykonując algorytm k razy i zwracając odpowiedź, która pasuje do większości.
BPP ( ograniczony błędów probabilistyczny czasie wielomianowym ) klasa złożoności opisuje problemy decyzyjne , które mogą być rozwiązane przez bezstronny algorytmu Monte-Carlo w czasie wielomianowym, z ograniczonym prawdopodobieństwem błędu.
Klasa złożoności RP (dla randomizowanego czasu wielomianu ) opisuje problemy, które można rozwiązać z ograniczonym prawdopodobieństwem błędu przez stronniczy algorytm Monte-Carlo: jeśli poprawna odpowiedź jest fałszywa , algorytm tak mówi, ale w przypadkach może odpowiedzieć fałszywie gdzie prawidłowa odpowiedź jest prawdziwa .
Z drugiej strony, klasa złożoności ZPP (dla zerowego błędu probabilistycznego czasu wielomianowego ) opisuje problemy rozwiązywane w czasie wielomianowym przez algorytm Las Vegas. Mamy ZPP ⊆ RP ⊆ BPP, ale nie wiemy, czy te klasy złożoności są wzajemnie różne. Innymi słowy, algorytmy Monte-Carlo mogą mieć lepszą wydajność niż algorytmy Las Vegas, ale nie zostało to wykazane.
Inną klasą złożoności jest PP (dla wielomianów probabilistycznych ); opisuje problemy decyzyjne rozwiązywane w czasie wielomianowym przez algorytm Monte-Carlo, który daje dokładniejszy wynik niż zwykły rzut monetą, ale którego prawdopodobieństwa błędu nie można znacznie zmniejszyć poniżej ½.
Godne uwagi algorytmy Monte-Carlo obejmują test pierwszości Solovaya-Strassena i test pierwszości Millera-Rabina , a także kilka szybkich odmian algorytmu Schreiera-Simsa w obliczeniowej teorii grup .
Rozwiązanie problemu komiwojażera jest trudne, ze względu na złożoność problemu, zastosowanie probabilistycznych metod optymalizacji może być skuteczne w uzyskaniu przybliżenia najlepszego rozwiązania w krótszym czasie niż w przypadku metod deterministycznych.
Minimalne cięcieAlgorytm Karger jest algorytm Monte Carlo do problemu minimalnego cięcia .