- بريم: خوارزمية للحصول على الشجرة الممتدة الدنيا (MST) في الرسوم البيانية المتصلة وغير الموجهة والموزونة، وتقليل مجموع أوزان الحواف.
- العملية: تبدأ من عقدة وتوسع الشجرة عن طريق اختيار الحافة ذات الوزن الأدنى التي تربط العقد المعالجة بالعقد غير المعالجة بشكل متكرر، مما يتجنب الحلقات.
- التعقيد: O(n²) مع مصفوفة التجاور أو O(a log n) مع الأكوام؛ عادة ما يكون Prim أفضل على الرسوم البيانية الكثيفة من Kruskal.
- التطبيقات: تصميم الشبكات، والأنظمة الكهربائية، وتوزيع المياه/الغاز، والرؤية الآلية والمعلوماتية الحيوية، وتحسين التكاليف والموارد.
تُعدّ خوارزمية بريم من أشهر الطرق لحلّ مشكلة الشجرة الممتدة الدنيا (MST). يظهر هذا النوع من المشاكل في العديد من المجالات، مثل تصميم شبكات الاتصالات ، والأنظمة الكهربائية ، وشبكات التوزيع. إذا كنت مهتمًا بفهم آلية عمل هذه الخوارزمية بعمق، فأنت في المكان الصحيح. سنشرح هنا كل ما يتعلق بخوارزمية بريم، بدءًا من تاريخها وصولًا إلى تطبيقها التقني وتطبيقاتها العملية.
على الرغم من أن الخوارزمية طُوّرت في الأصل عام ١٩٥٧ على يد روبرت بريم ، إلا أن أهميتها لم تتضاءل بمرور الوقت. فهي خوارزمية أساسية في تحليل الرسوم البيانية، لا سيما عند البحث عن حل فعال لربط جميع عُقد الرسم البياني بأقل تكلفة ممكنة. علاوة على ذلك، فإن سهولة تطبيقها تجعلها مثالية لتعلم تقنيات تحسين الرسوم البيانية في دليلنا الشامل للمبرمجين.
ما هي خوارزمية بريم؟
خوارزمية بريم هي تقنية لإيجاد الشجرة الممتدة الدنيا (MST) لرسم بياني متصل وغير موجه وموزون. الشجرة الممتدة الدنيا هي شجرة تربط جميع عقد الرسم البياني باستخدام أصغر مجموع ممكن لأوزان الحواف . تُعد هذه المسألة بالغة الأهمية في مجالات مثل تحسين الشبكات، حيث تساعد في تقليل استخدام الموارد مثل الكابلات والأنابيب ، وحتى مسارات النقل.
تعتمد الفكرة الرئيسية للخوارزمية على تقسيم عقد الرسم البياني إلى مجموعتين: معالجة وغير معالجة . ثم يتم اختيار أقصر حافة تربط المجموعتين بشكل متكرر، مع ضمان عدم تشكل أي دورات. في النهاية، تشكل مجموعة الحواف المختارة الشجرة الممتدة الدنيا للرسم البياني.
التاريخ والسياق
طوّر روبرت بريم هذه الخوارزمية عام 1957، لكن أصولها تعود إلى ما هو أبعد من ذلك، إلى عام 1926، عندما عمل أوتاكار بوروفكا على مشكلة كهربة تشيكوسلوفاكيا. وفي عام 1956 أيضًا، قدّم جوزيف كروسكال طريقته الخاصة لحلّ مشكلة الشجرة الممتدة الدنيا. ورغم أن كلتا الخوارزميتين تحلان المشكلة نفسها، إلا أن خوارزمية بريم فعّالة بشكل خاص مع الرسوم البيانية الكثيفة.
خلال الستينيات والسبعينيات من القرن العشرين، تمت دراسة الخوارزمية وتحسينها من قبل علماء الرياضيات في مختبرات بيل ، الذين ساهموا في تطوير تقنيات متقدمة لمشاكل التحسين التوافقي.
عملية الخوارزمية
تبدأ الخوارزمية باختيار أي عقدة أولية في الرسم البياني وإضافة حوافها إلى مجموعة الاتصالات الممكنة. ثم، في كل خطوة:
- تم الاختيار أقصر حافة الذي يربط عقدة تمت معالجتها بالفعل بأخرى غير معالجة.
- يتم وضع علامة على العقدة غير المعالجة المتصلة بالحافة المحددة على أنها معالجة.
- تستمر العملية حتى تتم معالجة كافة العقد.
تشكل المجموعة الأخيرة من الحواف الشجرة الممتدة الدنيا، المرتبطة بطرق أخرى مثل خوارزمية ويلسون.
التعقيد والمقارنة مع كروسكال
تُعد كفاءة خوارزمية بريم من أكثر الجوانب التي دُرست . في رسم بياني يحتوي على n عقدة و a حافة، يمكن أن يختلف تعقيدها تبعًا للتنفيذ:
- استخدام مصفوفة التجاور: س (ن²)
- استخدام التلال: O(a log n)
بالمقارنة، تبلغ تعقيد خوارزمية كروسكال O(a log n) ، مع العلم أن هذا يعتمد على أسلوب الفرز المستخدم. تُعد خوارزمية بريم أكثر كفاءة بشكل عام للرسوم البيانية الكثيفة، بينما تُفضل خوارزمية كروسكال للرسوم البيانية المتفرقة.
كود زائف للخوارزمية
إحدى الطرق الواضحة لفهم الخوارزمية هي من خلال شفرتها الزائفة وأمثلة على الخوارزميات الرياضية :
Prim (رسم بياني): ابدأ المجموعة المعالجة بعقدة أولية في حين وجود عقد غير معالجة: ابحث عن أقصر حافة تربط بين المجموعتين أضف الحافة إلى MST وضع علامة على العقدة على أنها معالجة أعد MST
تطبيقات عملية
تُستخدم خوارزمية بريم في العديد من التطبيقات العملية، بما في ذلك:
- تصميم شبكات الاتصالات:تحديد الطريقة الأكثر كفاءة لتوصيل شبكة من الخوادم أو المحطات الأساسية.
- أنظمة كهربائية:تقليل تكلفة الأسلاك في التركيبات الكهربائية.
- توزيع المياه أو الغاز:تحسين البنية التحتية لخطوط الأنابيب.
على سبيل المثال، تستطيع شركة تلفزيون الكابل استخدام هذه الخوارزمية لتقليل طول الكابلات اللازمة لتوصيل جميع العملاء في منطقة سكنية.
وقد تم استخدامه أيضًا في مجالات أكثر تعقيدًا، مثل تحليل الصور في رؤية الكمبيوتر ، وطَيّ البروتين في المعلوماتية الحيوية، والأساليب المتبعة في حل المشكلات الصعبة من نوع NP مثل مشكلة البائع المتجول.
بفضل تنوعها وقابليتها للتكيف ، تظل خوارزمية بريم أداة أساسية في تحسين المشكلات المتعلقة بالرسوم البيانية.