خوارزمية روزو-تومبا

خوارزمية روزو-تومبا، أو خوارزمية RT ^{[ 1 ]} ، هي خوارزمية خطية الزمن لإيجاد جميع المتتاليات الفرعية غير المتداخلة والمتجاورة ذات أعلى قيمة في متتالية من الأعداد الحقيقية. ^{[ 2 ]} اقترح خوارزمية روزو-تومبا كلٌ من والتر ل. روزو ومارتن تومبا. ^{[ 3 ]} تُعد هذه الخوارزمية تحسينًا للخوارزميات التربيعية الزمن المعروفة سابقًا. ^{[ 1 ]} كما أن المتتالية الفرعية ذات أعلى قيمة من المجموعة التي تنتجها الخوارزمية هي حل لمسألة المصفوفة الفرعية القصوى .

تُستخدم خوارزمية Ruzzo–Tompa في المعلوماتية الحيوية ، ^{[ 4 ]} واستخراج البيانات من الويب ، ^{[ 5 ]} واسترجاع المعلومات . ^{[ 6 ]}

تُعرَّف مشكلة إيجاد جميع المتتاليات الجزئية القصوى على النحو التالي: بالنظر إلى قائمة من الدرجات العددية الحقيقية${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ابحث عن قائمة المتتاليات الفرعية المتجاورة التي تعطي أعلى مجموع نقاط، حيث تمثل نقاط كل متتالية فرعية${\displaystyle S_{i,j}=\sum _{i\leq k\leq j}x_{k}}$يجب أن تكون التسلسلات الفرعية منفصلة (غير متداخلة) وأن يكون لها درجة موجبة. ^{[ 9 ]}

توجد عدة طرق لحل مشكلة المتتاليات الفرعية ذات أعلى قيمة. إحدى الطرق الطبيعية هي استخدام خوارزميات موجودة ذات زمن خطي لإيجاد المتتالية الفرعية القصوى (انظر مشكلة المصفوفة الفرعية القصوى )، ثم إيجاد المتتاليات الفرعية القصوى على يسار ويمين المتتالية الفرعية القصوى بشكل متكرر. تحليل هذه الخوارزمية مشابه لتحليل خوارزمية الفرز السريع : قد تكون المتتالية الفرعية القصوى صغيرة مقارنةً ببقية المتتالية، مما يؤدي إلى زمن تشغيل قدره${\displaystyle O(n^{2})}$في أسوأ الأحوال.

يتم تشغيل التطبيق القياسي لخوارزمية Ruzzo–Tompa في${\displaystyle O(n)}$يستغرق هذا الأسلوب وقتًا طويلاً ويستهلك مساحة O ( n )، حيث n هو طول قائمة الدرجات. يستخدم الخوارزمية البرمجة الديناميكية لبناء الحل النهائي تدريجيًا من خلال حل مجموعات فرعية أكبر تدريجيًا من المسألة. فيما يلي وصف الخوارزمية كما قدمه روزو وتومبا:

اقرأ الدرجات من اليسار إلى اليمين، واحتفظ بالمجموع التراكمي للدرجات المقروءة. احتفظ بقائمة مرتبة.${\displaystyle I_{1},I_{2},\ldots ,I_{j}}$من المتتاليات الفرعية المنفصلة. لكل متتالية فرعية${\displaystyle I_{j}}$سجل المجموع التراكمي${\displaystyle L_{j}}$من جميع الدرجات حتى الدرجة الموجودة في أقصى اليسار، ولكن ليس بما فيها${\displaystyle I_{j}}$والمجموع${\displaystyle R_{j}}$حتى النتيجة الأخيرة على اليمين، بما في ذلك${\displaystyle I_{j}}$.

تكون القوائم فارغة في البداية. تُقرأ الدرجات من اليسار إلى اليمين وتُعالج على النحو التالي. لا تتطلب الدرجات غير الموجبة أي معالجة خاصة، لذا تُقرأ الدرجة التالية. تُدمج الدرجة الموجبة في سلسلة فرعية جديدة.${\displaystyle I_{k}}$بطول واحد، ثم يتم دمجها في القائمة من خلال العملية التالية:

1. القائمة${\displaystyle I}$يتم البحث من اليمين إلى اليسار عن القيمة القصوى لـ${\displaystyle j}$مُرضٍ${\displaystyle L_{j}<L_{k}}$
2. إذا لم يكن هناك مثل هذا${\displaystyle j}$ثم أضف${\displaystyle I_{k}}$إلى نهاية القائمة.
3. إذا كان هناك مثل هذا${\displaystyle j}$، و${\displaystyle R_{j}\geq R_{k}}$ثم أضف${\displaystyle I_{k}}$إلى نهاية القائمة.
4. وإلا (أي، يوجد مثل هذا aj، ولكن${\displaystyle R_{j}<R_{k}}$), قم بتمديد التسلسل الفرعي${\displaystyle I_{k}}$إلى اليسار لتشمل كل شيء حتى النتيجة الموجودة في أقصى اليسار.${\displaystyle I_{j}}$حذف التسلسلات الفرعية${\displaystyle I_{j},I_{j}+1,\ldots ,I_{k}-1}$من القائمة، وألحقها${\displaystyle I_{k}}$إلى نهاية القائمة. أعد النظر في التسلسل الفرعي الممتد حديثًا.${\displaystyle I_{k}}$(أعيد ترقيمها الآن)${\displaystyle I_{j}}$) كما في الخطوة 1.

بمجرد الوصول إلى نهاية المدخلات، يتم عرض جميع التسلسلات الفرعية المتبقية في القائمة.${\displaystyle I}$هي القصوى. ^{[ 2 ]}

الكود التالي المكتوب بلغة بايثون ينفذ خوارزمية Ruzzo–Tompa:

def ruzzo_tompa ( scores ):"""خوارزمية Ruzzo–Tompa."""k = 0المجموع = 0# تخصيص مصفوفات بحجم nI ، L ، R ، Lidx = [[ 0 ] * len ( scores ) for _ in range ( 4 )]for i , s in enumerate ( scores ):المجموع += sإذا كانت قيمة s أكبر من 0 :# تخزين I[k] حسب مؤشرات (البداية، النهاية) للدرجاتI [ k ] = ( i , i + 1 )Lidx [ k ] = iL [ k ] = الإجمالي - sR [ k ] = الإجماليبينما صحيح :maxj = Nonefor j in range ( k - 1 , - 1 , - 1 ):إذا كان L [ j ] < L [ k ]:maxj = jاستراحةإذا لم يكن maxj يساوي None وكان R [ maxj ] < R [ k ] :I [ maxj ] = ( Lidx [ maxj ], i + 1 )R [ maxj ] = المجموعk = maxjآخر :k += 1استراحة# الحصول على أقصى تسلسلات فرعية باستخدام الفهارس المخزنةreturn [ scores [ I [ l ][ 0 ] : I [ l ][ 1 ]] for l in range ( k )]

• مشكلة المصفوفة الفرعية القصوى
• فرز سريع

• علي، سيد أرسلان؛ رضا، باسط؛ مالك، أحمد كامران؛ شهيد، أحمد رضا؛ فهيم، محمد؛ القهيز، هاني؛ كومار، يوجان جايا (2020). "نهج شبكة الاعتقاد العميق المُحسَّن والمُهيأ على النحو الأمثل (OCI-DBN) للتنبؤ بأمراض القلب بناءً على خوارزمية روزو-تومبا والخوارزمية الجينية المكدسة" . IEEE Access . 8. معهد مهندسي الكهرباء والإلكترونيات (IEEE): 65947-65958 . Bibcode : 2020IEEEA...865947A . doi : 10.1109/access.2020.2985646 . ISSN 2169-3536 . S2CID 215817246 .