Кіріспе
Кездейсоқ алгоритмнің түрі
Информатикада Лас-Вегас алгоритмі – әрқашан дұрыс нәтиже беретін кездейсоқ алгоритм; яғни, ол әрқашан дұрыс жауапты шығарады немесе оның сәтсіз аяқталғанын хабарлайды. Дегенмен, Лас-Вегас алгоритмінің жұмыс істеу уақыты кіріс деректерге байланысты өзгереді. Лас-Вегас алгоритмінің қалыпты анықтамасы күтілетін жұмыс істеу уақытының шекті болуын қамтиды, мұнда күту алгоритмде қолданылатын кездейсоқ ақпарат немесе энтропия кеңістігінде жүзеге асырылады. Балама анықтама бойынша Лас-Вегас алгоритмі әрқашан аяқталады (тиімді), бірақ шешім табудағы сәтсіздікті көрсету үшін шешім кеңістігіне жатпайтын символдарды шығара алады. Лас-Вегас алгоритмдерінің ерекшелігі оларды мүмкін болатын шешімдер саны шектеулі және шешім табу қиын болғанда, ал кандидат шешімнің дұрыстығын тексеру салыстырмалы түрде оңай болатын жағдайларда пайдалануға ыңғайлы етеді. Есептеу бойынша қиын мәселелерді шешу үшін жүйелі іздеу әдістері, мысалы, логикалық қанағаттандыру (SAT) үшін Дэвис-Путнам алгоритмінің кейбір түрлері де детерминистік емес шешімдерді қолданады, сондықтан оларды да Лас-Вегас алгоритмдері деп санауға болады.
In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex. Systematic search methods for computationally hard problems, such as some variants of the Davis–Putnam algorithm for propositional satisfiability (SAT), also utilize non deterministic decisions, and can thus also be considered Las Vegas algorithms.
Тарих
Лас-Вегас алгоритмдері 1979 жылы Ласло Бабай график изоморфизмі мәселесі аясында Монте-Карло алгоритмдеріне қарама-қарсы ретінде енгізілді. Бабай "Лас-Вегас алгоритмі" терминін тиындарды лақтырумен байланысты мысалмен бірге ұсынды: алгоритм тәуелсіз тиындар тізбегіне байланысты, және нәтиже шығармау мүмкіндігі бар (сәтсіздік). Бірақ, Монте-Карло алгоритмдерінен өзгеше, Лас-Вегас алгоритмі есептелген кез келген нәтиженің дұрыстығына кепілдік бере алады.
Қолдану сценарийлері
Лас-Вегас алгоритмдері мәселенің ерекшеліктеріне байланысты бағалау үшін әртүрлі критерийлерді қолданады. Бұл критерийлер Лас-Вегас алгоритмдерінің белгілі бір уақыт күрделілігі болмағандықтан, әртүрлі уақыт шектерімен үш санатқа бөлінеді. Мүмкін қолданылу сценарийлері: 1-тип: уақыт шектеуі жоқ, яғни алгоритм шешім табылғанша жұмыс істей береді. 2-тип: нәтижені табу үшін tmax уақыт шегі бар. 3-тип: Шешімнің пайдалылығы шешімді табуға кеткен уақытпен анықталады. (1- және 2-типтер 3-типтің ерекше жағдайлары болып табылады.) 1-типте, уақыт шектеуі болмағандықтан, орташа жұмыс уақыты алгоритмнің жұмыс істеу мінез-құлқын көрсете алады. Бұл 2-типке қатысты емес. Мұнда P(RT ≤ tmax), яғни белгілі бір уақыт ішінде шешім табу ықтималдығы, оның жұмыс уақытының мінез-құлқын сипаттайды. 3-типте оның жұмыс уақытын тек rtd: R → [0,1] жұмыс уақытын бөлу функциясы, яғни rtd(t) = P(RT ≤ t) немесе оның жуықтауы арқылы көрсетуге болады. Жұмыс уақытын бөлу (RTD) – Лас-Вегас алгоритмінің жұмыс істеу мінез-құлқын сипаттаудың ерекше тәсілі. Осы деректердің негізінде, біз кез келген уақыт шегі t үшін орташа жұмыс уақыты, стандартты ауытқу, медиана, пайыздық көрсеткіштер немесе табысқа жету ықтималдығы P(RT ≤ t) сияқты басқа да критерийлерді оңай анықтай аламыз.
Type 1: There are no time limits, which means the algorithm runs until it finds the solution. Type 2: There is a time limit tmax for finding the outcome. Type 3: The utility of a solution is determined by the time required to find the solution. (Type 1 and Type 2 are special cases of Type 3.) For Type 1 where there is no time limit, the average run time can represent the run time behavior. This is not the same case for Type 2. Here, P(RT ≤ tmax), which is the probability of finding a solution within time, describes its run time behavior. In case of Type 3, its run time behavior can only be represented by the run time distribution function rtd: R → [0,1] defined as rtd(t) = P(RT ≤ t) or its approximation. The run time distribution (RTD) is the distinctive way to describe the run time behavior of a Las Vegas algorithm. With this data, we can easily get other criteria such as the mean run time, standard deviation, median, percentiles, or success probabilities P(RT ≤ t) for arbitrary time limits t.
Салыстырмалылық
Лас-Вегас алгоритмдері іздеу мәселелерінде жиі кездеседі. Мысалы, онлайн режимінде ақпарат іздеген адам қажетті мәліметтерді табу үшін байланысты веб-сайттарды қарастыруы мүмкін. Осының салдарынан, уақыттың күрделілігі ең жақсы жағдайда дереу табылуынан бастап, ең нашар жағдайда көп уақыт жұмсауға дейін өзгереді. Дұрыс веб-сайт табылып қойғаннан кейін, қате болу мүмкіндігі жоқ.
Сегіз қыздың проблемасының кездейсоқ алгоритмі
Сегіз патшайым мәселесі әдетте кері іздеу алгоритмімен шешіледі. Дегенмен, Лас-Вегас алгоритмін қолдануға болады; шындығында, ол кері іздеуден тиімдірек. Шахмат тақтасына 8 патшайымды орналастырыңыз, олар бір-біріне шабуыл жасамасын. Патшайым бір қатарда, бағанда және диагональдардағы басқа патшайымдарға шабуыл жасайтынын есіңізде сақтаңыз. 0 ≤ k ≤ 8 аралығындағы k қатарда патшайымдар сәтті орналасқан деп есептейік. Егер k = 8 болса, онда сәттілікпен тоқтаңыз. Әйтпесе, k + 1 қатарды толтыруды жалғастырыңыз. Осы қатардағы, қолданыстағы патшайымдар шабуылдай алмайтын барлық қыштарды есептеңіз. Егер мұндай қыштар болмаса, сәтсіздікке ұшыраңыз. Әйтпесе, кездейсоқ біреуін таңдап, k-ны арттырып, қайталаңыз. Алгоритм патшайымды орналастыру мүмкін болмаса ғана сәтсіз аяқталады екенін есте сақтаңыз. Бірақ бұл процесті қайталауға болады және әр ретте әртүрлі орналасу нұсқалары туындайды.
Лас-Вегас алгоритмі
Лас-Вегас алгоритмін оңтайландыру үшін күтілетін орындалу уақыты ең төменге түсірілуі керек. Мұны мынадай жолмен істеуге болады: Лас-Вегас алгоритмі A(x) t1 қадамға дейін бірнеше рет орындалады. Егер A(x) орындалу барысында тоқтаса, онда A(x) жұмысы аяқталған болып саналады; әйтпесе, процесті тағы бір t2 қадамға дейін басынан қайталаңыз, және т.с.с. A(x) үшін барлық стратегиялардың арасындағы ең оңтайлы стратегияны ТА(x) үлестірімі туралы толық ақпарат негізінде жобалау. Оптималды стратегияның болуы – қызықты теориялық тұжырым болуы мүмкін. Дегенмен, бұл нақты өмірде тиімді емес, себебі ТА(x) үлестірімі туралы ақпаратты табу қиын. Сонымен қатар, үлестірім туралы ақпарат алу үшін экспериментті қайта-қайта жүргізудің қажеті жоқ, өйткені көбінесе кез келген x үшін жауап бір рет ғана керек болады.
The Las Vegas algorithm A(x) runs repeatedly for some number t1 steps. If A(x) stops during the run time then A(x) is done; otherwise, repeat the process from the beginning for another t2 steps, and so on. Designing a strategy that is optimal among all strategies for A(x), given the full information about the distribution of TA(x). The existence of the optimal strategy might be a fascinating theoretical observation. However, it is not practical in real life because it is not easy to find the information of distribution of TA(x). Furthermore, there is no point of running the experiment repeatedly to obtain the information about the distribution since most of the time, the answer is needed only once for any x.