On the optimum communication cost problem in interconnection network
No Thumbnail Available
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Saudi Digital Library
Abstract
في مسألة إيجاد شجرة الاتصال الممتدة المثلى، لابد من إيجاد شجرة تربط جميع الرؤوس في الرسم البياني الكامل، هذه الشجرة الممتدة لابد أن توفر جميع متطلبات الاتصال اللازمة للرؤوس وبأصغر تكلفة إجمالية. مسألة الشجرة الممتدة ذات المسافة المثلى (ODST)، والتي تكون متطلباتها ثابتة، هي حالة خاصة من مسألة الشجرة الممتدة ذات الاتصال الأمثل (OCST)، كلا المسألتين تعرفان بأنهما (NP-hard). نقوم في هذه الرسالة، باقتراح خوارزميات عشوائية لحل حالتين من مسألة (ODST) وبفعالية عالية، وذلك بتوليد أشجار ممتدة عشوائياً مع خصائص معينة. لدينا حدس بأن استخدام هذه الطريقة يؤدي إلى الحصول على حلول قريبة جداً من الحل الأمثل، قمنا بعمل تجارب لتقييم الخوارزميات المقترحة، هذه التجارب تضمنت اختبار الخوارزميات المقترحة لحل الحالات الخاصة باستخدام عدة رسومات بيانية مولدة عشوائياً، بالإضافة إلى شبكات الـ (hypercube) و (butterfly) إلى أبعاد محددة.