خوارزمية لاس فيغاس

في مجال الحوسبة ، تُعرف خوارزمية لاس فيغاس بأنها خوارزمية عشوائية تُعطي نتائج صحيحة دائمًا ؛ أي أنها تُنتج دائمًا النتيجة الصحيحة أو تُشير إلى الفشل. مع ذلك، يختلف زمن تشغيل خوارزمية لاس فيغاس باختلاف المُدخلات. يتضمن التعريف الشائع لخوارزمية لاس فيغاس شرط أن يكون زمن التشغيل المتوقع محدودًا، حيث يُحسب التوقع على فضاء المعلومات العشوائية، أو الإنتروبيا، المُستخدمة في الخوارزمية. ويشترط تعريف بديل أن تنتهي خوارزمية لاس فيغاس دائمًا (تكون فعّالة )، ولكنها قد تُخرج رمزًا ليس جزءًا من فضاء الحلول للإشارة إلى فشلها في إيجاد حل. ^{[ 1 ]} طبيعة خوارزميات لاس فيغاس تجعلها مناسبة في الحالات التي يكون فيها عدد الحلول الممكنة محدودًا، وحيث يكون التحقق من صحة حل مُرشح سهلًا نسبيًا بينما يكون إيجاد حل أمرًا معقدًا.

تستخدم أساليب البحث المنهجية للمسائل الصعبة حسابيًا، مثل بعض متغيرات خوارزمية ديفيس-بوتنام لإرضاء القضايا ( SAT)، قرارات غير حتمية، وبالتالي يمكن اعتبارها أيضًا خوارزميات لاس فيغاس. ^{[ 2 ]}

طُرحت خوارزميات لاس فيغاس على يد لازلو باباي عام 1979، في سياق مسألة تماثل الرسوم البيانية ، كبديل لخوارزميات مونت كارلو . ^{[ 3 ]} وقدّم باباي ^{[ 4 ]} مصطلح "خوارزمية لاس فيغاس" مصحوبًا بمثال يتضمن رمي العملة: تعتمد الخوارزمية على سلسلة من رميات العملة المستقلة، وهناك احتمال ضئيل للفشل (عدم الحصول على نتيجة). ومع ذلك، وعلى عكس خوارزميات مونت كارلو، تضمن خوارزمية لاس فيغاس صحة أي نتيجة يتم الإبلاغ عنها.

دالة ` getRandomInteger ( int n )` : ` Random rand = new Random ( ); return rand.nextInt ( n ) ; }`// خوارزمية لاس فيغاس، بافتراض أن a عبارة عن مصفوفة طولها n. // الهدف: إرجاع فهرس صحيح k بحيث يكون a[k] == 1. int lasVegasAlgorithm ( int [] a ) { int n = a . length ; while ( true ) { int k = getRandomInteger ( n ); if ( a [ k ] == 1 ) { return k ; } } }

كما ذُكر سابقًا، تُعيد خوارزميات لاس فيغاس دائمًا نتائج صحيحة. يُوضح الكود أعلاه هذه الخاصية. الهدف هو إيجاد فهرس في المصفوفة aيحتوي على القيمة 1. kيتم إنشاء متغير عشوائيًا؛ بعد kإنشائه، kيُستخدم لفهرسة المصفوفة a. إذا كان هذا الفهرس يحتوي على القيمة 1، يتم إرجاع القيمة 1 k؛ وإلا، تُكرر الخوارزمية هذه العملية حتى تجد القيمة 1. على الرغم من أن خوارزمية لاس فيغاس هذه تضمن إيجاد الإجابة الصحيحة، إلا أنها لا تملك وقت تشغيل ثابتًا؛ نظرًا للعشوائية، قد يمر وقت طويل جدًا قبل أن تنتهي الخوارزمية.

يُقدّم هذا القسم الشروط التي تُميّز كون الخوارزمية من نوع لاس فيغاس.

تعتبر الخوارزمية A خوارزمية لاس فيغاس لفئة المشكلة X، إذا ^{[ 5 ]}

1. عندما تُرجع الدالة حلاً s لمسألة معينة x∈X، فإن s مضمون أن يكون حلاً صحيحاً للمسألة x.
2. في كل حالة معينة x، يكون زمن تشغيل A متغيرًا عشوائيًا RT _A,x

توجد ثلاثة مفاهيم للاكتمال في خوارزميات لاس فيغاس:

• يمكن ضمان أن خوارزميات لاس فيغاس الكاملة قادرة على حل كل مشكلة قابلة للحل في غضون وقت التشغيل t max، حيث t max هو ثابت يعتمد على الحالة.

لنفترض أن P(RT _A,x ≤ t) تُمثل احتمال أن تجد A حلاً لمسألة قابلة للحل x في زمن t، فإن A تكون كاملة تمامًا إذا كان لكل x يوجد

بعض القيم القصوى لـ t بحيث يكون P(RT _A,x ≤ t _max ) = 1.

• تُحلّ خوارزميات لاس فيغاس شبه الكاملة كل مشكلة باحتمالية تتقارب إلى 1 مع اقتراب زمن التشغيل من اللانهاية. وبالتالي، تكون A شبه كاملة إذا كان لكل حالة x، lim _t→∞ P(RT _A,x ≤ t) = 1.
• خوارزميات لاس فيغاس غير المكتملة أساساً هي خوارزميات لاس فيغاس التي لا تكون مكتملة تقريباً.

إن الاكتمال التقريبي ذو أهمية نظرية في المقام الأول، حيث أن الحدود الزمنية لإيجاد الحلول عادة ما تكون كبيرة جدًا بحيث لا يمكن استخدامها عمليًا.

فئة تعقيد مسائل القرار التي تحتوي على خوارزميات لاس فيغاس ذات وقت تشغيل متعدد الحدود المتوقع هي ZPP .

اتضح أن

${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$

يرتبط هذا ارتباطًا وثيقًا بطريقة بناء خوارزميات لاس فيغاس أحيانًا. وتحديدًا، تتألف فئة RP من جميع مسائل القرار التي توجد لها خوارزمية عشوائية متعددة الحدود تُجيب دائمًا بشكل صحيح عندما تكون الإجابة الصحيحة "لا"، ولكن يُسمح لها بالخطأ باحتمالية معينة بعيدة عن الواحد عندما تكون الإجابة "نعم". عندما توجد مثل هذه الخوارزمية لكل من المسألة ومكملتها (مع تبديل الإجابتين "نعم" و"لا")، يمكن تشغيل الخوارزميتين في وقت واحد وبشكل متكرر: تشغيل كل منهما لعدد ثابت من الخطوات، بالتناوب، حتى تُعيد إحداهما إجابة نهائية. هذه هي الطريقة القياسية لبناء خوارزمية لاس فيغاس التي تعمل في وقت متعدد الحدود متوقع. تجدر الإشارة إلى أنه بشكل عام، لا يوجد حد أعلى لأسوأ حالة لوقت تشغيل خوارزمية لاس فيغاس.

لتحقيق الأداء الأمثل لخوارزمية لاس فيغاس، يجب تقليل وقت التشغيل المتوقع. ويمكن تحقيق ذلك عن طريق:

1. تُنفَّذ خوارزمية لاس فيغاس A ( x ) بشكل متكرر لعدد من الخطوات مقداره t ≤ _1. إذا توقفت A ( x ) أثناء التنفيذ، فهذا يعني أن العملية قد انتهت ؛ وإلا، تُكرَّر العملية من البداية لعدد آخر من الخطوات مقداره t ≤ 2 _، وهكذا.
2. تصميم استراتيجية مثلى من بين جميع الاستراتيجيات لـ A ( x )، بالنظر إلى المعلومات الكاملة حول توزيع T _A ( x ).

قد يكون وجود الاستراتيجية المثلى ملاحظة نظرية مثيرة للاهتمام. مع ذلك، فهو غير عملي في الواقع العملي لصعوبة الحصول على معلومات حول توزيع TA ₍ x ). علاوة على ذلك، لا جدوى من تكرار التجربة للحصول على معلومات حول التوزيع ، إذ غالبًا ما نحتاج إلى الإجابة مرة واحدة فقط لأي قيمة لـ x . ^{[ 8 ]}

يمكن مقارنة خوارزميات لاس فيغاس بخوارزميات مونت كارلو ، حيث تكون الموارد المستخدمة محدودة، ولكن قد تكون الإجابة خاطئة باحتمالية معينة (عادةً ما تكون صغيرة) . يمكن تحويل خوارزمية لاس فيغاس إلى خوارزمية مونت كارلو بتشغيلها لفترة زمنية محددة، ثم توليد إجابة عشوائية عند فشلها في التوقف. بتطبيق متباينة ماركوف ، يمكننا تحديد الحد الأقصى لاحتمالية تجاوز خوارزمية لاس فيغاس لهذا الحد الثابت.

إليكم جدول يقارن بين خوارزميات لاس فيغاس ومونت كارلو: ^{[ 9 ]}

إذا توفرت طريقة حتمية لاختبار صحة الخوارزمية، فمن الممكن تحويل خوارزمية مونت كارلو إلى خوارزمية لاس فيغاس. مع ذلك، يصعب تحويل خوارزمية مونت كارلو إلى خوارزمية لاس فيغاس دون وجود طريقة لاختبارها. في المقابل، يُعدّ تحويل خوارزمية لاس فيغاس إلى خوارزمية مونت كارلو أمرًا يسيرًا. يُمكن القيام بذلك بتشغيل خوارزمية لاس فيغاس لفترة زمنية محددة تُحددها قيمة معامل الثقة. إذا توصلت الخوارزمية إلى الحل خلال هذه الفترة، تُعتبر ناجحة، وإذا لم تتوصل إليه، يُمكن ببساطة عرض رسالة "عذرًا".

هذا مثال على خوارزميات لاس فيغاس ومونت كارلو للمقارنة: ^{[ 10 ]}

لنفترض وجود مصفوفة طولها عدد زوجي n . نصف عناصر المصفوفة عبارة عن أصفار، والنصف الآخر عبارة عن آحاد. الهدف هنا هو إيجاد فهرس يحتوي على الرقم 1.

// خوارزمية لاس فيجاس int lasVegasAlgorithm ( int [] a ) { int n = a . طول ؛ بينما ( صحيح ) { int k = getRandomInteger ( n )؛ إذا ( أ [ ك ] == 1 ) { إرجاع ك ؛ } } }// خوارزمية مونت كارلو int monteCarloAlgorithm ( int [] a ) { int n = a . length ; for ( int i = 0 ; i < 300 ; ++ i ) { int k = getRandomInteger ( n ); if ( a [ k ] == 1 ) { return k ; } } return - 1 ; // يشير إلى الفشل }

بما أن خوارزمية لاس فيغاس لا تتوقف حتى تجد الرقم 1 في المصفوفة، فإنها لا تُخاطر بصحة الحل بل بوقت التنفيذ. من ناحية أخرى، تُنفَّذ خوارزمية مونت كارلو 300 مرة، مما يعني أنه من المستحيل معرفة ما إذا كانت ستجد الرقم 1 في المصفوفة خلال 300 دورة تكرارية حتى يتم تنفيذ الكود فعليًا. قد تجد الحل أو لا. لذلك، على عكس لاس فيغاس، لا تُخاطر خوارزمية مونت كارلو بوقت التنفيذ بل بصحة الحل.

• خوارزمية مونت كارلو
• خوارزمية مدينة أتلانتيك
• العشوائية