بنية بيانات المجموعة المنفصلة

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 46 صور
الموسوعة الحرة

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

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

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

تاريخ

وُصفت غابات المجموعات المنفصلة لأول مرة من قِبل برنارد أ. غالر ومايكل ج. فيشر في عام 1964. [ 2 ] وفي عام 1973، تم تحديد تعقيدها الزمني بـيا(سجل*⁡(ن)){\displaystyle O(\log ^{*}(n))}، اللوغاريتم المتكرر لـن{\displaystyle n}، من تأليف هوبكروفت وأولمان. [ 3 ] في عام 1975 ، كان روبرت تارجان أول من أثبتيا(مα(ن)){\displaystyle O(m\alpha (n))}( دالة أكرمان العكسية ) حدٌّ أعلى لتعقيد الوقت للخوارزمية. [ 4 ] كما أثبت أيضًا أنه دقيق. في عام 1979، أظهر أن هذا كان الحد الأدنى لفئة معينة من الخوارزميات، وهي خوارزميات المؤشر ، التي تتضمن بنية غالر-فيشر. [ 5 ] في عام 1989، أظهر فريدمان وساكس أنΩ(α(ن)){\displaystyle \Omega (\alpha (n))}(مستهلكة) كلمات منيا(سجل⁡ن){\displaystyle O(\log n)}يجب الوصول إلى البتات بواسطة أي بنية بيانات منفصلة لكل عملية، [ 6 ] مما يثبت مثالية بنية البيانات في هذا النموذج.

في عام 1991، نشر جاليل وإيتاليانو دراسة استقصائية عن هياكل البيانات للمجموعات المنفصلة. [ 7 ]

في عام 1994، وصف ريتشارد ج. أندرسون وهيذر وول نسخة متوازية من خوارزمية الاتحاد والبحث لا تحتاج أبدًا إلى الحظر. [ 8 ]

في عام ٢٠٠٧، طوّر سيلفان كونشون وجان كريستوف فيلياتر نسخة شبه دائمة من بنية بيانات غابة المجموعات المنفصلة، ​​وقاما بتوثيق صحتها باستخدام مساعد البرهان روك (الذي كان يُعرف آنذاك باسم كوك ). [ ٩ ] تعني "شبه دائمة" الاحتفاظ بالإصدارات السابقة من البنية بكفاءة، ولكن الوصول إلى الإصدارات السابقة يُبطل الإصدارات اللاحقة. يحقق تطبيقهم الأسرع أداءً يكاد يُضاهي كفاءة الخوارزمية غير الدائمة. ولم يُجروا تحليلًا للتعقيد.

تم أيضًا دراسة أنواع مختلفة من هياكل بيانات المجموعات المنفصلة ذات أداء أفضل في فئة محدودة من المسائل. وقد أظهر جابو وتارجان أنه إذا تم تقييد الاتحادات الممكنة بطرق معينة، فإنه من الممكن الحصول على خوارزمية خطية تمامًا. [ 10 ] على وجه الخصوص، يمكن تحقيق زمن خطي إذا تم تحديد "شجرة الاتحاد" مسبقًا. هذه الشجرة تشمل جميع عناصر المجموعات. لنفترض أن p[ v ] يمثل الأصل في الشجرة، عندئذٍ يُفترض أن عمليات الاتحاد يجب أن تكون على شكل union ( v , p[ v ]) لبعض v .

التمثيل

في هذا القسم والقسم التالي، نصف أكثر تطبيقات بنية بيانات المجموعة المنفصلة شيوعاً، وهي عبارة عن غابة من أشجار مؤشر الأصل . يُعرف هذا التمثيل باسم أشجار غالر-فيشر .

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

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

العمليات

تدعم هياكل بيانات المجموعات المنفصلة ثلاث عمليات: إنشاء مجموعة جديدة تحتوي على عنصر جديد؛ إيجاد العنصر الممثل للمجموعة التي تحتوي على عنصر معين؛ ودمج مجموعتين.

صنع مجموعات جديدة

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

في غابة المجموعات المنفصلة، MakeSet​​تُهيئ الدالة مؤشر الأصل للعقدة وحجمها أو رتبتها. إذا مُثِّل الجذر بعقدة تُشير إلى نفسها، فيمكن وصف إضافة عنصر باستخدام الشفرة الزائفة التالية :

دالة MakeSet( x ) هي: إذا لم يكن x موجودًا بالفعل في الغابة، فإن x.parent := x، و x.size := 1 (إذا كانت العقد تخزن الحجم) ، و x.rank := 0 (إذا كانت العقد تخزن الرتبة) . نهاية الشرط . نهاية الدالة.

تتميز هذه العملية بتعقيد زمني خطي. وعلى وجه الخصوص، تتطلب تهيئة غابة ذات مجموعات منفصلة تحتوي على n عقدة زمنًا قدره O ( n ) .

يشير عدم وجود عقدة أصلية معينة للعقدة إلى أن العقدة غير موجودة في الغابة.

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

إيجاد ممثلي المجموعة

تتبع العملية Findسلسلة مؤشرات الأصل من عقدة استعلام محددة x حتى تصل إلى عنصر جذر. يمثل عنصر الجذر هذا المجموعة التي تنتمي إليها x، وقد يكون x نفسه. Findتُرجع العملية عنصر الجذر الذي تصل إليه.

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

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

دالة Find( x ) هي: إذا كان x.parent ≠ x، فإن x.parent := Find( x.parent ) تُرجع x.parent ، وإلا تُرجع x. نهاية الشرط. نهاية الدالة.

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

دالة Find( x ) هي root : = x بينما root.parent ≠ root do root := root.parent end whileبينما x.parent ≠ root، اجعل parent := x.parent ، ثم اجعل x.parent := root، ثم اجعل x := parent .إرجاع الجذر نهاية الدالة

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

دالة Find( x ) هي: بينما x.parent ≠ x، نفّذ ما يلي: ( x , x.parent ) := ( x.parent , x.parent.parent ) نهاية الحلقة، أرجع x نهاية الدالة

يعمل تقسيم المسار إلى النصف بشكل مشابه، ولكنه يستبدل فقط كل مؤشر أب آخر:

دالة Find( x ) هي: بينما x.parent ≠ x، قم بما يلي : x.parent := x.parent.parent ، x := x.parent، نهاية الحلقة، أرجع x. نهاية الدالة.

دمج مجموعتين

MakeSetيُنشئ 8 كائنات فردية.
بعد إجراء بعض العمليات Union، يتم تجميع بعض المجموعات معًا.

تستبدل هذه العملية المجموعة التي تحتوي على x والمجموعة التي تحتوي على y باتحادهما. يُستخدم أولاً لتحديد جذور الشجرتين اللتين تحتويان على x و y . إذا كانت الجذور متطابقة، فلا داعي للقيام بأي شيء آخر. وإلا، يجب دمج الشجرتين. يتم ذلك إما بتعيين مؤشر الأصل لجذر x إلى جذر y ، أو بتعيين مؤشر الأصل لجذر y إلى جذر x .Union(x, y)UnionFind

يؤثر اختيار العقدة التي تصبح العقدة الأب على تعقيد العمليات اللاحقة على الشجرة. فإذا تم ذلك بإهمال، قد تصبح الأشجار طويلة بشكل مفرط. على سبيل المثال، لنفترض أننا Unionنجعل دائمًا الشجرة التي تحتوي على x شجرة فرعية من الشجرة التي تحتوي على y . لنبدأ بغابة تم تهيئتها للتو بعناصر1،2،3،...،ن،{\displaystyle 1,2,3,\ldots ,n,}ثم يتم Union(1, 2)تنفيذ Union(2, 3)... ، ...​​​​​​​​Union(n - 1, n)Find(1)

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

الاتحاد حسب الحجم

في حالة دمج العقد حسب الحجم، يُخزَّن حجم العقدة، وهو ببساطة عدد فروعها (بما في ذلك العقدة نفسها). عند دمج الشجرتين ذواتي الجذرين x و y ، تصبح العقدة ذات الفروع الأكثر هي العقدة الأب. إذا كان للعقدتين نفس عدد الفروع، فيمكن لأي منهما أن تصبح العقدة الأب. في كلتا الحالتين، يُحدَّد حجم العقدة الأب الجديدة بعدد فروعها الإجمالي الجديد.

دالة الاتحاد ( س ، ص ) هي // استبدال العقد بالجذور س := البحث عن ( س ) ص := البحث عن ( ص ) إذا كان x = y ، فأرجع // x و y موجودان بالفعل في نفس المجموعة .// إذا لزم الأمر، قم بتبديل المتغيرات لضمان أن // يكون لـ x عدد من الأبناء على الأقل مساويًا لعدد أبناء y إذا كان حجم x < حجم y ، فإن ( x , y ) := ( y , x ) نهاية إذا// اجعل x الجذر الجديد y.parent := x // حدّث حجم x x.size := x.size + y.size end function

من الواضح أن عدد البتات اللازمة لتخزين الحجم هو نفسه عدد البتات اللازمة لتخزين n . وهذا يضيف عاملاً ثابتاً إلى مساحة التخزين المطلوبة للغابة.

الاتحاد حسب الرتبة

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

دالة الاتحاد ( س ، ص ) هي // استبدال العقد بالجذور س := البحث عن ( س ) ص := البحث عن ( ص ) إذا كان x = y ، فأرجع // x و y موجودان بالفعل في نفس المجموعة .// إذا لزم الأمر، أعد تسمية المتغيرات لضمان أن // رتبة x لا تقل عن رتبة y إذا كانت رتبة x أقل من رتبة y ، فإن ( x , y ) := ( y , x ) نهاية إذا// اجعل x الجذر الجديد y.parent := x // إذا لزم الأمر، قم بزيادة رتبة x إذا كانت x.rank = y.rank ثم x.rank : = x.rank + 1 end if end function

يمكن إثبات أن لكل عقدة رتبة⌊سجل⁡ن⌋{\displaystyle \lfloor \log n\rfloor }أو أقل. [ 11 ] وبالتالي، يمكن تخزين كل رتبة في O (log log n ) بت، ويمكن تخزين جميع الرتب في O ( n log log n ) بت. وهذا يجعل الرتب جزءًا ضئيلاً للغاية من حجم الغابة.

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

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

تعقيد الخطة

A disjoint-set forest implementation in which Find does not update parent pointers, and in which Union does not attempt to control tree heights, can have trees with height O(n). In such a situation, the Find and Union operations require O(n) time.

If an implementation uses path compression alone, then a sequence of nMakeSet operations, followed by up to n − 1Union operations and fFind operations, has a worst-case running time of Θ(n+f⋅(1+log2+f/n⁡n)){\displaystyle \Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))}.[11]

Using union by rank, but without updating parent pointers during Find, gives a running time of Θ(mlog⁡n){\displaystyle \Theta (m\log n)} for m operations of any type, up to n of which are MakeSet operations.[11]

The combination of path compression, splitting, or halving, with union by size or by rank, reduces the running time for m operations of any type, up to n of which are MakeSet operations, to Θ(mα(n)){\displaystyle \Theta (m\alpha (n))}.[4][5] This makes the amortized running time of each operation Θ(α(n)){\displaystyle \Theta (\alpha (n))}. This is asymptotically optimal, meaning that every disjoint set data structure must use Ω(α(n)){\displaystyle \Omega (\alpha (n))} amortized time per operation.[6] Here, the function α(n){\displaystyle \alpha (n)} is the inverse Ackermann function. The inverse Ackermann function grows extraordinarily slowly, so this factor is 4 or less for any n that can actually be written in the physical universe. This makes disjoint-set operations practically amortized constant time.

Proof of O(m log* n) time complexity of Union-Find

The precise analysis of the performance of a disjoint-set forest is somewhat intricate. However, there is a much simpler analysis that proves that the amortized time for any mFind or Union operations on a disjoint-set forest containing n objects is O(m log*n), where log* denotes the iterated logarithm.[12][13][14][15]

Lemma 1: As the find function follows the path along to the root, the rank of node it encounters is increasing.

Proof

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

اللمة 2: العقدة u التي هي جذر شجرة فرعية ذات رتبة r لها على الأقل2ر{\displaystyle 2^{r}}العقد.

دليل

في البداية، عندما تكون كل عقدة جذرًا لشجرتها الخاصة، يكون هذا صحيحًا بشكل بديهي. لنفترض أن عقدة u ذات رتبة r تحتوي على 2r عقدة على الأقل . عندئذٍ، عند دمج شجرتين من الرتبة r باستخدام عملية الاتحاد حسب الرتبة ، ينتج عن ذلك شجرة ذات رتبة r + 1 ، جذرها يحتوي على r عقدة على الأقل2ر+2ر=2ر+1{\displaystyle 2^{r}+2^{r}=2^{r+1}}العقد.

اللمة 3: الحد الأقصى لعدد العقد من الرتبة r هو على الأكثرن2ر.{\displaystyle {\frac {n}{2^{r}}}.}

دليل

من اللمة 2 ، نعلم أن العقدة u التي هي جذر شجرة فرعية ذات رتبة r لديها على الأقل2ر{\displaystyle 2^{r}}العقد. سنحصل على أكبر عدد من العقد ذات الرتبة r عندما تكون كل عقدة ذات رتبة r هي جذر شجرة تحتوي بالضبط على2ر{\displaystyle 2^{r}}العقد. في هذه الحالة، يكون عدد العقد ذات الرتبة r هون2ر.{\displaystyle {\frac {n}{2^{r}}}.}

في أي مرحلة من مراحل التنفيذ، يمكننا تجميع رؤوس الرسم البياني في "مجموعات" وفقًا لرتبتها. نُعرّف نطاقات المجموعات استقرائيًا كما يلي: تحتوي المجموعة 0 على رؤوس من الرتبة 0. تحتوي المجموعة 1 على رؤوس من الرتبة 1. تحتوي المجموعة 2 على رؤوس من الرتبتين 2 و3. بشكل عام، إذا كانت المجموعة B تحتوي على رؤوس برتب من الفترة[ر،2ر-1]=[ر،R-1]{\displaystyle \left[r,2^{r}-1\right]=[r,R-1]}إذن، ستحتوي الحاوية (B+1) على رؤوس ذات رتب من الفترة[R،2R-1].{\displaystyle \left[R,2^{R}-1\right].}

لب∈شمال{\displaystyle B\in \mathbb {N} }، يتركبرج(ب)=22⋯2⏟ب أوقات{\displaystyle {\text{tower}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ times}}}}ثم دلوب{\displaystyle B}ستحتوي على رؤوس ذات رتب في الفترة[برج(ب-1)،برج(ب)-1]{\displaystyle [{\text{tower}}(B-1),{\text{tower}}(B)-1]}.

إثباتيا(سجل*⁡ن){\displaystyle O(\log ^{*}n)}البحث الموحد

يمكننا أن نلاحظ أمرين بخصوص أحجام الدلاء.

  1. يبلغ العدد الإجمالي للدلاء على الأكثر log * n .
    البرهان: بما أنه لا يمكن لأي رأس أن يكون له رتبة أكبر منن{\displaystyle n}، الأول فقطسجل*⁡(ن){\displaystyle \log ^{*}(n)}يمكن أن تحتوي الحاويات على رؤوس، حيثسجل*{\displaystyle \log ^{*}}يشير إلى معكوسبرج{\displaystyle {\text{tower}}}الدالة المحددة أعلاه.
  2. الحد الأقصى لعدد العناصر في الحاوية[ب،2ب-1]{\displaystyle \left[B,2^{B}-1\right]}هو على الأكثر2ن2ب{\displaystyle {\frac {2n}{2^{B}}}}.
    البرهان: الحد الأقصى لعدد العناصر في الحاوية[ب،2ب-1]{\displaystyle \left[B,2^{B}-1\right]}هو على الأكثرن2ب+ن2ب+1+ن2ب+2+⋯+ن22ب-1≤2ن2ب.{\displaystyle {\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.}

لنفترض أن F تمثل قائمة عمليات "البحث" التي تم تنفيذها، ولنفترض

تي1=∑F(رابط إلى الجذر){\displaystyle T_{1}=\sum _{F}{\text{(رابط إلى الجذر)}}}تي2=∑F(عدد الروابط التي تم اجتيازها حيث تكون الحاويات مختلفة){\displaystyle T_{2}=\sum _{F}{\text{(عدد الروابط التي تم اجتيازها حيث تكون الحاويات مختلفة)}}}تي3=∑F(عدد الروابط التي تم اجتيازها حيث تكون الحاويات متطابقة).{\displaystyle T_{3}=\sum _{F}{\text{(عدد الروابط التي تم اجتيازها حيث تكون الحاويات متطابقة).}}}

إذن، التكلفة الإجمالية لـ m عملية شراء هيتي=تي1+تي2+تي3.{\displaystyle T=T_{1}+T_{2}+T_{3}.}

بما أن كل عملية بحث تقوم بعملية اجتياز واحدة بالضبط تؤدي إلى جذر، فإن لدينا T 1 = O ( m ) .

أيضًا، من الحد المذكور أعلاه لعدد الدلاء، لدينا T 2 = O ( m log * n ) .

بالنسبة لـ T 3 ، لنفترض أننا نجتاز حافة من u إلى v ، حيث يكون لـ u و v رتبة في المجموعة [ B , 2B − 1] و v ليس الجذر (في وقت هذا الاجتياز، وإلا سيتم احتساب الاجتياز في T 1 ). ثبت u وانظر إلى المتتاليةv1،v2،...،vك{\displaystyle v_{1},v_{2},\ldots ,v_{k}}التي تلعب دور v في عمليات البحث المختلفة. نظرًا لضغط المسار وعدم احتساب الحافة المؤدية إلى الجذر، فإن هذا التسلسل يحتوي فقط على عقد مختلفة، وبسبب اللمة 1، نعلم أن رتب العقد في هذا التسلسل تتزايد بشكل صارم. وبما أن كلتا العقدتين موجودتان في المجموعة، يمكننا أن نستنتج أن طول التسلسل k (عدد مرات ارتباط العقدة u بجذر مختلف في نفس المجموعة) هو على الأكثر عدد الرتب في المجموعات B ، أي على الأكثر2ب-1-ب<2ب.{\displaystyle 2^{B}-1-B<2^{B}.}

لذلك،تي3≤∑[ب،2ب-1]∑u2ب.{\displaystyle T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.}

من الملاحظتين 1 و 2 ، يمكننا أن نستنتج أنتي3≤∑ب2ب2ن2ب≤2نسجل*⁡ن.{\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}

لذلك،تي=تي1+تي2+تي3=يا(مسجل*⁡ن).{\displaystyle T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).}

هياكل أخرى

أفضل وقت ممكن لكل عملية في أسوأ الحالات

أسوأ وقت للعملية Findفي الأشجار التي تستخدم الاتحاد حسب الرتبة أو الاتحاد حسب الوزن هوΘ(سجل⁡ن){\displaystyle \Theta (\log n)}(أي، هو)يا(سجل⁡ن){\displaystyle O(\log n)}وهذا الحد ضيق). في عام 1985، قدم ن. بلوم تطبيقًا للعمليات لا يستخدم ضغط المسار، ولكنه يضغط الأشجار أثناءuنأناoن{\displaystyle union}. يتم تنفيذه فييا(سجل⁡ن/سجل⁡سجل⁡ن){\displaystyle O(\log n/\log \log n)}[ 16 ] وبالتالي، بالمقارنة مع هيكل جالر وفيشر، يتميز هذا الهيكل بزمن أسوأ حالة لكل عملية، ولكنه أقل كفاءة من حيث الوقت المستهلك. في عام 1999، قدم ألستروب وآخرون هيكلًا يتميز بزمن أسوأ حالة مثالي .يا(سجل⁡ن/سجل⁡سجل⁡ن){\displaystyle O(\log n/\log \log n)}بالإضافة إلى الوقت المستهلك وفقًا لنظرية أكرمان العكسية. [ 17 ]

الحذف

لا يستجيب التنفيذ التقليدي باستخدام غابات المجموعات المنفصلة بشكل إيجابي لحذف العناصر، بمعنى أن زمن التنفيذ Findلن يتحسن نتيجةً لانخفاض عدد العناصر. ومع ذلك، توجد تطبيقات حديثة تسمح بالحذف في زمن ثابت، حيث Findيعتمد الحد الزمني للحذف على العدد الحالي للعناصر [ 18 ] [ 19 ].

التراجع

من الممكن توسيع بعض هياكل الغابات ذات المجموعات المنفصلة للسماح بالتراجع . الشكل الأساسي للتراجع هو السماح Backtrack(1)بعملية تلغي آخر عملية Union. يسمح شكل أكثر تقدماً Backtrack(i)بعملية تلغي آخر i من الاتحادات. نتيجة التعقيد المعروفة هي: توجد بنية بيانات تدعم Union و Findفييا(سجل⁡ن/سجل⁡سجل⁡ن){\displaystyle O(\log n/\log \log n)}الوقت لكل عملية، Backtrackوفييا(1){\displaystyle O(1)}[ 20 ] في هذه النتيجة ، تُعد حرية Unionاختيار ممثل المجموعة المُشكّلة أمرًا أساسيًا. لا يمكن تحقيق وقت استهلاك أفضل ضمن فئة خوارزميات المؤشر القابلة للفصل . [ 20 ]

التطبيقات

عرض توضيحي لخوارزمية Union-Find عند استخدام خوارزمية Kruskal لإيجاد الشجرة الممتدة الدنيا.

تُستخدم هياكل بيانات المجموعات المنفصلة لنمذجة تقسيم مجموعة ما ، على سبيل المثال لتتبع المكونات المتصلة في رسم بياني غير موجه . ويمكن استخدام هذا النموذج لتحديد ما إذا كان رأسان ينتميان إلى نفس المكون، أو ما إذا كانت إضافة حافة بينهما ستؤدي إلى دورة. وتُستخدم خوارزمية الاتحاد-الإيجاد في تطبيقات التوحيد عالية الأداء . [ 21 ]

تستخدم مكتبة Boost Graph هذه البنية البيانية لتنفيذ وظيفة المكونات المتصلة التزايدية . كما أنها عنصر أساسي في تطبيق خوارزمية كروسكال لإيجاد الشجرة الممتدة الدنيا للرسم البياني.

تستخدم خوارزمية هوشن -كوبلمان عملية الاتحاد والبحث.

يمكن استخدام خوارزمية البحث عن الاتحاد لتنفيذ خوارزميات استنتاج الأنواع ذات الأداء المعقول .

انظر أيضاً

  • تحسين التقسيم ، وهو بنية بيانات مختلفة للحفاظ على المجموعات المنفصلة، ​​مع تحديثات تفصل المجموعات بدلاً من دمجها معًا
  • الاتصال الديناميكي – بنية بيانات تحتفظ بمعلومات حول المكونات المتصلة في الرسم البياني 

مراجع

  1. 1 2 3 4 5 6 تارجان، روبرت إندري (1975). "كفاءة خوارزمية اتحاد مجموعات جيدة ولكنها غير خطية". مجلة ACM . 22 (2): 215-225 . doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 . 
  2. ↑ غالر، برنارد أ .؛ فيشر، مايكل ج. (مايو 1964). "خوارزمية محسّنة للتكافؤ" . مجلة اتصالات رابطة مكائن ​​الحوسبة . 7 (5): 301-303 . doi : 10.1145/364099.364331 . S2CID 9034016 . الورقة البحثية التي ابتكرت مفهوم الغابات المنفصلة.
  3. ↑ هوبكروفت، جيه إي ؛ أولمان، جيه دي (1973). "خوارزميات دمج المجموعات". مجلة SIAM للحوسبة . 2 (4): 294-303 . doi : 10.1137/0202024 .
  4. 1 2 3 تارجان، روبرت إي .؛ فان ليوين، جان (1984). "تحليل أسوأ الحالات لخوارزميات اتحاد المجموعات" . مجلة ACM . 31 (2): 245-281 . doi : 10.1145/62.2160 . S2CID 5363073 . 
  5. 1 2 تارجان، روبرت إندري (1979). "فئة من الخوارزميات التي تتطلب وقتًا غير خطي للحفاظ على مجموعات منفصلة" . مجلة علوم الحاسوب والنظم . 18 (2): 110-127 . doi : 10.1016/0022-0000(79)90042-4 .
  6. 1 2 فريدمان، م.؛ ساكس، م. (مايو 1989). "تعقيد مسبار الخلية لهياكل البيانات الديناميكية". وقائع الندوة السنوية الحادية والعشرين لجمعية ACM حول نظرية الحوسبة - STOC '89 . الصفحات 345-354 . doi : 10.1145/73007.73040 . ISBN  0897913078. S2CID 13470414 . النظرية 5: أي تطبيق CPROBE(log n ) لمشكلة اتحاد المجموعات يتطلب Ω( m α( m , n )) من الوقت لتنفيذ m عملية بحث و n − 1 عملية اتحاد، بدءًا من n مجموعة أحادية. 
  7. ↑ جاليل، ز.؛ إيتاليانو، ج. (1991). "هياكل البيانات والخوارزميات لمشاكل اتحاد المجموعات المنفصلة". مجلة ACM Computing Surveys . 23 (3): 319-344 . doi : 10.1145/116873.116878 . S2CID 207160759 . 
  8. ↑ أندرسون، ريتشارد جيه؛ وول، هيذر (1994). خوارزميات متوازية بدون انتظار لمسألة الاتحاد والبحث . المؤتمر الثالث والعشرون لجمعية الحوسبة الآلية حول نظرية الحوسبة. الصفحات 370-380 . doi : 10.1145/103418.103458 . 
  9. ↑ كونشون، سيلفان؛ فيلياتر، جان كريستوف (أكتوبر 2007). "بنية بيانات الاتحاد والبحث المستمرة". ورشة عمل ACM SIGPLAN حول ML . فرايبورغ، ألمانيا.
  10. ↑ هارولد ن. غابو، روبرت إندري تارجان، "خوارزمية خطية الزمن لحالة خاصة من اتحاد المجموعات المنفصلة"، مجلة علوم الحاسوب والأنظمة، المجلد 30، العدد 2، 1985، الصفحات 209-221، الرقم الدولي الموحد للدوريات 0022-0000، https://doi.org/10.1016/0022-0000(85)90014-5
  11. ١ ٢ ٣ كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (٢٠٠٩). "الفصل ٢١: هياكل البيانات للمجموعات المنفصلة". مقدمة في الخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا. الصفحات ٥٧١-٥٧٢ . ISBN   978-0-262-03384-8.
  12. ↑ رايموند سيدل ، ميخا شارير. "تحليل من أعلى إلى أسفل لضغط المسار"، مجلة SIAM للحوسبة 34(3):515–525، 2005
  13. ↑ تارجان، روبرت إندري (1975). "كفاءة خوارزمية اتحاد مجموعات جيدة ولكنها غير خطية" . مجلة ACM . 22 (2): 215-225 . doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 . 
  14. ↑ هوبكروفت، جيه إي؛ أولمان، جيه دي (1973). "خوارزميات دمج المجموعات". مجلة SIAM للحوسبة . 2 (4): 294-303 . doi : 10.1137/0202024 .
  15. ↑ روبرت إي. تارجان ويان فان ليوين . تحليل أسوأ الحالات لخوارزميات اتحاد المجموعات. مجلة ACM، 31(2):245–281، 1984.
  16. ↑ بلوم، نوربرت (1985). "حول تعقيد الوقت في أسوأ حالة لعملية واحدة لمسألة اتحاد المجموعات المنفصلة". الندوة الثانية حول الجوانب النظرية لعلوم الحاسوب : 32-38 .
  17. ↑ ألستروب، ستيفن؛ بن عمرام، أمير م.؛ راوه، ثيس (1999). "الحالة الأسوأ والأمثلية المُستهلكة في خوارزمية الاتحاد والبحث (ملخص موسع)". وقائع الندوة السنوية الحادية والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة . الصفحات 499-506 . doi : 10.1145/301250.301383 . ISBN  1581130678. S2CID 100111 . 
  18. ^ ألستروب ، ستيفن. ثوروب، ميكيل. جورتز، إنجي لي؛ راوهي، ثيس؛ زويك ، أوري (2014). “العثور على الاتحاد مع حذف الوقت المستمر”. المعاملات ACM على الخوارزميات . 11 (1): 6: 1-6:28. دوى : 10.1145/2636922 . S2CID 12767012 . 
  19. ↑ بن عمرام، أمير م.؛ يوفي، سيمون (2011). "خوارزمية بسيطة وفعالة للدمج والبحث والحذف". علوم الحاسوب النظرية . 412 ( 4-5 ): 487-492 . doi : 10.1016/j.tcs.2010.11.005 .
  20. 1 2 ويستبروك، جيفري ر.؛ تارجان، روبرت إي. (1989). "التحليل المُستهلك للخوارزميات الخاصة باتحاد المجموعات مع التراجع". مجلة SIAM للحوسبة . 18 (1): 1-11 . doi : 10.1137/0218001 .
  21. ↑ نايت، كيفن (1989). "التوحيد: دراسة متعددة التخصصات" (ملف PDF) . مجلة ACM Computing Surveys . 21 : 93-124 . doi : 10.1145/62029.62030 . S2CID 14619034 .