دراسة تأثير موازاة خوارزميات التفرع و الحد (Bound & Branch) في تحسين أدائها


الملخص بالعربية

تستخدم خوارزميات التفرع و الحد (Bound and Branch) التي يرمز لها بـ B&B في حل مـسائل الأمثلة (الاستمثال) التوافقية التي تصنف درجة تعقيدها في الفئة hard-NP . و على الرغم من فعالية هذه الخوارزميات فقد بقي حجم المسائل التي تتمكن من حلها و البرهان على أمثلة الحـل محـدوداً بـسبب محدودية قدرات الحواسيب رغم تطورها الكبير. و مع ظهور البرمجة المتوازية و الحواسيب متعددة المعالجات فكر الباحثون بالاستفادة من قدرات هذه التقانات و الأجهزة في زيادة حجم المسائل المحلولة إلا أنه نجم عن الموازاة ثلاثة أنـواع مختلفـة مـن الشذوذ. يهدف هذا البحث إلى تقديم نموذج جديد لخوارزمية التفرع و الحد المتوازية يسمح بتحليـل فعاليـات الخوارزمية و يستند هذا النموذج إلى قواعد جديدة للاختيار بين العقد المتساوية التقويم بعد أن ثبت عجز قاعدة اختيار العقدة ذات التقويم الأفضل، كما نقوم بحساب حدود محكمة لكل قاعدة من القواعد و نبـرهن على إمكانية بلوغها، كما نقدم الشروط اللازمة و الكافية لظهور كل حالة من حالات الشذوذ النـاجم عـن موازاة الخوارزمية. درسنا و قارنا في هذا البحث النتائج الناجمة عن تجاهل بعض الفرضيات المستخدمة في خوارزميـات التفرع و الحد، و اقترحنا فضلاً عن ذلك استخدام النماذج غير المتزامنة للاستفادة القصوى من الإمكانيـات التي تقدمها البرمجة المتوازية.

المراجع المستخدمة

AKL, S. G. (1997).'' Parallel Computation Models And Methods'', Prentice Hall
Almasi, G. S., Gottlieb, A. (1994). ''Highly Parallel Computing'', The Benjamin Cummings Publishing Company, Inc
Aorts, E., Lenstra, J. K. (2003). ''Local Search In Combinatorial Optimization'', Princeton University Press

تحميل البحث