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

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

الگوریتم لاس وگاس توسط  László Babai در سال 1979 در زمینه مشکل گراف ایزومورفیسم (هم‌ریخت) به عنوان یک دوگانه به مونت کارلو و الگوریتم معرفی شد. الگوریتم لاس وگاس  را می توان در موقعیت های که در آن‌ها تعداد راه حل ها ممکن است نسبتاً کم باشد و در آن تایید صحت یک کاندیدا راه حل نسبتاً آسانی است استفاده کرد در حالی که در واقع راه‌حل محاسبات واقعاً پیچیده است.

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

پانویس 

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