الجديد طريقه معرفة نوع الجنين وترجيح المولود القادم بأذن الله - حكم التسول بالقرآن , آيات عن التسول , اية قرانية عن المتسولين - [بحث جاهز للطباعة] أهم بحث شامل حول الرضاعة الطبيعية - - لهجة شمالية (سعودية) بعض كلمات ومفردات اللهجة - إيديبوسات اسم القبيلة - 7 فوائد صحية للساونا.. تعزز المناعة وتجمل الشعر - ما هو علاج بكتيريا اليوريا بلازما؟ - فطار فطراني التاريخ - كونان (ناروتو) شخصيتها - هاتف ومعلومات عن الدكتور عبدالغني محمد الفتيح بالرياض - المحقق كونان (الموسم 11) عناوين الحلقات - هاتف وعنوان المستوصف النموذجي الطبي - النظيم, مدينة الرياض - الجامعة الوطنية - السودان كليات الجامعة - قنطريون جبلي الموئل والانتشار - ريام الجزائري عن حياتها - العلاقة بين الوزن والسرعة - سرطان البنكرياس مخاطر الإصابة - خلايا الأنبوب الغربالي - كربوكسي ميثيل السليولوز التحضير - مملكة الجبل (مسلسل) قصة المسلسل - [بحث جاهز للطباعة] بحوث علمية عن المجموعة الشمسية - - هاتف وعنوان مستشفى المغربي للعيون - عوالي, المدينة المنورة - عتيق بنشيكر عتيق بنشيكر في سطور - وصفة لعلاج سلس البراز بالاعشاب الطبيعية - حلقات عالم غامبول المدهش نظرة على السلسلة - هاتف ومعلومات عن مركز سيتي ماكس التجاري بالرياض - رواية (أدب) عناصر بناء الرواية - باب الكيسة - عراق المنشية التسمية - أرقام وهواتف عيادات د نعيمة عبدالله أبا الخيل بالرياض والعنوان - مكافآت طلاب مدارس تحفيظ القرآن الكريم بالمملكة العربية السعودية - هاتف وعنوان مستوصف البلاد الطبي - منفوحه, مدينة الرياض - طريقة تحضير الماسية بالحليب طبق من سوريا خطوة بخطوة - أشعر بحرقان يمتد من الحنجرة إلى المعدة...فما تشخيصه؟ - طريقة تحضير الخبز الحجازي اللذيذ بالصور - دالة ثابتة خصائص التابع الثابت - قيء بلون القهوة - قبيلة الشحري قبائل الشحري - فوائد دبس التمر للنفاس - [بحث جاهز للطباعة] طريقة و طرق و كيفية كتابة تقرير و تقارير عن زيارة و طبي و مدرسي و صحفي فني اداري - - هاتف وعنوان مكتب عبد الرحمن القصيبي للأدوية والمعدات الطبية - مشرفه, جدة - هواتف مؤسسة الثلاثيه الحديثة للمقاولات ومعلومات عنها بالسعودية - قبيلة الهزازي أقسام قبيلة الهزازي - الكشوف الجغرافية الإسبانية دوافع الكشوف الجغرافية الإسبانية - الاستكمال الرياضي بفروق نيوتن طرق الاستكمال - طريقة تحضير القراقيش المصريه من الشيف منال العالم - [ رقم هاتف ] جوازات منفذ الوديعة بالسعودية - مال خاتون خلفية - دائرة مقاومة ومكثف مقدمة - الدرملي فقري تملي (فيلم) قصة الفيلم - نترات النحاس الثنائي الخواص - هاتف مدرسة علي بن المديني ابتدائي و معلومات عنها بالرياض - اقتصاديات الطاقة معلومات تاريخية - قبيلة الصلبه نسب القبيلة وافخاد القبيلة - نظائر الكلور كلور-36 - رسائل أدبية مزعجة السبب في تسميتها بالرسائل الأدبية العشوائية - حمدا ولد التاه نسبه - كهنة دان (هرازبي الجنوبي) - لمحة عن تضاريس الكويت - تاريخ البحرين تايلوس وأرادوس - ويب أوبيديا - القلاب J-K طريقة عمل القلاب JK - نظرية فيثاغورس المبرهنة - [بحث جاهز للطباعة] أجدد بحث عن كيفية كتابة تقرير ميداني - - جسر إلى تيرابيثيا ملخص - سوبر ماريو (سلسلة) الألعاب - نظرية التلقي المزدوج - الحفر النفقي أنواعه - هاتف وعنوان مطاعم حراء - الصفا, جدة - هاتف وعنوان مجموعة المتبولي المتحدة للأجهزة المنزلية - خميس مشيط, عسير - [بحث جاهز للطباعة] بحث علمي جاهز ومفصل عن السمنة - - [طب بديل ] عود الصليب - مواضيع صحية - سعيد بن قيس الهمداني اسمه الكامل - فوائد ثمرة البابايا للبشرة - معركة تاننبرغ - بسلامته عايز يتجوز (فيلم) قصة الفيلم - سعود بن إبراهيم البوسعيدي نبذه عنه - [بحث جاهز للطباعة] قائمة بعناوين مشاريع التخرج لتخصص الخدمة الاجتماعية - - نظرية ستورم-ليوفيل - توصيل دلتا الفرق بين توصيل دلتا وتوصيل نجمة - هاتف وعنوان مؤسسة الشعيبي للأحذية - باب مكه, جدة - طريقة عمل ومقادير الدولمه العراقيه من مطبخ منال العالم - سدير بن عامر البدراني الدوسري حماية البدارين الدواسر لنجد من التمدد الشيعي - فوائد قربة الماء الساخن - روبرك مكونات الروبرك - هاتف وعنوان المستشفى التخصصي بأبها - ابها, مدينة ابها - الطراز الدولي (عمارة) تاريخ - جيل 27 نبذة عن مفهوم الجيل - الحلة التسمية - [بحث جاهز للطباعة] بحث عن اللغة العربية والكفايات اللغويه - - نظرية الحكم الاجتماعي - ميسون السويدان السيرة الذاتية - هاتف وعنوان مستوصف منار الطبي - بقيق, الدمام - بوكاهونتاس (فيلم 1995) ملخص القصة - أنيميا دياموند-بلاكفان الأعراض - رجيم الجريب فروت للتخلص من دهون البطن والأرداف - [بحث جاهز للطباعة] قائمة بعناوين مشاريع التخرج لتخصص التربية الابتدائية - - وصفة هائلة من الطب البديل لعلاج الروماتيزم أمراض العظام والمفاصل بالاعشاب - ألفينترن أقراص مضاد للإلتهابات والتورم Alphintern Tablets - [بحث جاهز للطباعة] بحث علمي جاهز عن التضخم - -
آخر المشاهدات [طب بديل ] نبات الجابوراندي يضبط ضغط العين ويشفي من الجلوكوما - مواضيع صحية - عبثت بنفسي ونزلت نقطتان من الدم، هل فقدت عذريتي؟ - الموت القادم إلى الشرق (مسلسل) قصة المسلسل - كيمياء عضوية فلزية خصائص المركبات العضوية الفلزية - علاج مسمار الاقدام -تخلص من مسامير الاقدام بطرق طبيعية و فعالة - [طب بديل ] رجيم ينزل الوزن 20 كيلو بالشهر للدكتور أسامة حمدي - مواضيع صحية - رمال رمال حياته - سور القران لكل شهر من شهور الحمل - يوكي كاجي أدواره في الأنمي - الرهبة من فض غشاء البكارة - رجاء مكي - [بحث] الإعجاز التربوي في القرآن الكريم (أبحاث ودراسات )ا - ملخصات وتقارير جاهزة للطباعة - شخصيات مسلسل الدبور الجزء الثاني شخصيات المسلسل - [بحث جاهز للطباعة] قائمة بعناوين مشاريع التخرج لتخصص التربية الاسلامية - - طريقة عمل الرفيس القسنطيني- من المطبخ الجزائري لا تفوتك - حساب محيط الخصر و الوزن المثالي و نسبة الدهون و دليل كتلة الجسم Body Mass Index - رجيم ورشاقة و تنحيف وانقاص الوزن - معنى مقولة " لا تنكح الحنانة والمنانة والحداقة والبراقة " - باب المندب معلومات جغرافية - وصفة هائلةمن الطب البديل لعلاج مشاكل الدوره الشهرية و الحيض بالاعشاب - مشكلتي أن الأشفار متباعدة عن بعضها، هل هذا شيء طبيعي؟ - معمارية الحاسوب معمارية الحاسوب - جوزيف اوروسمال - سعد اليتيم (فيلم) قصة الفيلم - [بحث جاهز للطباعة] مشروع تخرج علم اجتماع جاهز , مشاريع تخرج علم اجتماع - - الانسداد الدائم في الأنف - ليل المسافرين (مسلسل) قصة المسلسل - نظرية التقييم (تحليل الخطاب) - النشرة الداخلية لعقار كاريزوبرودول Carisoprodol - الفلاح الفصيح ملخص القصة - ملكاوي أصل العشيرة - معطف أبي (فيلم) - مقتل روجر أكرويد (رواية) ملخص الرواية - هاتف ومعلومات عن فندق العطاس بالمدينة المنورة - رايلي ستيل حياتها - إدارة نظم المعلومات للقوات المسلحة (مصر) مهام الإدارة - فيصل محمود مدوه الموهبة المبكرة - طريقة تحضير الميرمية (أعشاب) بطريقة سهلة - خصائص الوصف انواع الوصف - هاتف وعنوان مكتب محمد حسين العمودي - الرويس, جدة - خماسي أضلاع الخماسي المنتظم - الحارث بن كلدة سبب وفاته - هواتف مستشفى الصحة النفسية و معلومات عنها بعسير بالسعودية - كلية الحرس السلطاني العماني التقنية - كيناكومب كريم لعلاج الإلتهابات الجلدية والتسلخات Kenacomb Cream - طريقة عمل الميكاتو بطعم لذيذ - تعريف النص الوصفي وما هو - رتبة العصويات - بنات العم (فيلم) القصة - جامعة الفاشر كليات ومراكز ومعاهد الجامعة - فلاردينجن طوبوغرافيا - سوق المتعة (فيلم) قصة الفيلم - نوران جاد(ممثلة) أعمالها - علي ولد زايد من أقواله المشهورة في اليمن - مثل تعريف المثل الشعبي - عبد الواحد الدكالي حياته - لهجة جنوبية لهجة منطقة عسير - نور الجليل الدندر الموقع - طريقه معرفة نوع الجنين وترجيح المولود القادم بأذن الله - هاتف وعنوان مستوصف الصحة والحياة - الخليج, الدمام - سعود بن إبراهيم البوسعيدي نبذه عنه - القرية الخضراء تعريف - أمونيوم لوريال سلفات - فيروز (مغنية) نشأتها - وصفة لعلاج سلس البراز بالاعشاب الطبيعية - لهجة شمالية (سعودية) بعض كلمات ومفردات اللهجة - طريقة عمل كعكة حليب النيدو اللذيذة - بوكاهونتاس (فيلم 1995) ملخص القصة - احذية رياضية للرجال - بروبيوتيك تاريخ البروبيوتيك - توصيل دلتا الفرق بين توصيل دلتا وتوصيل نجمة - سوبر ماريو (سلسلة) الألعاب - معلومات عن دواء اكسيمستان Exemestane لعلاج سرطان الثدي - [بحث] اكتشف خط زمنك · - ملخصات وتقارير - تاريخ البحرين تايلوس وأرادوس - أحمد ميتو نبذة عنه - هاتف وعنوان مستوصف مستشاري الطبي - بيشه, عسير - كارثة بوبال - هاتف وعنوان مجموعة المتبولي المتحدة للأجهزة المنزلية - خميس مشيط, عسير - نظرية التلقي المزدوج - طريقة تحضير القراقيش المصريه من الشيف منال العالم - جسر إلى تيرابيثيا ملخص - دائرة مقاومة ومكثف مقدمة - فوائد المتة للكلى - نظرية فيثاغورس المبرهنة - رسائل أدبية مزعجة السبب في تسميتها بالرسائل الأدبية العشوائية - جورج وجونغل (فيلم) القصة - نفط أصل النفط - هاتف مدرسة علي بن المديني ابتدائي و معلومات عنها بالرياض - ابيات شعر باسم زمزم , معنى اسم زمزم - معلومات عن حقن فورتيو Forteo - فوائد ثمرة البابايا للبشرة - الحفر النفقي أنواعه - مكافآت طلاب مدارس تحفيظ القرآن الكريم بالمملكة العربية السعودية - [بحث جاهز للطباعة] بحث عن اللغة العربية والكفايات اللغويه - - زمن عود امتلاء الشعيرات طالع أيضا - [بحث جاهز للطباعة] بحث علمي جاهز عن التضخم - - لمحة عن تضاريس الكويت - علو شفط إيجابي صافي طالع أيضا - صالح هواري نشأته وعلمه - جرائم الأبجدية (فيلم) بطولة - اختفاء جعفر المصري (فيلم) قصة الفيلم - مفصل رزي أمثلة على المفصل الرزي - هاتف وعنوان مشغل سميرة محمد المصري النسائي - النسيم, مدينة الرياض - ميزانية و تكاليف ودراسة جدوى مشروع تجهيز وتصنيع وتعبئة لحوم ودواجن - المعيار الدولي للوصف الأرشيفي العام لمحة تاريخية - الشروط المطلوب استيفائها للحصول على ترخيص نقل البضائع والمهمات بأجر بالسعودية شروط ترخيص نقل البضائع - السعيد الزاهري نشأته ودراسته - الخطوط الملكية المغربية الرحلة 630 - دمي ودموعي وابتسامتي (فيلم) قصة الفيلم - [بحث جاهز للطباعة] بحث علمي جاهز ومفصل عن السمنة - - هواتف و عناوين مكتب الخطوط الجويه العربيه السعوديه في جاكرتا - دالة الإشارة خصائص الدالة - هافا ناجيلا نص الأغنية مع ترجمة عربية - دبلجة المحقق كونان نظرة عامة - [بحث جاهز للطباعة] بحوث علمية عن المجموعة الشمسية - - محاولة عيش كاتب الرواية - معركة عين دارة الخلفية التاريخية - فرط ضغط الدم الرئوي الأعراض و العلامات - ابن حدري شهرته - البؤساء كلمة أولى - اوسوفورتين اقراص لعلاج نقص فيتامين د Ossofortin Vitamins Tablets - باميلا (رواية) - صبغة الهيماتوكسيلين والأيوزين - تشوهات قوامية - استعلام عن القضايا المرفوعة ضدكم بالكويت - كالسيترون كبسولات مكمل غذائي للحمل والرضاعة Calcitron Capsules - سهام بن زاموش - حكم التسول بالقرآن , آيات عن التسول , اية قرانية عن المتسولين - مشروع تخرج لطلبة كلية التربية قسم اللغة الإنجليزية جاهز للطباعة - عبد الله الشلتي نشأته - نظرية ثراء وسائل الإعلام خلفية عن النظرية - أفضل محل أسماك بالرياض - جهاز الجيبة الفغرية الرقائق والصفائح القاعدية - هاتف مركز النهضة والخليج الصحي بالرياض و معلومات عنه بالسعودية - تداخل الموجات التداخل البناء والتداخل الهدام - بهبهان سبب التسمية - هل تناول حبوب كليمن بطريقة خاطئة من الممكن أن يؤثر على الهرمونات؟ - آلة تبريد تبريد عميق علم التبريد - هاتف وعنوان شركة مصنع الأضواء لإنتاج وحدات الإنارة - الحاير, مدينة الرياض - وجود قطعة لحمية على فتحة المهبل، هل هو دليل على عدم العذرية؟ - الجرعة الصحيحة لدواء الفلوزاك لعلاج الوساوس - رمل قوالب السباكة الرمل الأخضر - الليالي الطويلة (فيلم) فريق العمل - الجيزال كريم لعلاج الالام والالتهابات الروماتيزمية Algesal Cream - ثيودوريك العظيم الشباب - جمعية الإرشاد والإصلاح التأسيس - تقرير عن تاون سكوير دبي .. شقق ( جنة و زهرة ) - سنجيولير أقراص للعلاج والوقاية من الربو المزمن Singulair Tablets - دلتا كرونكر - هاتف وعنوان مطعم الطازج - بريده, القصيم - المعابد اليونانية نشأة المعابد اليونانية - إيديبوسات اسم القبيلة - هل يحق لي رفع دعوى رد اعتبار عن تشويه سمعه بدعوى كيديه - خس التصنيف والتسمية - طريقة عمل الهفيت / الفتيت من الشيف دعد أبو جابر - فض غشاء البكارة وكيفيته لـ+18 - هاتف ومعلومات عن مستوصف زهرة الأمل الطبي 2 بالرياض - أقوال دوستويفسكي عن النساء - نظرية الغرس الثقافي تعريف - هاتف وعنوان شركة الرضا للصناعات الغذائية المحدودة - النزله, جدة - معمر بن الحارث معمر بن الحارث الجمحي - طريقة عمل بتر تشكين من مطبخ منال العالم - آلة ويمشورست مكونات آلة ويمشورست - قبيلة الصلبه نسب القبيلة وافخاد القبيلة - ملف شامل لاهم وصفات الدكتور عادل عبد العال لعلاج الامراض المختلفة بالاعشاب - عدلي لملوم تمرده على قانون الإصلاح الزراعي - سبب الشعور بالغثيان عند القراءة أثناء ركوب السيارة وعلاجه - وصفة هائلة من الطب البديل لعلاج الالتهاب الكيسي والأوتار بالاعشاب - هاتف مركز الربوة الصحي بالرياض و معلومات عنه بالسعودية - [بحث جاهز للطباعة] تحميل أبحاث علمية باللغة الإنجليزية لطلاب المدارس والجامعات - - طريقة تحضير سندويشات الصوصيص بالصور - طريقة عمل مشروب الروينه بطعم لذيذ - هاتف وعنوان مطبخ مكة - ابها, مدينة ابها - متلازمة السن المتصدع التصنيف والتعريف - تلبيسة الاسنان .. هل يمكن ازالة التلبيسه الدائمه؟ - علال القلدة (فيلم) - كيفية توليد الموجات الكهرومغناطيسية - شمع معدني انواع الشمع المعدني (شمع النفط) - إدريس الضحاك مسيرته - بوليوود التاريخ - المحقق كونان (الموسم 11) عناوين الحلقات - هل نزول الدم عند فض غشاء البكارة ضروري لمعرفة العذرية من عدمها؟ - ميكرومتر (جهاز قياس) مكونات جهاز الميكرومتر العادي - [بحث جاهز للطباعة] بحث علمى حول مادة الرياضيات - - بيدامان كروس فاير-كروس فايت بيدامان القصة - خصائص معلمة رياض الأطفال - منزل العائلة المسمومة (فيلم) - فريديريك فروبل لمحة عن حياته - معهد الخرطوم الدولي للغة العربية نشأة المعهد - [ رقم هاتف ]مكتب الضمان الاجتماعى ب أبها ومعلومات عنها بالسعودية - قائمة شخصيات كابتن ماجد الشخصيات - وقعة طلال الثانية (1290) ما قبل المعركة - جلسات نسائية (مسلسل) القصة - طريقة عمل الزيتون الاسود على طريقة مدام منال - جون ليزلي - شهرزاد (شخصية) وصف شهرزاد - أل في أم أش - مويت هنسي لوي فيتون التاريخ - إينازوما إليفن الأسلوب - جسيمات فضة نانوية التخليق التحضير - نظرية الإشارات الانتقاء الجنسي -
اليوم: الاثنين 30 نوفمبر 2020 , الساعة: 10:53 م


اعلانات

محرك البحث


خوارزمية بريم خوارزمية بريمّ

آخر تحديث منذ 4 يوم و 22 ساعة 11 مشاهدة

اعلانات
عزيزي زائر الموقع تم إعداد وإختيار هذا الموضوع خوارزمية بريم خوارزمية بريمّ فإن كان لديك ملاحظة او توجيه يمكنك مراسلتنا من خلال الخيارات الموجودة بالموضوع.. وكذلك يمكنك زيارة القسم وتصفح المواضيع المتنوعه... آخر تحديث للمعلومات بتاريخ اليوم 26/11/2020

خوارزمية بريمّ





خوارزمية بريمّ هي أحد أهم المسائل في علوم الحاسوب ، تعتبر خوارزمية بريمّ إحدى الخوارزميات المندرجة تحت الخوارزمية الطمّاعة أو الشجّعة، التي تعمل على إيجاد الحد الأدنى للشجرة الممتدة على الرسمة الغير موجّهة(بإتجاه واحد).

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


تم تطوير الخوارزمية على يد عالم الرياضيات كزيتش، وبعد ذلك تمّ اكتشافها من قبل عالم الكمبيوتر روبرت سي.

اكتشفها بريمّ عام ظ،ظ©ظ¥ظ§، و ادسكير ديجسترا عام ظ،ظ©ظ¥ظ©. لذلك يتم تسميها في بعض الأوقات بخوارزمية (د ج ب) نسبة لأسماء العلماء الذين قاموا باكتشاف الخوارزمية.


وتشمل أيضاً خوارزميات معروفة لهذه المشكلة مثل خوارزمية كروسكال وخوارزمية بروفكا.

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

مع ذلك، تعمل خوارزمية بريمّ بشكل منفصل لكل مكون متصل على الرسمة، ويمكن أيضاً أن تستخدم للحصول على الحدّ الأدنى للرسمات الممتدة.


من حيث تعقيد الوقت التقريبي، فهذه الخوارزميات الثلاثة سريعة على حدّ سواء للرسمات الضئيلة، ولكنها أبطأ من الخوارزميات الأكثر تطوراً.

في المقابل فهي كافية للرسمات الكثيفة، على أنه يمكن إجراء خوارزمية بريمّ لتعمل على الزمن الخطي،لإجماع أو تحسين حدود الوقت بالنسبة لخوارزميات أخرى.


وصف تفصيلي لخوارزمية بريمّ





يتم وصف الخوارزمية بالخطوات التالية

يتم بدىء الشجرة بقمة واحدة يتم اختيارها عشوائياً من الرسمة.

يتم إضافة أو نمو الشجرة من حافة أو إتجاه واحد للحواف التي تربط الشجرة إلى القمم التي ليست بعد في الشجرة، والعثور على الحدّ الأدنى للورن، ونقلها للشجرة.

يتم كرر تلك الخطوة مرتين(حتى تكون كل القمم في الشجرة).


للمنتسبين مع كل قمّة من الرسمة المطلق عليها مثلاً باسم v، أي [C[V (أرخص تكلفة اتصال مع V) والحافة [E[V (الحافة تنتسب لأقل إتصال).


لبدء تلك القيم، يتم وضع كل القيم في [C[V لكل [E[V لتكون كإشارة خاصة للقيم التي تعني أنه لا يوجد حافة ربط v في القمم السابقة.


البدء في تفريغ F ومجموعة Q التي لم يتضمنها القمم بعد في F (البدء في كل القمم).

كرر الخطوات التالية حتى تفرّغ ال Q

البحث وإزالة V من الQ التي لها أقل إحتمالية من ال .C[V]

إضافة V إلى F، وأيضاً وضع شرط إذا كانت E[V] ليست إشارة خاصة للقيم، أيضاً أضف E[V] ل F، ثم قم بإعادة الحلقات VW مربوطاً ب V للقمم الأخرى.

لكل حافة، إذا W مازالت تنتمي ل Q و VW أصغر وزناً من C[W]، إذن قمّ بالخطوات التالية


ضع C[W] لتكلفة .VW

ضع E[W] لنقاط الحواف .VW

عودة ل.F


كما هوّ موضّح أعلاه، سيتم اختيار قمة الرأس ابتداءاً من الخوارزمية ، لأن التكرار الأول من الحلقة الرئسية للخوارزمية سيكون لمجموعة ال Q كلها ستكون بنفس الأوزان، والخوارزمية تلقائياً ستبدأ بشجرة جديدة في F عندما يُكمل الشجرة الممتدة لكل عناصر الإتصال عن طريق مدخلات الرسمة.

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


وقت التعقيد





إنّ الطابع التعقيدي لخوارزمية بريمّ تعمتد على هيكل البيانات المستخدمة في الرسمة لترتيب الحواف حسب الوزن، التي يُمكن أن تتم باستخدام طابور الأولويات.




! الهيكلية لأقل حافة وزن !! (المجموع)

-

adjacency matrix , searching O( V ^2)
-

binary heap and adjacency list O(( V + E ) log V ) O( E log V )
-

Fibonacci heap and adjacency list O( E + V log V )



تنفيذ بسيط لخوارزمية بريمّ، ذلك باستخدام مصفوفة الجوار أو الرسمة المتماثلة القائمة على البحث الخطي لمجموعة من الأوزان لإيجاد الحدّ الأدنى من وزن الحافة، إضافة الى أنه يتطلب O( V 2) بتنفيذ الوقت.

ومع ذلك الوقت الذي يتم بالتنفيذ يُمكن أن يتم تحسينه بسكل كبير من جراء استخدام أكوام (heaps) لتنفيذ إيجاد الحدّ الأدنى لحواف الوزن في الحلقة الداخلية المتكررة للخوارزمية.


أول نسخة مُحسّنة تستخدم الكومة (heap) لتخزين جميع الحواف من مدخلات الرسمة، الذي يتم بحسب ترتيب الأوزان.

هذا يعني أنه في أسوأ الأحوال سيكون O( E log E ). ولكن يُمكن تحسين تخزين القمم بدلاً من الحواف أكثر فأكثر. يجب على كومة (heap) أن تقوم بترتيب القمم من أصغر حافة حسب الوزن التي تربطهم جزئياً لأي قمة في الشجرة الممتدة (أو إلى ما لا نهاية إذ لم توجد مثل هذه الحافة). في كل مرة يتم اختيار قمة V وإضافتها للحدّ الأدنى من الشجرة الممتدة، يتم تنفيذ عملية الإنخفاض الرئيسي في كل القمم W خارج الشجرة الممتدة للحدّ الأدنى بحيث تكون V متصلةبW، ووضع الرمز ألى الحدّ الأدنى من قيمته السابقة ، علماً أنها ستكوت تكلفة الحافة .(v,w)


باستخدام وسيلة الثنائي البسيطة لحلّ هيكلة البيانات، يُمكن لخوارزمية بريمّ أن تعمل لتشغيل الوقت لنتفيذه

O( E log V ) حيث E هي عدد الحواف و V هي عدد القمم.


باستخدام الكومة (heap) الأكثر تطوراً، يُمكن أن تُخفَض إلى (O( E + V log V التي هي أسرع عندما تكون الرسمة مكثّفة أي أنه يُمكن أن تكون ( E هي د‰( V ) ، وعندما تكون في وضع الزمن الخطّي تكون E هيّ على الأقل V log V.


للرسامات الأكثر كثافة يُمكن إجراء خوارزمية بريمّ للتشغيل بالنسبة للزمن الخطي حيث تكون أكثرها بساطة، عندها يتم تطبيقها/ استخدامها بالكومة d-ary heap بدلاً من كومة (Fibonacci heap ) فيبوناتشي.


إثبات صحة خوارزمية بريمّ





لنفترض بأن P متصلة،في الرسمة التي لها وزن. في كل تكرار لخوارزمية بريمّ، يجب أن تكون هناك ميزة التي تتم بها ربط قمة الرأس في الرسمة إلى القمة خارج الرسمة. ونظراً لارتباط P ، سيكون هناك دائماً طريق لكل قمة. الناتج سيكون Y لخوارزمية بريمّ وهو الشجرة، لأن الحافة و القمة تم إضافتهما للشجرة Y المتصلة. لنفرض Y1 هي الحدّ الأدنى للرسمة P.


وإذا كانت Y Y1 هي الحدّ الأدنى من الشجرة الممتدة. في خلاف على ذلك دعونا نقول لوّ أن e هي أول حافة يتم إضافتها أثناء البناء الشجرة Y التي ليست بY1 ، و V تكون مجموعة قمم متصّلين في حواف يتم إضافتهم قبل e.


بعد ذلك يتم وضع النقطة النهائية ل e في المجموعة V والبقية لا يتم وضعهم. منذ أن الشجرة Y1 هي رسمة فيها شجرة ممتدة لP، فهناك مسار في شجرة Y1 للإنضمام لنقطة النهاية.

كما يتم توجيه المسار بكامله، لابد من إلتقاء الحافة f مع المنضمّين من المجموعة V إلى التي ليست من المجموعة V. حالياً في حالة التكرار يتم إضافة حافة e إلى الشجرة Y،

ويمكن أيضاً إضافة حافة f، ويمكن أيضاً إضافة الحافة e إذا كان وزنها أقل من e ، في تلك الحالة الحافة f لم تُضاف،على ذلك فإننا نستنتج أن -


(W(f)> W(e.

لنجعل مثلاً شجرة Y2 التي تمّ الحصول عليها عن طريق إزالة الحافة f وإضافة الحافة e للشجرة Y1. من هنا يمكننا القول أن من السهل إثبات أن Y2 متصلة، ولديها نفس عدد الحواف للشجرة Y1 ، و مجموع الأوزان لتلك الحواف ليست أكبر من الشجرة Y1، بالتالي فإنّ الحدّ الأدنى للشجرة من الرسمة P وعلى ذلك فإنه يحتوي علي الحافة e وإضافة على ذلك يتم إضافة كل الحواف خلال بناء مجموعة V.

كرر الخطوات المذكورة في الأعلى وسوف يتم الحصول على الحدّ الأدنى للشجرة من الرسمة P المطابقة للشجرة . Y هذا يدل أن Y هي الحدّ الأدنى من الشجرة الممتدة.


المصادر


https //en.wikipedia.org/wiki/Prim 27s_algorithm

غير مصنفة

شاركنا رأيك

 
اعلانات
التعليقات

لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا

أقسام الموقع المتنوعة أوجدت لخدمة الزائر ليسهل عليه تصفح الموقع بسلاسة وأخذ المعلومات تصفح هذا الموضوع خوارزمية بريم خوارزمية بريمّ ويمكنك مراسلتنا في حال الملاحظات او التعديل او الإضافة او طلب حذف الموضوع ...آخر تعديل اليوم 26/11/2020



الاكثر مشاهدة في شبكة طريق 95
اخبار لم تشاهدها من قبل
موضوعات خاصة بالقارئ
الأكثر مشاهدة خلال 24 ساعة
الأكثر قراءة
الموضوعات الاكثر بحث علي مدار الساعة
الموضوعات الاكثر مناقشة
الاكثر مناقشه بالقرب مني