في بداية القرن التاسع عشر ، قام جيوبر شتاينر بعمل مقياس جيولوجي من برلينتحديد مهمة كيفية ربط القرى الثلاث بحيث يكون طولها أقصر. بعد ذلك ، قام بتعميم هذه المشكلة: من الضروري العثور على نقطة على متن الطائرة بحيث تكون المسافة منها إلى النقاط الأخرى هي الأصغر. في القرن العشرين ، استمر العمل في هذا الموضوع. تقرر اتخاذ عدة نقاط وربطها بطريقة كانت المسافة بينها أقصر. كل هذا هو حالة خاصة من المشكلة قيد الدراسة.
خوارزميات الجشع
تنتمي خوارزمية Kraskal إلى خوارزميات "الجشع"(يطلق عليهم أيضا تدرج). جوهر تلك - أكبر مكسب في كل خطوة. لا توفر خوارزميات "الجشع" دائمًا أفضل حل للمشكلة. هناك نظرية تظهر أنه عند تطبيقها على مهام محددة ، فإنها توفر الحل الأمثل. هذه هي نظرية matroids. تشير خوارزمية Kraskal إلى مثل هذه المشاكل.
إيجاد إطار الوزن الأدنى
الخوارزمية المدروسة تبني الأفضلرسم بياني للإطار السلكي. المشكلة في ذلك على النحو التالي. يتم إعطاؤك رسمًا بيانيًا غير موجه بدون حواف وحلقات متعددة ، وعلى مجموعة حوافها ، يتم إعطاء دالة وزن w ، والتي تعين لكل حافة e رقمًا - وزن الحافة - w (e). يتم تحديد وزن كل مجموعة فرعية من مجموعة الحواف من خلال مجموع أوزان حوافها. مطلوب العثور على إطار أصغر وزن.
وصف
تعمل خوارزمية Kruskal على هذا النحو. أولاً ، تم ترتيب جميع حواف الرسم البياني الأصلي بترتيب تصاعدي للأوزان. في البداية ، لا يحتوي الهيكل العظمي على أي حواف ، ولكنه يشمل جميع رؤوس الرسم البياني. بعد الخطوة التالية من الخوارزمية ، تتم إضافة حافة واحدة إلى الجزء المشيد بالفعل من الهيكل العظمي ، وهو غابة ممتدة. لم يتم اختياره بشكل عشوائي. يمكن تسمية جميع حواف الرسم البياني التي لا تنتمي إلى الإطار السلكي باللون الأحمر والأخضر. توجد رؤوس كل حافة حمراء في مكون واحد متصل من الغابة قيد الإنشاء ، ورؤوس الحافة الخضراء في مكونات مختلفة. لذلك ، إذا أضفنا حافة حمراء هناك ، فستظهر دورة ، وإذا كانت خضراء ، فإن مكون الاتصال في الغابة الذي تم الحصول عليه بعد هذه الخطوة سيكون واحدًا أقل. وبالتالي ، لا يمكن إضافة حافة حمراء إلى البناء الناتج ، ولكن يمكن إضافة أي حافة خضراء لإنشاء غابة. ويتم إضافة حافة خضراء بأقل وزن. والنتيجة هي أخف إطار.
تطبيق
دعونا نشير إلى الغابة الحالية F. إنه يقسم مجموعة رؤوس الرسم البياني إلى مناطق اتصال (أشكال اتحادهم F ، ولا تتقاطع في أزواج). تحتوي الحواف الحمراء على كلا الرأسين في نفس الجزء. الجزء (x) هو دالة ترجع ، لكل رأس x ، اسم الجزء الذي ينتمي إليه x. Unite (x، y) هو إجراء يقوم ببناء قسم جديد يتكون من اتحاد الجزأين x و y وجميع الأجزاء الأخرى. لنفترض أن n هو عدد الحواف في الرسم البياني. تم تضمين كل هذه المفاهيم في خوارزمية Kruskal. التنفيذ:
قم بترتيب جميع حواف الرسم البياني من الأول إلى التاسع بترتيب تصاعدي للأوزان. (ai ، bi هي رؤوس الحافة مرقمة).
بالنسبة لـ i = 1 to n do.
x: = الجزء (ai).
ص: = الجزء (ثنائي).
إذا كانت x لا تساوي y فإن Unite (x، y) ، قم بتضمين الحافة i في F.
الصواب
دع T هو الهيكل العظمي للرسم البياني الأصلي الذي تم إنشاؤه باستخدام خوارزمية Kruskal ، ويكون S هو الهيكل العظمي التعسفي. نحتاج إلى إثبات أن w (T) لا يتجاوز w (S).
دع M هي مجموعة الحواف S ، P هي مجموعة الحوافإذا كانت S لا تساوي T ، فهناك حافة وإطار T لا ينتمي إلى S. نعلق وآخر لـ S. تتشكل دورة ، دعنا نسميها C. نزيل من C أي حافة تنتمي إلى S. نحصل على إطار جديد ، لأن الحواف ، وهناك العديد من القمم فيه. لا يتجاوز وزنه w (S) ، لأن w (et) هو على الأكثر w (es) بحكم خوارزمية Kruskal. سنكرر هذه العملية (استبدال الحواف S بالحواف T) حتى نحصل على T. وزن كل إطار ناتج لاحق ليس أكبر من وزن الإطار السابق ، ومن هنا يتبع ذلك w (T) ليس أكبر من w (S).
أيضًا ، فإن صحة خوارزمية Kruskal تتبع نظرية Rado-Edmonds في matroids.
أمثلة على استخدام خوارزمية Kruskal
إعطاء رسم بياني بالرؤوس أ ، ب ، ج ، د ، هـ والحواف (أ ،ب) ، (أ ، هـ) ، (ب ، ج) ، (ب ، هـ) ، (ج ، د) ، (ج ، هـ) ، (د ، هـ). أوزان الضلع موضحة في الجدول والشكل. في البداية ، تحتوي الغابة F قيد الإنشاء على جميع رؤوس الرسم البياني ولا تحتوي على أي حواف. تضيف خوارزمية Kruskal أولاً حافة (a ، e) ، نظرًا لأنها تحتوي على أصغر وزن ، والرؤوس a و e في مكونات متصلة مختلفة للغابة F (الحافة (a ، e) خضراء) ، ثم الحافة (c ، d) ، لذلك أن هذه الحافة لها أقل وزن لحواف الرسم البياني التي لا تنتمي إلى F ، وأنها خضراء ، ثم تتم إضافة الحافة (أ ، ب) لنفس الأسباب. لكن تم تخطي الحافة (ب ، هـ) ، على الرغم من أنها تحتوي على أصغر وزن للحواف المتبقية ، لأنها حمراء: تنتمي الرؤوس b و e إلى نفس المكون المتصل من الغابة F ، أي إذا أضفنا الحافة (b ، e) إلى F ، دورة. ثم يتم إضافة حافة خضراء (ب ، ج) ، ويتم تخطي حافة حمراء (ج ، هـ) ، ثم د ، هـ. وهكذا ، تتم إضافة الحواف (أ ، هـ) ، (ج ، د) ، (أ ، ب) ، (ب ، ج) بالتتابع. يتكون الهيكل الأمثل للرسم البياني الأولي منهم. هذه هي الطريقة التي تعمل بها الخوارزمية في هذه الحالة رسم. وقد أظهر هذا مثال.
يوضح الشكل رسمًا بيانيًا يتكون من مكونين متصلين. تُظهر الخطوط الغامقة حواف الهيكل العظمي الأمثل (الأخضر) ، المبني باستخدام خوارزمية Kruskal.
يوضح الشكل العلوي الرسم البياني الأصلي ، بينما يوضح الشكل السفلي الحد الأدنى للوزن الهيكل العظمي المصمم له باستخدام الخوارزمية المدروسة.
تسلسل الحواف المضافة: (1،6) ؛ (0.3) أو (2.6) أو (2.6) أو (0.3) - لا يهم ؛ (3.4) ؛ (0.1) أو (1.6) أو (1.6) أو (0.1) غير مبال أيضًا (5.6).
تجد خوارزمية Kruskal تطبيقًا عمليًا ، على سبيل المثال ، لتحسين وضع الاتصالات والطرق في الأحياء الجديدة للمستوطنات في كل بلد ، وكذلك في حالات أخرى.
