تقاطع الماترويد

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

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

تنص نظرية تقاطع الماترويد ، التي وضعها جاك إدموندز ، [ 1 ] على أنه لأي ماترويدينم1=(هـ،أنا1){\displaystyle M_{1}=(E,{\mathcal {I}}_{1})}وم2=(هـ،أنا2){\displaystyle M_{2}=(E,{\mathcal {I}}_{2})}لدينا

الأعلىأنا∈أنا1∩أنا2|أنا|=مينأ⊆هـ(ر1(أ)+ر2(هـ∖أ)){\displaystyle \max _{I\in {\mathcal {I}}_{1}\cap {\mathcal {I}}_{2}}|I|=\min _{A\subseteq E}(r_{1}(A)+r_{2}(E\setminus A))}

أينر1{\displaystyle r_{1}}ور2{\displaystyle r_{2}}هي دوال الرتبة الخاصة بـم1{\displaystyle M_{1}}وم2{\displaystyle M_{2}}بمعنى آخر، هناك دائمًا برهان بسيط للحد الأعلى، يتكون من تقسيم المجموعة الأرضية بين المصفوفتين، والتي تساوي قيمتها (مجموع الرتب المعنية ) حجم مجموعة مستقلة مشتركة قصوى.

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

أمثلة

ليكن G  =  ( U , V ; E ) رسمًا بيانيًا ثنائي الأجزاء . يمكن تعريف مصفوفة تقسيم MU على المجموعة الأساسية E ، حيث تكون مجموعة من الحواف مستقلة إذا لم يكن لأي حافتين منها نفس نقطة النهاية في U. وبالمثل ، يمكن تعريف مصفوفة تقسيم MU بحيث تكون مجموعة من الحواف مستقلة إذا لم يكن لأي حافتين منها نفس نقطة النهاية في V. أي مجموعة من الحواف المستقلة في كل من MU و MU تتميز بخاصية عدم اشتراك أي حافتين منها في نقطة نهاية واحدة؛ أي أنها مجموعة مطابقة . وبالتالي، فإن أكبر مجموعة مستقلة مشتركة بين MU و MU هي مجموعة مطابقة قصوى في G.

وبالمثل، إذا كان لكل حافة وزن، فإن المجموعة المستقلة ذات الوزن الأقصى لـ M U و M V هي مطابقة الوزن الأقصى في G.

الخوارزميات

توجد عدة خوارزميات ذات زمن تشغيل متعدد الحدود لتقاطع المصفوفات الموزونة، وتختلف هذه الخوارزميات في زمن التشغيل. ويتم تحديد أزمنة التشغيل بدلالة ن{\displaystyle n}- عدد العناصر في المجموعة الأساسية المشتركة،ر{\displaystyle r}- الحد الأقصى بين رتبتي الماترويدتين، تي{\displaystyle T}- عدد العمليات المطلوبة لخوارزمية البحث عن الدوائر ، وك{\displaystyle k}- عدد العناصر في التقاطع (في حال أردنا إيجاد تقاطع بحجم محدد)ك{\displaystyle k}).

  • تستخدم خوارزمية إدموندز البرمجة الخطية والمجسمات متعددة الأوجه. [ 1 ]
  • خوارزمية لولر . [ 2 ]
  • خوارزمية إيري وتوميزاوا [ 3 ]
  • تستخدم خوارزمية أندراس فرانك [ 4 ]يا(ن3تي){\displaystyle O(n^{3}T)}العمليات الحسابية.
  • خوارزمية أورلين وفاندي-فات. [ 5 ]
  • تتطلب خوارزمية كانينغهام [ 6 ]يا(ر1.5نتي){\displaystyle O(r^{1.5}nT)}العمليات على الماترويدات العامة، ويا(نر2سجل⁡ر){\displaystyle O(nr^{2}\log {r})}العمليات على المصفوفة الخطية ، لمصفوفتين من الرتبة r × n .
  • يقدم Brezovec و Cornuejos و Glover [ 7 ] خوارزميتين لتقاطع المصفوفات الموزونة.
    • تتطلب الخوارزمية الأولى أن تكون جميع الأوزان أعدادًا صحيحة، وتجد تقاطعًا من حيث العدديةك{\displaystyle k}في الوقت المناسبيا((ن3ك2+نكتي)⋅(1+سجل⁡دبليو)){\displaystyle O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))}.
    • تعمل الخوارزمية الثانية في الوقت المحدديا(نر⋅(سجل⁡ن+ر+تي)){\displaystyle O(nr\cdot (\log {n}+r+T))}.
  • أظهر هوانغ وكاكيمورا وكامياما [ 8 ] أنه يمكن حل مسألة تقاطع الماترويد الموزون بحل W حالة من مسألة تقاطع الماترويد غير الموزون، حيث W هو أكبر وزن مُعطى، بافتراض أن جميع الأوزان المُعطاة أعداد صحيحة. هذه الخوارزمية أسرع من الخوارزميات السابقة عندما تكون W صغيرة. كما قدموا خوارزمية تقريبية تجد حلاً تقريبيًا من الرتبة e عن طريق حليا(ϵ-1سجل⁡ر){\displaystyle O(\epsilon ^{-1}\log {r})}أمثلة على مشكلة تقاطع الماترويد غير الموزون، حيث r هو الرتبة الأصغر للماترويدين المدخلين.
  • قام غوش وغورجار وراج [ 9 ] بدراسة تعقيد وقت التشغيل لتقاطع المصفوفات في نموذج الحوسبة المتوازية .
  • يقدم كل من بيرتسي، وكيرالي، وياماغوتشي، ويوكوي [ 10 ] خوارزميات ذات وقت متعدد الحدود بقوة لتقاطع المصفوفات الموزونة باستخدام أوراكل أكثر تقييدًا.

الإضافات

زيادة الوزن إلى أقصى حد مع مراعاة العددية

في أحد أنواع تقاطع المصفوفات الموزونة، والذي يُسمى "(P k )"، يتمثل الهدف في إيجاد مجموعة مستقلة مشتركة ذات وزن أقصى ممكن بين جميع المجموعات ذات العدد k ، إن وُجدت. ويمكن حل هذا النوع أيضًا في وقت متعدد الحدود. [ 7 ]

ثلاثة ماترويدات

تصبح مشكلة تقاطع الماترويد صعبة الحل (NP-hard) عندما يتم تضمين ثلاث ماترويدات، بدلاً من اثنتين فقط.

أحد البراهين على صعوبة هذه المسألة يعتمد على اختزال من مسألة المسار الهاميلتوني في الرسوم البيانية الموجهة . بفرض وجود رسم بياني موجه G ذي n رأسًا، وعقدتين محددتين s و t ، فإن مسألة المسار الهاميلتوني هي تحديد ما إذا كان هناك مسار بسيط بطول n − 1 يبدأ من s وينتهي عند t . يمكن افتراض، دون فقدان للعمومية، أن s ليس له حواف واردة وأن t ليس له حواف صادرة. عندئذٍ، يوجد مسار هاميلتوني إذا وفقط إذا كانت هناك مجموعة من n − 1 عنصرًا في تقاطع ثلاث مصفوفات على مجموعة حواف الرسم البياني: مصفوفتا تقسيم تضمنان أن تكون درجة الدخول ودرجة الخروج لمجموعة الحواف المختارة على الأكثر واحدًا، والمصفوفة الرسومية للرسم البياني غير الموجه المُشكَّل بتجاهل اتجاهات الحواف في G ، مما يضمن أن مجموعة الحواف المختارة لا تحتوي على دورات. [ 11 ]    

تكافؤ الماترويد

صاغ لولر [ 12 ] مسألة حسابية أخرى تتعلق بالماترويدات، وهي مسألة تكافؤ الماترويدات ، كتعميم شائع لمسألة تقاطع الماترويدات ومطابقة الرسوم البيانية غير الثنائية. ومع ذلك، فرغم إمكانية حلها في وقت متعدد الحدود للماترويدات الخطية ، إلا أنها تُصنف ضمن المسائل الصعبة حسابيًا (NP-hard) للماترويدات الأخرى، وتتطلب وقتًا أُسّيًا في نموذج أوراكل الماترويدات . [ 13 ]

الماترويدات المقيمة

الماترويد المُقَيَّم هو ماترويد مزود بدالة قيمة v على مجموعة قواعده، مع خاصية التبادل التالية : لأي قاعدتين مختلفتينأ{\displaystyle A}وب{\displaystyle B}، لوأ∈أ∖ب{\displaystyle a\in A\setminus B}إذن يوجد عنصرب∈ب∖أ{\displaystyle b\in B\setminus A}بحيث يكون كلاهما(أ∖{أ})∪{ب}{\displaystyle (A\setminus \{a\})\cup \{b\}}و(ب∖{ب})∪{أ}{\displaystyle (B\setminus \{b\})\cup \{a\}}هي قواعد، و  :v(أ)+v(ب)≤v(ب∖{ب}∪{أ})+v(أ∖{أ}∪{ب}){\displaystyle v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\})}.

بالنظر إلى رسم بياني ثنائي الأجزاء مُثقَّل G = ( X + Y , E ) ومصفوفتين مُقَيَّمتين، إحداهما على X بمجموعة قواعد BX وتقييم vX ، والأخرى على Y بقواعد BY وتقييم vY ، فإن مسألة التخصيص المستقل المُقَيَّم هي مسألة إيجاد تطابق M في G ، بحيث يكون MX (المجموعة الجزئية من X التي يُطابقها M ) قاعدة في BX ، ويكون MY قاعدة في BY ، وبشرط ذلك، يكون المجموعw(م)+vX(مX)+vY(مY){\displaystyle w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})}يتم تعظيمها. تُعد مسألة تقاطع الماترويد الموزون حالة خاصة تكون فيها تقييمات الماترويد ثابتة، لذلك نسعى فقط إلى تعظيمهاw(م){\displaystyle w(M)}بشرط أن يكون M X قاعدة في B X و M Y قاعدة في BY . [ 14 ] يقدم موروتا خوارزمية زمنية متعددة الحدود لهذه المسألة . [ 15 ]

انظر أيضاً

مراجع

  1. 1 2 إدموندز، جاك (1970)، "الدوال شبه المعيارية، والماترويدات، وبعض المجسمات متعددة السطوح"، في آر. جاي؛ إتش. هانام؛ إن. ساوير؛ جيه. شونهايم (محررون)، الهياكل التوافقية وتطبيقاتها (وقائع مؤتمر كالجاري 1969) ، جوردون وبريتش، نيويورك، ص 69-87 . أعيد طبعه في M. Jünger وآخرون. (محرران): التحسين التوافقي (Edmonds Festschrift)، LNCS 2570، الصفحات 1126، Springer-Verlag، 2003.
  2. ↑ لولر، يوجين ل. (1975)، "خوارزميات تقاطع الماترويد"، البرمجة الرياضية ، 9 (1): 31-56 ، doi : 10.1007/BF01681329 ، S2CID 206801650 
  3. ^ إيري، ماساو؛ توميزاوا، نوبواكي (1976). "خوارزمية لإيجاد "المهمة المستقلة" الأمثل"" .日本オペレーションズ・リサーチ学会論文誌. 19 (1): 32– 57. doi : 10.15807/jorsj.19.32 .
  4. ↑ فرانك، أندراس (1981)، "خوارزمية تقاطع الماترويد الموزون"، مجلة الخوارزميات ، 2 (4): 328-336 ، doi : 10.1016/0196-6774(81)90032-8
  5. ↑ أورلين، جيمس ب.؛ فانديفات، جون (1983). حول خوارزمية تقاطع الماترويد "الأولية" (ورقة عمل كلية سلون للإدارة رقم 1446-83). hdl : 1721.1/2050 .
  6. ↑ كونينغهام، ويليام هـ. (1986-11-01). "حدود محسّنة لخوارزميات تقسيم المصفوفات وتقاطعها" . مجلة SIAM للحوسبة . 15 (4): 948-957 . doi : 10.1137/0215066 . ISSN 0097-5397 . 
  7. 1 2 بريزوفيتش، كارل؛ كورنويجول، جيرار ؛ جلوفر، فريد (1986)، "خوارزميتان لتقاطع الماترويد الموزون"، البرمجة الرياضية ، 36 (1): 39-53 ، doi : 10.1007/BF02591988 ، S2CID 34567631 
  8. ↑ هوانغ، تشين-تشونغ؛ كاكيمورا، ناونوري؛ كامياما، ناويوكي (2019-09-01). "خوارزميات دقيقة وتقريبية لتقاطع الماترويد الموزون" . البرمجة الرياضية . 177 (1): 85-112 . doi : 10.1007/s10107-018-1260-x . hdl : 2324/1474903 . ISSN 1436-4646 . S2CID 254138118 .  
  9. ↑ غوش، سومنتا؛ غورجار، روهيت؛ راج، روشان (2022-01-01)، "اختزال متوازٍ حتمي من بحث تقاطع المصفوفات الموزونة إلى القرار" ، وقائع ندوة ACM-SIAM السنوية لعام 2022 حول الخوارزميات المنفصلة (SODA) ، وقائع جمعية الرياضيات الصناعية والتطبيقية، الصفحات 1013-1035 ، doi : 10.1137/1.9781611977073.44 ، ISBN  978-1-61197-707-3، S2CID 245799113 ، تم استرجاعه بتاريخ 28-11-2022 
  10. ^ بيرزي، كريستوف. كيرالي، تاماس؛ ياماغوتشي، يوتارو؛ يوكوي ، يو (28/09/2022). “تقاطع Matroid تحت Oracles المقيدة”. أرخايف : 2209.14516 [ cs.DS ].
  11. ^ الويلزية، DJA (2010) [1976]، نظرية ماترويد ، منشورات كورير دوفر، ص. 131، ردمك  9780486474397.
  12. ↑ لولر، يوجين ل. (1976)، "الفصل 9: مشكلة تكافؤ الماترويد" ، التحسين التوافقي: الشبكات والماترويدات ، نيويورك: هولت، راينهارت ووينستون، ص 356-367 ، MR 0439106  .
  13. ↑ جنسن، بير م.؛ كورت، برنارد (1982)، "تعقيد خوارزميات خصائص الماترويد"، مجلة SIAM للحوسبة ، 11 (1): 184-190 ، doi : 10.1137/0211014 ، MR 0646772 .
  14. ↑ موروتو، كازو (1996-11-01). "تقاطع المصفوفات المُقَيَّمة 1: معايير الأمثلية" . مجلة SIAM للرياضيات المتقطعة . 9 (4): 545-561 . doi : 10.1137/S0895480195279994 . ISSN 0895-4801 . 
  15. ^ موروتا ، كازو (نوفمبر 1996). "تقييم تقاطع ماترويد II: الخوارزميات" . مجلة SIAM للرياضيات المنفصلة . 9 (4): 562-576 . دوى : 10.1137 / S0895480195280009 . ISSN 0895-4801 . 

للمزيد من القراءة