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

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

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

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

وقت التعقيد

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

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

المصادر

^[1]

مراجع

موسوعات ذات صلة :

• موسوعة خوارزميات