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

عرض توضيحي لخوارزمية بريم على أساس المسافة الإقليدية

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

تبدأ خوارزمية Prim التي تبدأ من الرأس A. في الخطوة الثالثة، يكون للحواف BD وAB وزن 2، لذلك يجري اختيار BD بشكل عشوائي. بعد هذه الخطوة، لم يعد AB مرشحًا للإضافة إلى الشجرة لأنه يربط عقدتين موجودتين بالفعل في الشجرة.

الوصف

يمكن وصف الخوارزمية بشكل غير رسمي بأنها تؤدي الخطوات التالية:

1. اختر رأسًا عشوائية من الرسم لتبدأ بها الشجرة.
2. وسع الشجرة بإضافة حافة: من الحواف التي تربط الشجرة برؤوس ليست ضمن الشجرة، أوجد الحافة ذات أقل وزن، وضمها إلى الشجرة.
3. كرر الخطوة الثانية (إلى أن تضم كل الرؤوس إلى الشجرة).

بمزيد من التفصيل، يمكن تنفيذها باتباع السودوكود أدناه.

1. نُحدد لكل رأس v في الرسم رقمًا C[v] (يمثل أقل تكلفة للربط مع v) وحافة E[v] (الحافة التي تُعطي أقل ربط تكلفةً). للبدء بقيم ابتدائية لهذه الأرقام، اجعل قيمة C[v] تساوي +∞ (أو أي رقم أكبر من وزن أكبر حافة) وخصص لـ E[v] قيمة خاصة en:flag value لتوضيح أنه ليس هناك حافة تربط v بأي من الرؤوس سابقة.
2. إبدأ بمجموعة فارغة "غابة" forest F ومجموعة أخرى Q تضم الرؤوس التي لا تنتمي إلى المجموعة F (في البداية ستحتوي Q على كل الرؤوس).
3. كرر الخطوات التالية إلى أن تصبح المجموعة Q فارغة:
   1. اختر رأس v من Q والتي لها أقل قيمة C[v]
   2. ثم قم بإضافة v إلى F وحذفها من Q
   3. كرر لكل الحواف vw التي تربط v برأس أخرى w. لكل حافة، إذا كانت w تنتمي إلى Q وكانت الحافة vw لها وزن أقل من C[w]، نفذ الخطوات التالية:
      1. اجعل C[w] تساوي تكلفة الحافة vw
      2. اجعل E[w] تشير إلى vw.
4. حدد المجموعة F

كما هو موضح أعلاه، سيجري اختيار رأس البداية للخوارزمية بشكل عشوائي، لأن التكرار الأول للحلقة الرئيسية للخوارزمية سيكون له مجموعة من الرؤوس في Q التي لها أوزان متساوية، وستبدأ الخوارزمية تلقائيًا في شجرة جديدة في F عندما تكمل شجرة ممتدة لكل مكون متصل من الرسم البياني. يمكن تعديل الخوارزمية لتبدأ بأي رأس معين من خلال ضبط C[s] ليكون رقمًا أصغر من القيم الأخرى لـ C (على سبيل المثال، صفر)، ويمكن تعديله للعثور على شجرة ممتدة واحدة فقط بدلاً من غابة ممتدة بالكامل (تطابق الوصف غير الرسمي بشكل أوثق) عن طريق التوقف متى واجهت رأس أخرى قد وُضع علامة عليها على أنها لا تحتوي على حافة مرتبطة.

تختلف الصور المختلفة للخوارزمية عن بعضها البعض في كيفية تنفيذ المجموعة Q : كقائمة مرتبطة بسيطة أو مصفوفة من الرؤوس، أو كهيكل بيانات طابور أولوية أكثر تعقيدًا. يؤدي هذا الاختيار إلى اختلافات في التعقيد الزمني للخوارزمية. بشكل عام، ستكون قائمة الانتظار ذات الأولوية أسرع في العثور على قمة الرأس v بأقل تكلفة، ولكنها ستستلزم تحديثات أكثر تكلفة عندما تتغير قيمة C[w].

تعقيد الوقت

يعتمد التعقيد الزمني لخوارزمية بريم على هياكل البيانات المستخدمة للرسم البياني ولترتيب الحواف بالوزن، وهو ما يمكن القيام به باستخدام قائمة انتظار ذات أولوية. يوضح الجدول التالي الخيارات النموذجية:

الحد الأدنى لهيكل بيانات وزن الحافة	تعقيد الوقت (الإجمالي)
مصفوفة الجوار، البحث	$O(|V|^{2})$
الكومة الثنائية والقائمة المجاورة	$O((|V|+|E|)\log |V|)=O(|E|\log |V|)$
قائمة الكومة والجوار في فيبوناتشي	$O(|E|+|V|\log |V|)$

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

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

إظهار الإثبات. في هذه الحالة، الرسم البياني Y₁= Y - f + e يساوي Y بالفعل. بشكل عام، قد تحتاج العملية إلى التكرار.

إثبات صحتها

لنفترض أن P هو رسم بياني مرجح متصل (connected, weighted graph). في كل تكرار لخوارزمية بريم، يجب إيجاد حافة تربط رأس في الرسم البياني الفرعي بالرأس خارج الرسم البياني الفرعي. نظرًا لأن P متصلة، فسيكون هناك دائمًا مسار لكل رأس. الناتج Y لخوارزمية بريم هو شجرة، لأن الحافة والرأس المضافين إلى الشجرة Y متصلان. لنفترض أن Y₁ هي الحد الأدنى من الشجرة الممتدة للرسم البياني P. إذا كانت Y₁ = Y فإن Y هي الحد الأدنى من الشجرة الممتدة. بخلاف ذلك، لنفرض e أول حافة مضافة أثناء بناء الشجرة Y غير الموجودة في الشجرة Y₁، وتكون V هي مجموعة الرؤوس المتصلة بالحواف المضافة قبل الحافة e. ثم تكون إحدى نقاط النهاية للحافة e في المجموعة V والأخرى ليست كذلك. نظرًا لأن الشجرة Y₁ هي شجرة ممتدة من الرسم البياني P، إذن يوجد مسار في الشجرة Y₁ يربط بين نقطتي النهاية. عندما ينتقل المرء على طول المسار، يجب أن يواجه المرء حافة f تضم رأس في المجموعة V إلى أخرى غير موجودة في المجموعة V. الآن، عند التكرار عند إضافة الحافة e إلى الشجرة Y، يمكن أيضًا إضافة الحافة f وستتم إضافتها بدلاً من الحافة e إذا كان وزنها أقل من e، وبما أن الحافة f لم تتم إضافتها، فإننا نستنتج أن

$w(f)\geq w(e).$

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

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

مصفوفة التقارب موزعة بين معالجات متعددة لخوارزمية Prim الموازية. في كل تكرار للخوارزمية، يقوم كل معالج بتحديث الجزء الخاص به من C عن طريق فحص صف الرأس المُدرج حديثًا في مجموعة الأعمدة الخاصة به في المصفوفة المجاورة. يتم بعد ذلك جمع النتائج واختيار الرأس التالي الذي سيتم تضمينه في MST بشكل عام.

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

1. Assign each processors $P_{i}$ a set $V_{i}$ of consecutive vertices of length ${\tfrac {|V|}{|P|}}$.
2. Create C, E, F, and Q as in the sequential algorithm and divide C, E, as well as the graph between all processors such that each processor holds the incoming edges to its set of vertices. Let $C_{i}$, $E_{i}$ denote the parts of C, E stored on processor $P_{i}$.
3. Repeat the following steps until Q is empty:
   1. On every processor: find the vertex $v_{i}$ having the minimum value in $C_{i}$[$v_{i}$] (local solution).
   2. Min-reduce the local solutions to find the vertex v having the minimum possible value of C[v] (global solution).
   3. بث عام the selected node to every processor.
   4. Add v to F and, if E[v] is not the special flag value, also add E[v] to F.
   5. On every processor: update $C_{i}$ and $E_{i}$ as in the sequential algorithm.
4. Return F

يمكن تنفيذ هذه الخوارزمية بشكل عام على الأجهزة الموزعة وكذلك على أجهزة الذاكرة المشتركة. وقت التشغيل هو $O({\tfrac {|V|^{2}}{|P|}})+O(|V|\log |P|)$، على افتراض أنه يمكن إجراء عمليات التخفيض والبث في $O(\log |P|)$. كما جرى استكشاف متغير من خوارزمية بريم لأجهزة الذاكرة المشتركة، حيث يجري تشغيل خوارزمية بريم المتسلسلة بالتوازي، بدءًا من الرؤوس المختلفة. ومع ذلك، تجدر الإشارة إلى وجود خوارزميات أكثر تعقيدًا لحل مشكلة الشجرة الممتدة الدنيا الموزعة بطريقة أكثر كفاءة.

انظر أيضًا

• خوارزمية ديكسترا

روابط خارجية

• تقدم خوارزمية بريم على النقاط الموزعة عشوائيًا