خوارزمية SMAWK

الموسوعة الحرة

خوارزمية SMAWK هي خوارزمية لإيجاد القيمة الدنيا في كل صف من مصفوفة رتيبة كليًا معرفة ضمنيًا . سُميت نسبةً إلى الأحرف الأولى من أسماء مخترعيها الخمسة، وهم: بيتر شور ، وشلومو موران ، وألوك أغاروال، وروبرت ويلبر، وماريا كلاوي . [ 1 ]

مدخل

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

في خوارزمية SMAWK، تُعرَّف المصفوفة المراد البحث فيها كدالة، وتُعطى هذه الدالة كمدخل للخوارزمية (مع أبعاد المصفوفة). ثم تُقيِّم الخوارزمية الدالة كلما احتاجت إلى معرفة قيمة خلية معينة في المصفوفة. إذا استغرق هذا التقييم زمنًا قدره O ( 1 )، فإن زمن التشغيل وعدد تقييمات الدالة لمصفوفة ذات r صفوف و c أعمدة يكونان O ( c (1  +  log( r / c ))). وهذا أسرع بكثير من زمن O ( rc ) للخوارزمية البسيطة التي تُقيِّم جميع خلايا المصفوفة.

طريقة

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

التطبيقات

تمثلت التطبيقات الرئيسية لهذه الطريقة، التي عُرضت في الورقة البحثية الأصلية لأغاروال وآخرون، في الهندسة الحسابية ، وتحديد أبعد نقطة عن كل نقطة من نقاط المضلع المحدب، وإيجاد المضلعات المحيطة المثلى. وكشفت أبحاث لاحقة عن تطبيقات للخوارزمية نفسها في تقسيم الفقرات إلى أسطر ، [ 2 ] والتنبؤ بالبنية الثانوية للحمض النووي الريبي (RNA) ، [ 3 ] ومحاذاة تسلسل الحمض النووي (DNA) والبروتين ، [ 4 ] [ 5 ] وبناء رموز البادئات ، [ 6 ] وتحديد عتبة الصور ، [ 7 ] وغيرها.

مراجع

  1. ↑ أغاروال، ألوك؛ كلاوي، ماريا م .؛ موران، شلومو ؛ شور، بيتر ؛ ويلبر، روبرت (1987)، "التطبيقات الهندسية لخوارزمية البحث في المصفوفات"، Algorithmica ، 2 ( 1-4 ): 195-208 ، doi : 10.1007/BF01840359 ، MR 0895444 .
  2. ↑ ويلبر، روبرت (1988)، "إعادة النظر في مشكلة المتتالية الفرعية ذات الوزن الأدنى المقعر"، مجلة الخوارزميات ، 9 (3): 418-425 ، doi : 10.1016/0196-6774(88)90032-6 ، MR 0955150 
  3. ↑ لارمور، لورانس ل .؛ شيبر، باروخ (1991)، "البرمجة الديناميكية عبر الإنترنت مع تطبيقات للتنبؤ بالبنية الثانوية للحمض النووي الريبي"، مجلة الخوارزميات ، 12 (3): 490-515 ، doi : 10.1016/0196-6774(91)90016-R ، MR 1114923 .
  4. ↑ روسو، لويس إم إس (2012)، "خصائص مونج لمحاذاة التسلسل"، علوم الحاسوب النظرية ، 423 : 30-49 ، doi : 10.1016/j.tcs.2011.12.068 ، MR 2887979 .
  5. ↑ كروشيمور، ماكسيم؛ لاندو، جاد م.؛ زيف-أوكيلسون، ميشال (2003)، "خوارزمية محاذاة تسلسلية شبه تربيعية لمصفوفات التسجيل غير المقيدة"، مجلة SIAM للحوسبة ، 32 (6): 1654-1673 (إلكترونية)، CiteSeerX 10.1.1.57.8562 ، doi : 10.1137/S0097539702402007 ، MR 2034254  .
  6. ↑ برادفورد، فيل؛ جولين، موردخاي ج.؛ لارمور، لورانس ل .؛ ريتر، فويتش (2002)، "رموز مثالية خالية من البادئات لتكاليف أحرف غير متساوية: البرمجة الديناميكية مع خاصية مونج"، مجلة الخوارزميات ، 42 (2): 277-303 ، CiteSeerX 10.1.1.45.5501 ، doi : 10.1006/jagm.2002.1213 ، MR 1895977  .
  7. ↑ لوسي، م.؛ إيخمان، م.؛ شوستر، ج.م.؛ كاتساجيلوس، أ.ك. (2006)، "نتائج جديدة حول تحديد عتبة الصور الأمثل متعدد المستويات بكفاءة"، المؤتمر الدولي لمعالجة الصور التابع لمعهد مهندسي الكهرباء والإلكترونيات ، الصفحات 773-776 ، CiteSeerX 10.1.1.461.663 ، doi : 10.1109/ICIP.2006.312426 ، ISBN   978-1-4244-0480-3.