مرجع
آخر الزيارات

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

779 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: في علم الحاسوب، المجموعة المنفصلة من هيكلة البيانات كما تسمى ايضًا هيكلة بيانات العثور المتحد أو مجموعة العثور المندمج، هيكلة البيانات هذه تضمن أن يكون تتابع العناصر فيها منفصل في عدد من الفروع المفككة (غير متداخلة.) كما تدعم هذه الهيكلة…. تجد هنا «x.parent := x»، «x.rank := 0» و«xRoot.parent := yRoot» ضمن 11 قسماً.
المحتويات
  1. x.parent := x
  2. x.rank := 0
  3. xRoot.parent := yRoot
  4. تطبيقات
  5. xRoot.rank := xRoot.rank + 1
  6. المجموعة المنفصلة ذات القوائم المترابطة
  7. غابات المجموعات المنفصلة
  8. تاريخ
  9. return
  10. else
  11. if x.parent != x

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

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

كذلك، 1- الإيجاد (Find) : تحديد في أي الفروع يوجد العنصر، تعيد عملية الإيجاد بالعادة العنصر من هذه المجموعة عن طريق ممثله عبر مقارنة نتيجتي علميتي بحث، ليتم تحديد إذا كان العنصرين في نفس المجموعة ام لا.2- الاتحاد (Union) : حيث يقوم بجمع فرعين في فرع واحد.

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

من جانب آخر، إذًا Find(x) تعيد ممثل المجموعة التي ينتمي اليها x، وعملية الاتحاد Union تأخد ممثلي المجموعتين لدمجهما معا في مجموعة واحدة.

x.parent := x

  • function Find(x)
  • if x.parent == x
  • return x

x.rank := 0

  • function Union(x, y)
  • xRoot := Find(x)
  • yRoot := Find(y)
  • if xRoot == yRoot

xRoot.parent := yRoot

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

x.parent := x

function MakeSet(x)

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

ومن جهة أخرى، الطريقة الأولى، وهي الدمج حسب المرتبة أي دمج الشجرة الأصخر اليى الشجرة الأكبر، حيث عمق الشجرة هو من يتحكم بمقدار جودة الشجرة وبالتالي لن يزداد العمق الا بحالة كان العمقين متساووين.

تطبيقات

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

xRoot.rank := xRoot.rank + 1

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

function Find(x)

المجموعة المنفصلة ذات القوائم المترابطة

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

وفي السياق ذاته، هيكلة المجموعات المنفصلة للبيانات بصيغتها البسيطة تستعمل القوائم المترابطة لكل مجموعة، ويتم اختيار رأس هذه القائمة كممثل لهذه المجموعة.

في هذا الإطار، لكن من الممكن تجاهل هذا بإضافة مؤشر يؤشر على رأس القائمة في كل عقدة (node) تابعة لهذه القائمة وبتالي ستأخذ عملية البحث وقت ثابت حيث يعود هذا المؤشر بشكل مباشر إلى الممثل لهذه القائمة لكن بهذه الحالة سنقع في مشكلة أخرى حيث سنصبح بحاجة إلى تعديل كل العقد ليؤشروا على رأس قائمة من القائمتين في حال استعملنا عملية الاتحاد Union وهذا يتتطلب O(n) عملية.

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

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

علاوةً على ذلك، غابات المجموعات المنفصلة هي هيكلة بينات حيث تكون كل مجموعة على شكل هيكلة بيانات شجرية بحيت تحتوي كل عقدة مؤشر للعقدة الأب.

function MakeSet(x)

كذلك، في غابة المجموعة المنفصلة الممثل لكل مجموعة هو جذر شجرة المجموعة حيث تقوم عملية البحث بتتبع الأب لكل عقدة حتى تصل إلى جذر الشجرة وتقوم عملية الدمج بحيث يتم رفح جذر أحد الأشجار إلى الشجرة المراد الدمج اليها حيث يتم كتابة العمليات الثلاث بالشكل التالي:

تاريخ

علاوةً على ذلك، كما طور ترجان وفان لوين خوارزمية البحث تقوم باعادة النتيجة بمرور واحد أكثر دقة.

إضافةً إلى ذلك، في عام 2007 قام سلفيان كونكون وو جين كريستوف فليتر طور نسخة متكررة من هيكلة المجموعة المنفصلة بحيث يسمح للهيكل السابق بالحفاظ على كفائته بستخدام اثبات مساعد كوك

ومن جهة أخرى، رغم أن الأفكار المستعملة في المجموعات المنفصلة ومعروفة منذ زمن، كان روبرت ترجان أول من أثبت الحد الأعلى والنسخة المقيدة من الحد الأدنى بعكس وظيفة اركمان عام 1975، حتى هذا الوقت كان أفضل حد مكتشف عر هوبكرافت ويلمان حيث كان O(logn)، الخوارزمية المعادة ل n، معادلة أخرى تنمو ببطء.

return

  • // x and y are not already in same set. Merge them.
  • if xRoot.rank < yRoot.rank
  • xRoot.parent := yRoot
  • else if xRoot.rank > yRoot.rank
  • yRoot.parent := xRoot
  • else
  • yRoot.parent := xRoot

else

  • return Find(x.parent)
  • function Union(x, y)
  • xRoot := Find(x)
  • yRoot := Find(y)

if x.parent != x

return x.parent

x.parent := Find(x.parent)

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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