אלגוריתם לאס וגאס
במדעי המחשב, אלגוריתם לאס וגאס הוא אלגוריתם אקראי המחזיר תמיד תוצאה נכונה; כלומר, הוא תמיד נותן את התוצאה הנכונה או שהוא מודיע על כישלון. במילים אחרות, אלגוריתם לאס וגאס אינו מהמר על נכונות התוצאה; הוא מהמר רק על המשאבים המשמשים לצורך החישוב. דוגמה פשוטה היא מיון מהיר אקראי, כאשר איבר הציר נבחר באופן אקראי, אבל התוצאה תמיד ממוינת. ההגדרה הרגילה של אלגוריתם לאס וגאס כוללת את ההגבלה שתוחלת זמן הריצה תמיד תהיה סופית, כאשר התוחלת מתבצעת מעל מרחב המידע האקראי, או האנטרופיה, בהם האלגוריתם משתמש. הגדרה חלופית דורשת שאלגוריתם לאס וגאס תמיד יסתיים (יהיה יעיל), אך הוא עשוי לתת כפלט סמל שאינו חלק ממרחב הפתרונות כדי לדווח על כשל במציאת פתרון.[1]
אלגוריתמים מסוג לאס וגאס הוצגו על ידי לסלו בבאי ב-1979, בהקשר של בעיית איזומורפיות גרפים, כזוג לאלגוריתם מונטה קרלו.[2] ניתן להשתמש באלגוריתמים מסוג לאס וגאס במצבים בהם מספר הפתרונות האפשריים מוגבל, וכאשר אימות נכונותו של הפתרון המועמד הוא קל יחסית, בעוד חישוב הפתרון הוא מורכב.
השם מתייחס לעיר לאס וגאס, אשר ידועה כסמל להימורים.
מחלקת סיבוכיות
מחלקת הסיבוכיות של בעיות הכרעה להן קיים אלגוריתם לאס וגאס עם תוחלת זמן ריצה פולינומית, היא ZPP.
מתקיים כי
דבר הקשור באופן הדוק עם הדרך שאלגוריתמים מסוג לאס וגאס נבנים לעיתים. כלומר המחלקה RP מורכבת מכל בעיות ההכרעה להן קיים אלגוריתם זמן-פולינומי אקראי המחזיר תשובה נכונה כאשר התשובה הנכונה היא "לא", אבל רשאי לטעות בהסתברות מסוימת הרחוקה מ-1, כאשר התשובה היא "כן". כאשר קיים אלגוריתם כזה עבור בעיה והמשלימה שלה (התשובות "כן" ו "לא" מוחלפות), ניתן להריץ בו זמנית את שני האלגוריתמים ובאופן חוזר ונשנה: להריץ כל אחד מספר קבוע של צעדים, בתורנות, עד שאחד מהם מחזיר תשובה ודאית. זו הדרך הרגילה לבנות אלגוריתם לאס וגאס הפועל בתוחלת זמן פולינומית. שימו לב כי באופן כללי אין חסם עליון על זמן הריצה של המקרה הגרוע של אלגוריתם לאס-וגאס.
הקשר לאלגוריתם מונטה קרלו
ניתן להשוות אלגוריתם לאס וגאס לעומת אלגוריתם מונטה קרלו, שבהם המשאבים בשימוש חסומים, אבל לא מובטח שהתשובה נכונה. על ידי יישום של אי-שוויון מרקוב, ניתן להמיר אלגוריתם לאס וגאס לאלגוריתם מונטה קרלו באמצעות סיום מוקדם.
ראו גם
קישורים חיצוניים
- המדריך לאלגוריתמים ותורת החישוביות, CRC Press LLC, 1999.
- אלגוריתם "לאס וגאס" ב"מילון של אלגוריתמים ומבני נתונים [באינטרנט], פאול א. בלק, ארצות הברית, המכון הלאומי לתקנים וטכנולוגיה. זמין מ: 17 יולי 2006. (גישה מאי 09, 2009)[1]
הערות שוליים
- ^ Steven D. Galbraith (2012). Mathematics of Public Key Cryptography. Cambridge University Press. p. 16. ISBN 978-1-107-01392-6.
- ^ László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.
22746038אלגוריתם לאס וגאס