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

خوارزمية بريم
في علوم الحاسوب، تعد خوارزمية بريم Prim's algorithm (المعروفة أيضًا باسم خوارزمية Jarník) هي خوارزمية جشعة تعثر على الحد الأدنى من الشجرة الممتدة لرسم بياني مرجح غير موجه (weighted undirected graph). هذا يعني أنه يعثر على مجموعة فرعية من الحواف التي تشكل شجرة تتضمن كل رأس، حيث يجري تقليل الوزن الإجمالي لجميع حواف الشجرة إلى أدنى حد. تعمل الخوارزمية عن طريق بناء هذه الشجرة باستخدام رأسًا واحدًا في كل مرة، وتبدأ برأس عشوائية، في كل خطوة تضيف أرخص اتصال ممكن من الشجرة إلى رأس أخرى.
قام عالم الرياضيات التشيكي Vojtěch Jarník بتطوير الخوارزمية في عام 1930، ثم أعاد اكتشافها ونشرها من علماء الحاسوب Robert C. Prim في عام 1957 وEdsger W. Dijkstra في عام 1959. لذلك، يطلق عليها أحيانًا خوارزمية جارنيك، أو خوارزمية Prim – Jarník، أو خوارزمية Prim – Dijkstra أو خوارزمية DJP.
تشمل الخوارزميات الأخرى المعروفة لهذه المشكلة خوارزمية Kruskal وخوارزمية Borůvka. تجد هذه الخوارزميات الحد الأدنى من مجموعة التفرعات الممتدة في رسم بياني محتمل غير متصل ؛ في المقابل، فإن الشكل الأساسي لخوارزمية بريم لا يجد سوى الحد الأدنى من الأشجار الممتدة في الرسوم البيانية المتصلة. ومع ذلك، عند تشغيل خوارزمية بريم بشكل منفصل لكل مكون متصل بالرسم البياني، يمكن أيضًا استخدامها للعثور على الحد الأدنى من مجموعة التفرعات الممتدة. من حيث تعقيدها الزمني المقارب، فإن هذه الخوارزميات الثلاثة متساوية في السرعة بالنسبة للرسوم البيانية المتفرقة، ولكنها أبطأ من الخوارزميات الأخرى الأكثر تعقيدًا. ومع ذلك، بالنسبة للرسوم البيانية الكثيفة بما فيه الكفاية، يمكن عمل خوارزمية بريم للعمل في الوقت الخطي، أو تلبية أو تحسين الحدود الزمنية للخوارزميات الأخرى.
الوصف
يمكن وصف الخوارزمية بشكل غير رسمي بأنها تؤدي الخطوات التالية:
بمزيد من التفصيل، يمكن تنفيذها باتباع السودوكود أدناه.
كما هو موضح أعلاه، سيجري اختيار رأس البداية للخوارزمية بشكل عشوائي، لأن التكرار الأول للحلقة الرئيسية للخوارزمية سيكون له مجموعة من الرؤوس في Q التي لها أوزان متساوية، وستبدأ الخوارزمية تلقائيًا في شجرة جديدة في F عندما تكمل شجرة ممتدة لكل مكون متصل من الرسم البياني. يمكن تعديل الخوارزمية لتبدأ بأي رأس معين من خلال ضبط C[s] ليكون رقمًا أصغر من القيم الأخرى لـ C (على سبيل المثال، صفر)، ويمكن تعديله للعثور على شجرة ممتدة واحدة فقط بدلاً من غابة ممتدة بالكامل (تطابق الوصف غير الرسمي بشكل أوثق) عن طريق التوقف متى واجهت رأس أخرى قد وُضع علامة عليها على أنها لا تحتوي على حافة مرتبطة.
تختلف الصور المختلفة للخوارزمية عن بعضها البعض في كيفية تنفيذ المجموعة Q : كقائمة مرتبطة بسيطة أو مصفوفة من الرؤوس، أو كهيكل بيانات طابور أولوية أكثر تعقيدًا. يؤدي هذا الاختيار إلى اختلافات في التعقيد الزمني للخوارزمية. بشكل عام، ستكون قائمة الانتظار ذات الأولوية أسرع في العثور على قمة الرأس v بأقل تكلفة، ولكنها ستستلزم تحديثات أكثر تكلفة عندما تتغير قيمة C[w].
تعقيد الوقت
يعتمد التعقيد الزمني لخوارزمية بريم على هياكل البيانات المستخدمة للرسم البياني ولترتيب الحواف بالوزن، وهو ما يمكن القيام به باستخدام قائمة انتظار ذات أولوية. يوضح الجدول التالي الخيارات النموذجية:
يتطلب التنفيذ البسيط لخوارزمية بريم، باستخدام مصفوفة متجاورة أو تمثيل رسم بياني لقائمة متجاورة والبحث الخطي في مصفوفة من الأوزان للعثور على حافة الوزن الأدنى لإضافتها، وقت تشغيل O(|V|2). ومع ذلك، يمكن تحسين وقت التشغيل هذا بشكل كبير باستخدام أكوام لتنفيذ إيجاد الحد الأدنى من حواف الوزن في الحلقة الداخلية للخوارزمية.
يستخدم الإصدار المحسن الأول كومة لتخزين جميع حواف الرسم البياني، مرتبة حسب وزنها. هذا يؤدي إلى وقت تشغيل أسوأ حالة O(|E| log |E|). لكن تخزين الرؤوس بدلاً من الحواف يمكن أن يحسنها أكثر. يجب أن ترتب الكومة القمم بأصغر وزن للحافة يربطها بأي رأس في الشجرة الممتدة الدنيا المنشأة جزئيًا (MST minimum spanning tree) (أو اللانهاية في حالة عدم وجود مثل هذه الحافة). في كل مرة يجري فيها اختيار رأس v وإضافته إلى MST، يتم إجراء عملية تقليل-مفتاح decrease-key على جميع القمم w خارج MST الجزئية بحيث يتم توصيل v بـ w، مع ضبط المفتاح على أدنى قيمته السابقة وتكلفة الحافة من (v،w).
باستخدام بنية بيانات كومة ثنائية binary heap بسيطة، يمكن الآن عرض خوارزمية بريم للتشغيل في الوقت O(|E| log |V|) حيث |E| هو عدد الحواف و|V| هو عدد الرؤوس. باستخدام كومة فيبوناتشي أكثر تعقيدًا، يمكن خفض ذلك إلى O(|E| + |V| log |V|)، وهو أسرع بشكل مقارب عندما يكون الرسم البياني كثيفًا بدرجة كافية لـ |E| هو ω(|V|)، والوقت الخطي عندما |E| على الأقل |V| log |V|. للرسوم البيانية ذات الكثافة الأكبر (التي لها حواف (|V|)c على الأقل لبعض قيم c > 1)، يمكن جعل خوارزمية بريم تعمل في الوقت الخطي بشكل أكثر بساطة، باستخدام كومة <i id="mwsg">d</i>-ary بدلاً من كومة Fibonacci.
إثبات صحتها
لنفترض أن P هو رسم بياني مرجح متصل (connected, weighted graph). في كل تكرار لخوارزمية بريم، يجب إيجاد حافة تربط رأس في الرسم البياني الفرعي بالرأس خارج الرسم البياني الفرعي. نظرًا لأن P متصلة، فسيكون هناك دائمًا مسار لكل رأس. الناتج Y لخوارزمية بريم هو شجرة، لأن الحافة والرأس المضافين إلى الشجرة Y متصلان. لنفترض أن Y1 هي الحد الأدنى من الشجرة الممتدة للرسم البياني P. إذا كانت Y1 = Y فإن Y هي الحد الأدنى من الشجرة الممتدة. بخلاف ذلك، لنفرض e أول حافة مضافة أثناء بناء الشجرة Y غير الموجودة في الشجرة Y1، وتكون V هي مجموعة الرؤوس المتصلة بالحواف المضافة قبل الحافة e. ثم تكون إحدى نقاط النهاية للحافة e في المجموعة V والأخرى ليست كذلك. نظرًا لأن الشجرة Y1 هي شجرة ممتدة من الرسم البياني P، إذن يوجد مسار في الشجرة Y1 يربط بين نقطتي النهاية. عندما ينتقل المرء على طول المسار، يجب أن يواجه المرء حافة f تضم رأس في المجموعة V إلى أخرى غير موجودة في المجموعة V. الآن، عند التكرار عند إضافة الحافة e إلى الشجرة Y، يمكن أيضًا إضافة الحافة f وستتم إضافتها بدلاً من الحافة e إذا كان وزنها أقل من e، وبما أن الحافة f لم تتم إضافتها، فإننا نستنتج أن
نفرض أن الشجرة Y2 هي الرسم البياني الذي نحصل عليه عن طريق إزالة الحافة f وإضافة الحافة e إلى الشجرة Y1. من السهل إظهار أن الشجرة Y2 متصلة، ولها نفس عدد حواف الشجرة Y1، وأن إجمالي أوزان حوافها ليس أكبر من الشجرة Y1، وبالتالي فهي أيضًا شجرة ممتدة أدنى من الرسم البياني P وهي تحتوي على الحافة e وجميع الحواف المضافة قبلها أثناء إنشاء المجموعة V. كرر الخطوات المذكورة أعلاه وسنحصل في النهاية على الحد الأدنى من الشجرة الممتدة للرسم البياني P والمطابقة للشجرة Y. هذا يدل على أن Y هو الحد الأدنى من الشجرة الممتدة. يسمح الحد الأدنى للشجرة الممتدة بتوسيع المجموعة الفرعية الأولى من المنطقة الفرعية إلى مجموعة فرعية أصغر X، والتي نفترض أنها الحد الأدنى.
خوارزمية موازية
الحلقة الرئيسية لخوارزمية بريم هي بطبيعتها متسلسلة وبالتالي فهي غير قابلة للتوازي. ومع ذلك، فإن الحلقة الداخلية، التي تحدد الحافة التالية من الحد الأدنى للوزن الذي لا يشكل دورة، يمكن موازنتها بقسمة الرؤوس والحواف بين المعالجات المتاحة. يوضح السودوكود التالي هذا.يمكن تنفيذ هذه الخوارزمية بشكل عام على الأجهزة الموزعة وكذلك على أجهزة الذاكرة المشتركة. وقت التشغيل هو ، على افتراض أنه يمكن إجراء عمليات التخفيض والبث في . كما جرى استكشاف متغير من خوارزمية بريم لأجهزة الذاكرة المشتركة، حيث يجري تشغيل خوارزمية بريم المتسلسلة بالتوازي، بدءًا من الرؤوس المختلفة. ومع ذلك، تجدر الإشارة إلى وجود خوارزميات أكثر تعقيدًا لحل مشكلة الشجرة الممتدة الدنيا الموزعة بطريقة أكثر كفاءة.
انظر أيضًا
خوارزمية ديكسترا
المراجع
روابط خارجية
تقدم خوارزمية بريم على النقاط الموزعة عشوائيًا
خوارزميات مخططات
شجرة الامتداد
مقالات تحوي مقاطع فيديو
مقالات تحوي براهين