الگوریتم لاس وگاس

در محاسبات، الگوریتم لاس وگاس، یک الگوریتم تصادفی است که همیشه پاسخ صحیح را می‌دهد. که یعنی همیشه منجر به تولید پاسخ صحیح است یا ما را از خطا آگاه می‌کند. به عبارت دیگر, الگوریتم لاس وگاس, با صحت نتایج، بازی یا قمار نمی‌کند، بلکه با منابعی که برای محاسبه استفاده می‌شوند بازی (قمار) می‌کند یک مثال ساده مرتب‌سازی سریع تصادفی است. که در آن محور یا عضو مؤثر در مرتب‌سازی به صورت تصادفی انتخاب شده اما نتیجه این است که همیشه پاسخ مرتب شده داریم. الگوریتم لاس وگاس یک محدودیت دارد و آن این است که باید همیشه زمان اجرا متناهی باشد. 

الگوریتم لاس وگاس توسط  László Babai در سال 1979 در زمینه مشکل گراف ایزومورفیسم (هم‌ریخت) به عنوان یک دوگانه به مونت کارلو و الگوریتم معرفی شد.László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.Leonid Levin, The Tale of One-way Functions, Problems of Information Transmission, vol. 39 (2003), 92-103.Dan Grundy, Concepts and Calculation in Cryptography , University of Kent, Ph.D. thesis, 2008 الگوریتم لاس وگاس  را می توان در موقعیت های که در آن‌ها تعداد راه حل ها ممکن است نسبتاً کم باشد و در آن تایید صحت یک کاندیدا راه حل نسبتاً آسانی است استفاده کرد در حالی که در واقع راه‌حل محاسبات واقعاً پیچیده است.

نام الگوریتم اشاره به نام شهر لاس وگاس نوادا است که به خوبی در ایالات متحده به عنوان یک نماد از قمار شناخته شده است.

 پانویس 

رده:الگوریتم‌های تصادفی