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

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

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

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

يتم وصف الخوارزمية بالخطوات التالية :
يتم بدىء الشجرة بقمة واحدة يتم اختيارها عشوائياً من الرسمة.
يتم إضافة أو نمو الشجرة من حافة أو إتجاه واحد للحواف التي تربط الشجرة إلى القمم التي ليست بعد في الشجرة، والعثور على الحدّ الأدنى للورن، ونقلها للشجرة.
يتم كرر تلك الخطوة مرتين(حتى تكون كل القمم في الشجرة).
للمنتسبين مع كل قمّة من الرسمة المطلق عليها مثلاً باسم 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 على سبيل المثال إن كانت صفر، ويمكن تعديلها لتجد شجرة واحدة ممتدة بدلاً من أكثر من شجرة ممتدة بالكامل، من خلال ذلك يمكن إيقافه كلما كان يصادف قمة أخرى تحمل العلم الخاص بأنه ليس هناك أي حافة مرتبطة بها.

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

لنفترض بأن 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 هي الحدّ الأدنى من الشجرة الممتدة.