در محاسبات، الگوریتم لاس وگاس، یک الگوریتم تصادفی است که همیشه پاسخ صحیح را میدهد. که یعنی همیشه منجر به تولید پاسخ صحیح است یا ما را از خطا آگاه میکند. به عبارت دیگر, الگوریتم لاس وگاس, با صحت نتایج، بازی یا قمار نمیکند، بلکه با منابعی که برای محاسبه استفاده میشوند بازی (قمار) میکند یک مثال ساده مرتبسازی سریع تصادفی است. که در آن محور یا عضو مؤثر در مرتبسازی به صورت تصادفی انتخاب شده اما نتیجه این است که همیشه پاسخ مرتب شده داریم. الگوریتم لاس وگاس یک محدودیت دارد و آن این است که باید همیشه زمان اجرا متناهی باشد. [1]
الگوریتم لاس وگاس توسط László Babai در سال 1979 در زمینه مشکل گراف ایزومورفیسم (همریخت) به عنوان یک دوگانه به مونت کارلو و الگوریتم معرفی شد.[2][3][4] الگوریتم لاس وگاس را می توان در موقعیت های که در آنها تعداد راه حل ها ممکن است نسبتاً کم باشد و در آن تایید صحت یک کاندیدا راه حل نسبتاً آسانی است استفاده کرد در حالی که در واقع راهحل محاسبات واقعاً پیچیده است.
نام الگوریتم اشاره به نام شهر لاس وگاس نوادا است که به خوبی در ایالات متحده به عنوان یک نماد از قمار شناخته شده است.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.