Khalid Saud Al-Zamil2022-05-182022-05-184624https://drepo.sdl.edu.sa/handle/20.500.14154/2109في مسألة إيجاد شجرة الاتصال الممتدة المثلى، لابد من إيجاد شجرة تربط جميع الرؤوس في الرسم البياني الكامل، هذه الشجرة الممتدة لابد أن توفر جميع متطلبات الاتصال اللازمة للرؤوس وبأصغر تكلفة إجمالية. مسألة الشجرة الممتدة ذات المسافة المثلى (ODST)، والتي تكون متطلباتها ثابتة، هي حالة خاصة من مسألة الشجرة الممتدة ذات الاتصال الأمثل (OCST)، كلا المسألتين تعرفان بأنهما (NP-hard). نقوم في هذه الرسالة، باقتراح خوارزميات عشوائية لحل حالتين من مسألة (ODST) وبفعالية عالية، وذلك بتوليد أشجار ممتدة عشوائياً مع خصائص معينة. لدينا حدس بأن استخدام هذه الطريقة يؤدي إلى الحصول على حلول قريبة جداً من الحل الأمثل، قمنا بعمل تجارب لتقييم الخوارزميات المقترحة، هذه التجارب تضمنت اختبار الخوارزميات المقترحة لحل الحالات الخاصة باستخدام عدة رسومات بيانية مولدة عشوائياً، بالإضافة إلى شبكات الـ (hypercube) و (butterfly) إلى أبعاد محددة.enThesis