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

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 17 صور
الموسوعة الحرة
عرض توضيحي لخوارزمية بريم القائمة على المسافة الإقليدية

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

طُوِّرت هذه الخوارزمية عام 1930 على يد عالم الرياضيات التشيكي فويتش يارنيك [ 1 ] ، ثم أُعيد اكتشافها ونشرها لاحقًا على يد عالمي الحاسوب روبرت سي. بريم عام 1957 [ 2 ] وإدسكير دبليو. ديكسترا عام 1959 [ 3 ]. ولذلك، تُسمى أحيانًا خوارزمية يارنيك [ 4 ]، أو خوارزمية بريم -يارنيك [ 5 ] ، أو خوارزمية بريم -ديكسترا [ 6 ]، أو خوارزمية DJP [ 7 ] .

من بين الخوارزميات الأخرى المعروفة لحل هذه المشكلة خوارزمية كروسكال وخوارزمية بوروفكا . [ 8 ] تجد هذه الخوارزميات الغابة الممتدة الدنيا في رسم بياني قد يكون غير متصل؛ في المقابل، لا تجد أبسط أشكال خوارزمية بريم سوى الأشجار الممتدة الدنيا في الرسوم البيانية المتصلة. مع ذلك، يمكن استخدام خوارزمية بريم لإيجاد الغابة الممتدة الدنيا عند تشغيلها بشكل منفصل لكل مكون متصل من الرسم البياني. [ 9 ] من حيث تعقيدها الزمني التقاربي ، تتساوى هذه الخوارزميات الثلاث في السرعة بالنسبة للرسوم البيانية المتفرقة ، لكنها أبطأ من الخوارزميات الأخرى الأكثر تطورًا. [ 7 ] [ 6 ] مع ذلك، بالنسبة للرسوم البيانية ذات الكثافة الكافية، يمكن جعل خوارزمية بريم تعمل في زمن خطي ، مما يحقق أو يحسّن الحدود الزمنية للخوارزميات الأخرى. [ 10 ]

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

وصف

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

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

بمزيد من التفصيل، يمكن تنفيذه باتباع الشفرة الزائفة أدناه.

الدالة Prim(vertices, edges ) هي لكل رأس في vertices do أرخص تكلفة[الرأس] ← ∞ أرخص حافة[رأس] ← لا شيء تم استكشافه ← مجموعة فارغة غير مستكشف ← مجموعة تحتوي على جميع الرؤوس startVertex ← أي عنصر من عناصر الرؤوس أرخص تكلفة[رأس البداية] ← 0 طالما أن المنطقة غير المستكشفة ليست فارغة، نفّذ // تحديد الرأس في المنطقة غير المستكشفة بأقل تكلفة currentVertex ← vertex in unexplored with minimum cheapestCost[vertex] unexplored.remove(currentVertex) explored.add(currentVertex) لكل حافة (الرأس الحالي، الجار) في الحواف ، إذا كان الجار في غير مستكشف وكان وزن (الرأس الحالي، الجار) < أرخص تكلفة [الجار ] ، أرخص تكلفة[الجار] ← وزن(الرأس الحالي، الجار) cheapestEdge[neighbor] ← (currentVertex, neighbor) resultEdges ← قائمة فارغة لكل رأس في الرؤوس ، إذا كان أرخص حافة[الرأس] ≠ فارغًا ، resultEdges.append(cheapestEdge[vertex]) أعد حواف النتيجة

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

Different variations of the algorithm differ from each other in how the set Q is implemented: as a simple linked list or array of vertices, or as a more complicated priority queue data structure. This choice leads to differences in the time complexity of the algorithm. In general, a priority queue will be quicker at finding the vertex v with minimum cost, but will entail more expensive updates when the value of C[w] changes.

Time complexity

Prim's algorithm has many applications, such as in the generation of this maze, which applies Prim's algorithm to a randomly weighted grid graph.

The time complexity of Prim's algorithm depends on the data structures used for the graph and for ordering the edges by weight, which can be done using a priority queue. The following table shows the typical choices:

Minimum edge weight data structureTime complexity (total)
adjacency matrix, searchingO(|V|2){\displaystyle O(|V|^{2})}
binary heap and adjacency listO((|V|+|E|)log⁡|V|)=O(|E|log⁡|V|){\displaystyle O((|V|+|E|)\log |V|)=O(|E|\log |V|)}
Fibonacci heap and adjacency listO(|E|+|V|log⁡|V|){\displaystyle O(|E|+|V|\log |V|)}

A simple implementation of Prim's, using an adjacency matrix or an adjacency list graph representation and linearly searching an array of weights to find the minimum weight edge to add, requires O(|V|2) running time. However, this running time can be greatly improved by using heaps to implement finding minimum weight edges in the algorithm's inner loop.

A first improved version uses a heap to store all edges of the input graph, ordered by their weight. This leads to an O(|E| log |E|) worst-case running time. But storing vertices instead of edges can improve it still further. The heap should order the vertices by the smallest edge-weight that connects them to any vertex in the partially constructed minimum spanning tree (MST) (or infinity if no such edge exists). Every time a vertex v is chosen and added to the MST, a decrease-key operation is performed on all vertices w outside the partial MST such that v is connected to w, setting the key to the minimum of its previous value and the edge cost of (v,w).

باستخدام بنية بيانات كومة ثنائية بسيطة ، يمكن الآن إثبات أن خوارزمية بريم تعمل في زمن O ( | E | log | V | )، حيث | E | هو عدد الحواف و | V | هو عدد الرؤوس. وباستخدام كومة فيبوناتشي أكثر تعقيدًا ، يمكن اختزال هذا الزمن إلى O ( | E | + | V | log | V | )، وهو أسرع تقاربًا عندما يكون الرسم البياني كثيفًا بما يكفي بحيث يكون | E | يساوي ω ( | V | )، ويكون الزمن خطيًا عندما يكون |E| على الأقل يساوي |V|  log  |V|. بالنسبة للرسوم البيانية ذات الكثافة الأعلى (التي تحتوي على |V| c حافة على الأقل لبعض c  >  1)، يمكن جعل خوارزمية بريم تعمل في زمن خطي بشكل أبسط، باستخدام كومة من الرتبة d بدلًا من كومة فيبوناتشي. [ 10 ] [ 11 ]

إثبات البرهان. في هذه الحالة، يكون الرسم البياني Y 1 = Y − f + e مساويًا بالفعل لـ Y. عمومًا، قد يلزم تكرار العملية.

إثبات صحة النتائج

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

ليكن Y1 شجرة امتداد دنيا للرسم البياني P. إذا كان Y1 = Y ، فإن Y شجرة امتداد دنيا. وإلا، ليكن e أول حافة تُضاف أثناء بناء الشجرة Y ولا تنتمي إلى الشجرة Y1 ، ولتكن V مجموعة الرؤوس المتصلة بالحواف المضافة قبل الحافة e . عندئذٍ ، تقع إحدى نهايتي الحافة e في المجموعة V والأخرى لا تقع فيها. بما أن الشجرة Y1 شجرة امتداد للرسم البياني P ، يوجد مسار في الشجرة Y1 يربط بين النهايتين. أثناء السير على طول هذا المسار، لا بد من مصادفة حافة f تربط رأسًا في المجموعة V برأس آخر لا ينتمي إليها . الآن، في التكرار الذي أُضيفت فيه الحافة e إلى الشجرة Y ، كان من الممكن أيضًا إضافة الحافة f ، وكانت ستُضاف بدلًا من الحافة e إذا كان وزنها أقل من وزن e ، وبما أن الحافة f لم تُضَف، نستنتج أن

w(و)≥w(هـ).{\displaystyle w(f)\geq w(e).}

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

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

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

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

  1. قم بتعيين كل معالجPأنا{\displaystyle P_{i}}مجموعةVأنا{\displaystyle V_{i}}من الرؤوس المتتالية ذات الطول|V||P|{\displaystyle {\tfrac {|V|}{|P|}}}.
  2. أنشئ C و E و F و Q كما في الخوارزمية التسلسلية ، وقسّم C و E، بالإضافة إلى الرسم البياني، بين جميع المعالجات بحيث يحتفظ كل معالج بالحواف الواردة إلى مجموعة رؤوسه.جأنا{\displaystyle C_{i}}،هـأنا{\displaystyle E_{i}}تشير إلى أجزاء C و E المخزنة على المعالجPأنا{\displaystyle P_{i}}.
  3. كرر الخطوات التالية حتى تصبح Q فارغة:
    1. على كل معالج: ابحث عن الرأسvأنا{\displaystyle v_{i}}امتلاك القيمة الدنيا فيجأنا{\displaystyle C_{i}}[vأنا{\displaystyle v_{i}}(حل محلي).
    2. تقليل الحلول المحلية لإيجاد الرأس v الذي له أقل قيمة ممكنة لـ C [ v ] (الحل العالمي).
    3. قم ببث العقدة المحددة إلى كل معالج.
    4. أضف v إلى F ، وإذا لم تكن E [ v ] هي قيمة العلم الخاصة، فأضف أيضًا E [ v ] إلى F.
    5. على كل معالج: تحديثجأنا{\displaystyle C_{i}}وهـأنا{\displaystyle E_{i}}كما هو الحال في الخوارزمية التسلسلية.
  4. العودة F

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

انظر أيضاً

مراجع

  1. ↑ جارنيك، في. (1930)، "O jistém problému minimálním" [ حول مشكلة بسيطة معينة ] ، Práce Moravské Přírodovědecké Společnosti (باللغة التشيكية)، 6 (4): 57–63 ، hdl : 10338.dmlcz/500726.
  2. ↑ بريم، آر سي (نوفمبر 1957)، "شبكات الاتصال الأقصر وبعض التعميمات" ، مجلة بيل سيستم التقنية ، 36 (6): 1389-1401 ، رمز Bibcode : 1957BSTJ...36.1389P ، doi : 10.1002/j.1538-7305.1957.tb01515.x.
  3. ^ Dijkstra، EW (ديسمبر 1959)، “ملاحظة حول مشكلتين فيما يتعلق بالرسوم البيانية” (PDF) ، Numerische Mathematik ، 1 (1): 269–271 ، CiteSeerX 10.1.1.165.7577 ، دوى : 10.1007 / BF01386390 ، S2CID 123284777  .
  4. ↑ سيدجويك، روبرت ؛ واين، كيفن دانيال (2011)، الخوارزميات ( الطبعة الرابعة)، أديسون-ويسلي، ص 628، ISBN   978-0-321-57351-3.
  5. ↑ روزن، كينيث (2011)، الرياضيات المتقطعة وتطبيقاتها ( الطبعة السابعة)، ماكجرو هيل ساينس، ص 798  .
  6. 1 2 شيريتون، ديفيد ؛ تارجان، روبرت إندري (1976)، "إيجاد الأشجار الممتدة الدنيا"، مجلة SIAM للحوسبة ، 5 (4): 724-742 ، doi : 10.1137/0205051 ، MR 0446458 .
  7. 1 2 بيتي، سيث؛ راماتشاندران، فيجايا (يناير 2002)، "خوارزمية مثلى للشجرة الممتدة الدنيا" (ملف PDF) ، مجلة ACM ، 49 (1): 16-34 ، CiteSeerX 10.1.1.110.7670 ، doi : 10.1145/505241.505243 ، MR 2148431 ، S2CID 5362916   .
  8. ↑ تارجان، روبرت إندري (1983)، "الفصل 6. الأشجار الممتدة الدنيا. 6.2. ثلاث خوارزميات كلاسيكية"، هياكل البيانات وخوارزميات الشبكات ، سلسلة مؤتمرات CBMS-NSF الإقليمية في الرياضيات التطبيقية، المجلد 44، جمعية الرياضيات الصناعية والتطبيقية ، الصفحات 72-77  .
  9. ↑ كيبنر، جيريمي؛ جيلبرت، جون (2011)، خوارزميات الرسوم البيانية بلغة الجبر الخطي ، البرمجيات، البيئات، والأدوات، المجلد 22، جمعية الرياضيات الصناعية والتطبيقية ، ص 55، ISBN   9780898719901.
  10. 1 2 تارجان (1983) ، ص. 77.
  11. ↑ جونسون، دونالد ب. (ديسمبر 1975)، "طوابير الأولوية مع التحديث وإيجاد الأشجار الممتدة الدنيا"، رسائل معالجة المعلومات ، 4 (3): 53-57 ، doi : 10.1016/0020-0190(75)90001-0.
  12. 1 2 3 جراما، أنانث؛ غوبتا، أنشول؛ كاريبيس، جورج؛ كومار ، فيبين (2003)، مقدمة للحوسبة المتوازية ، أديسون ويسلي، الصفحات من 444 إلى 446، ISBN  978-0201648652
  13. ^ كوين ، مايكل ج. ديو، نارسينغ (1984)، “خوارزميات الرسم البياني المتوازي”، مسوحات الحوسبة ACM ، 16 (3): 319–348 ، دوى : 10.1145/2514.2515 ، S2CID 6833839 
  14. ↑ سيتيا، روهيت (2009)، "خوارزمية متوازية جديدة لمسألة الشجرة الممتدة الدنيا" (PDF) ، وقائع المؤتمر الدولي للحوسبة عالية الأداء (HiPC)