Монте-Карло алгоритмдері: қателік мүмкіндігі бар кездейсоқ алгоритмдер
Monte Carlo algorithm
Монте-Карло алгоритмі: кездейсоқ алгоритмдер, қателік мүмкіндігі бар, бірақ аздап. Кarger–Stein және минимумдық кері байланыс жинағы алгоритмдері мысал. 🎲💻
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Кездейсоқ алгоритмнің түрі
Type of randomized algorithm
Есептеу техникасында Монте-Карло алгоритмі – белгілі бір (әдетте кішкентай) ықтималдықпен нәтижесі қате болуы мүмкін кездейсоқ алгоритм. Мұндай алгоритмдердің екі мысалы – Каргер-Штейн алгоритмі және ең кішкентай кері байланыс доғалар жиынына арналған Монте-Карло алгоритмі. Атауы Монако княздығындағы Монте-Карло казиносына сілтеме жасайды, ол әлем бойынша құмар ойындарының символы ретінде кеңінен танымал. "Монте-Карло" терминін алғаш рет 1947 жылы Николас Метрополис енгізген. Лас-Вегас алгоритмдері Монте-Карло алгоритмдеріне қарама-қарсы және ешқашан қате жауап бермейді. Дегенмен, олар өз жұмысының бір бөлігі ретінде кездейсоқ таңдаулар жасай алады. Соның салдарынан, уақыт бірдей кіріс деректерімен де әртүрлі болуы мүмкін. Егер Монте-Карло алгоритмінің нәтижесінің дұрыстығын тексеруге процедура болса және дұрыс жауап беру ықтималдығы нөлден жоғары болса, онда алгоритмді қайта-қайта орындап, нәтижелерді тексеру арқылы, міндетті түрде дұрыс жауап алынады. Бұл процестің Лас-Вегас алгоритміне жататыны, тоқтау ықтималдығының біреуге тең болуы анықтаманы қанағаттандырады-қанағаттандырмайды дегенге байланысты.
In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are the Karger–Stein algorithm and the Monte Carlo algorithm for minimum feedback arc set. The name refers to the Monte Carlo casino in the Principality of Monaco, which is well known around the world as an icon of gambling. The term "Monte Carlo" was first introduced in 1947 by Nicholas Metropolis. Las Vegas algorithms are a dual of Monte Carlo algorithms and never return an incorrect answer. However, they may make random choices as part of their work. As a result, the time taken might vary between runs, even with the same input. If there is a procedure for verifying whether the answer given by a Monte Carlo algorithm is correct, and the probability of a correct answer is bounded above zero, then with probability one, running the algorithm repeatedly while testing the answers will eventually give a correct answer. Whether this process is a Las Vegas algorithm depends on whether halting with probability one is considered to satisfy the definition.
Бір жақты және екі жақты қате
Детерминистік алгоритм берген жауап әрқашан дұрыс болады деп күтіледі, бірақ Монте-Карло алгоритмдері үшін бұл осылай болмайды. Шешім қабылдау мәселелері үшін бұл алгоритмдер жалған қисайлы немесе нақты қисайлы деп жіктеледі. Жалған қисайлы Монте-Карло алгоритмі жалған жауап бергенде әрқашан дұрыс болады; нақты қисайлы алгоритм дұрыс жауап бергенде әрқашан дұрыс болады. Бұл бір жақты қателерге ие алгоритмдерді сипаттайды, ал басқалары қисайлылықсыз болуы мүмкін; олар екі жақты қателерге ие деп айтылады. Олар ұсынатын жауап (нағыз немесе жалған) белгілі бір шектеулі ықтималдықпен дұрыс немесе бұрыс болуы мүмкін. Мысалы, Соловай-Страссендік жай сан тесті берілген санның жай сан екенін анықтау үшін қолданылады. Ол жай сандар үшін әрқашан дұрыс жауап береді; құрама сандар үшін ол кем дегенде 1/2 ықтималдығымен жалған жауап береді және 1/2 ықтималдығынан кем ықтималдығымен дұрыс жауап береді. Осылайша, алгоритмнің жалған жауаптарының дұрыс екеніне сенуге болады, ал дұрыс жауаптар белгісіз болып қалады; мұндай алгоритм 1/2 дұрыс, жалған қисайлы алгоритм деп аталады.
While the answer returned by a deterministic algorithm is always expected to be correct, this is not the case for Monte Carlo algorithms. For decision problems, these algorithms are generally classified as either false biased or true biased. A false biased Monte Carlo algorithm is always correct when it returns false; a true biased algorithm is always correct when it returns true. While this describes algorithms with one sided errors, others might have no bias; these are said to have two sided errors. The answer they provide (either true or false) will be incorrect, or correct, with some bounded probability. For instance, the Solovay–Strassen primality test is used to determine whether a given number is a prime number. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least 1/2 and true with probability less than 1/2. Thus, false answers from the algorithm are certain to be correct, whereas the true answers remain uncertain; this is said to be a 1/2 correct false biased algorithm.
Көшейткіш
Бір жақты қатесі бар Монте-Карло алгоритмі үшін, алгоритмді k рет іске қосу арқылы сәтсіздік ықтималдығын азайтуға (және сәттілік ықтималдығын арттыруға) болады. Соловэй-Страссен алгоритмін қарастырайық, ол 1/2 дәл, жалған және бұрмаланған. Бұл алгоритмді бірнеше рет іске қосып, k итерация ішінде жалған жауап алынса, жалған жауап береді, әйтпесе дұрыс жауап береді. Осылайша, егер сан жай болса, жауап әрқашан дұрыс болады, ал егер сан жаратылған болса, жауап кем дегенде 1−(1−1/2)k = 1−2−k ықтималдығымен дұрыс болады. Екі жақты қатесі бар Монте-Карло шешім алгоритмдері үшін, алгоритмді k рет іске қосып, жауаптардың көпшілік функциясын қайтару арқылы сәтсіздік ықтималдығын тағы да азайтуға болады.
For a Monte Carlo algorithm with one sided errors, the failure probability can be reduced (and the success probability amplified) by running the algorithm k times. Consider again the Solovay–Strassen algorithm which is 1/2 correct false biased. One may run this algorithm multiple times returning a false answer if it reaches a false response within k iterations, and otherwise returning true. Thus, if the number is prime then the answer is always correct, and if the number is composite then the answer is correct with probability at least 1−(1−1/2)k = 1−2−k. For Monte Carlo decision algorithms with two sided error, the failure probability may again be reduced by running the algorithm k times and returning the majority function of the answers.
Күрделілік сыныптары
Күрделілік класы BPP екі жақты қателіктердің шектелген ықтималдығымен полиномиалдық уақытта жұмыс істейтін Монте-Карло алгоритмдерімен шешілетін шешімдерді сипаттайды, ал күрделілік класы RP Монте-Карло алгоритмімен шешілетін проблемаларды сипаттайды, онда бір жақты қателіктердің ықтималдығы шектелген: егер дұрыс жауап жалған болса, алгоритм әрқашан осылай деп жауап береді, бірақ дұрыс жауап шын болған жағдайларда кейде қателікпен жалған деп жауап беруі мүмкін. Ал күрделілік класы ZPP күтілетін уақытта Лас-Вегас алгоритмдерімен шешілетін проблемаларды сипаттайды. ZPP ⊆ RP ⊆ BPP, бірақ осы күрделілік сыныптарының бірінен-бірі ерекшеленетіні белгісіз; яғни Монте-Карло алгоритмдері Лас-Вегас алгоритмдерінен артық есептеу күшіне ие болуы мүмкін, бірақ бұл әлі дәлелденбеді. Осылайша, "SO-ның кемшілігі жойылды және шешімге сенімділік қалыптастырылды".
The complexity class BPP describes decision problems that can be solved by polynomial time Monte Carlo algorithms with a bounded probability of two sided errors, and the complexity class RP describes problems that can be solved by a Monte Carlo algorithm with a bounded probability of one sided error: if the correct answer is false, the algorithm always says so, but it may answer false incorrectly for some instances where the correct answer is true. In contrast, the complexity class ZPP describes problems solvable by polynomial expected time Las Vegas algorithms. ZPP ⊆ RP ⊆ BPP, but it is not known whether any of these complexity classes is distinct from each other; that is, Monte Carlo algorithms may have more computational power than Las Vegas algorithms, but this has not been proven. In this way, "drawback of SO has been mitigated, and a confidence in a solution has been established."