خوارزمية بلوسوم

في نظرية المخططات ، تُعدّ خوارزمية الزهرة خوارزميةً لإنشاء متطابقات قصوى على المخططات . طُوّرت هذه الخوارزمية بواسطة جاك إدموندز عام 1961، ^{[ 1 ]} ونُشرت عام 1965. ^{[ 2 ]} بالنظر إلى مخطط عام G = ( V , E ) ، تجد الخوارزمية تطابقًا M بحيث يكون كل رأس في V متصلًا بحافة واحدة على الأكثر في M ، ويكون طول التطابق | M | في أعلى قيمة له. يُنشأ التطابق من خلال التحسين التكراري لتطابق أولي فارغ على طول مسارات مُوسّعة في المخطط. على عكس التطابق الثنائي ، تكمن الفكرة الجديدة الرئيسية في اختزال دورة ذات طول فردي في المخطط (الزهرة) إلى رأس واحد، مع استمرار البحث بشكل تكراري في المخطط المُختزل.

يعمل الخوارزمية في زمن قدره O ( | E || V | ^² ) ، حيث | E | هو عدد حواف الرسم البياني و | V | هو عدد رؤوسه . زمن تشغيل أفضل لـ${\displaystyle O(|E|{\sqrt {|V|}})}$ويمكن تحقيق نفس المهمة باستخدام خوارزمية ميكالي وفازيراني الأكثر تعقيدًا. ^{[ 3 ]}

من أهم أسباب أهمية خوارزمية بلوسوم أنها قدمت أول برهان على إمكانية إيجاد تطابق ذي حجم أقصى باستخدام وقت حسابي متعدد الحدود. سبب آخر هو أنها أدت إلى وصف متعدد السطوح للمطابقة باستخدام البرمجة الخطية ، مما أسفر عن خوارزمية للمطابقة ذات الوزن الأدنى . ^{[ 4 ]} وكما أوضح ألكسندر شريفر ، تكمن أهمية هذه النتيجة في كونها أول متعدد سطوح لا يُستنتج برهان تكامله من أحادية المعامل الكلية فحسب ، وكان وصفه بمثابة طفرة في التوافقية متعددة السطوح . ^{[ 5 ]}

بفرض أن G = ( V , E ) وتطابق M في G ، يكون الرأس v مكشوفًا إذا لم يكن أي ضلع من M متصلًا به . المسار في G هو مسار متناوب ، إذا كانت أضلاعه بالتناوب إما غير موجودة في M أو موجودة في M (أو موجودة في M وغير موجودة في M ). المسار المُعزِّز P هو مسار متناوب يبدأ وينتهي عند رأسين مكشوفين مختلفين. لاحظ أن عدد الأضلاع غير المتطابقة في المسار المُعزِّز أكبر بواحد من عدد الأضلاع المتطابقة، وبالتالي فإن العدد الإجمالي للأضلاع في المسار المُعزِّز فردي. التطابق المُعزِّز على طول المسار المُعزِّز P هو عملية استبدال M بتطابق جديد.

${\displaystyle M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)}$.

بحسب مبرهنة بيرج ، تكون المطابقة M قصوى إذا وفقط إذا لم يكن هناك مسار مُعزِّز لـ M في G. ^{[ 6 ] [ 7 ]} وبالتالي، إما أن تكون المطابقة قصوى، أو يمكن تعزيزها. لذا، بدءًا من مطابقة أولية، يمكننا حساب المطابقة القصوى بتعزيز المطابقة الحالية بمسارات مُعزِّزة طالما أمكننا إيجادها، ونعود عندما لا يتبقى أي مسارات مُعزِّزة. يمكننا صياغة الخوارزمية رسميًا كما يلي:

 المدخلات: الرسم البياني G ، المطابقة الأولية M على G. المخرجات: المطابقة القصوى M* على G. A1 دالة find_maximum_matching ( G , M ) : M* A2 P ← find_augmenting_path ( G , M ) A3 إذا كانت P غير فارغة، فإن A4 تُرجع find_maximum_matching ( G , augment M along P ) A5 وإلا A6 إرجاع M A7 نهاية الشرط A8 نهاية الدالة

لا يزال يتعين علينا وصف كيفية إيجاد المسارات المعززة بكفاءة. تستخدم الدالة الفرعية لإيجادها التفتحات والتقلصات.

بالنظر إلى G = ( V , E ) ومطابقة M لـ G ، فإن الزهرة B هي دورة في G تتكون من 2k + 1 حافة منها k تنتمي بالضبط إلى M ، وحيث يكون أحد رؤوس الدورة v ( القاعدة ) بحيث يوجد مسار متناوب ذو طول زوجي ( الجذع ) من v إلى رأس مكشوف w .

إيجاد الأزهار:

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

عرّف الرسم البياني المتقلص G' على أنه الرسم البياني الذي تم الحصول عليه من G عن طريق تقليص كل حافة من B ، وعرّف المطابقة المتقلصة M' على أنها مطابقة G' المقابلة لـ M.

تحتوي G' على مسار مُعزِّز من النوع M' إذا وفقط إذا كانت G تحتوي على مسار مُعزِّز من النوع M ، ويمكن رفع أي مسار مُعزِّز من النوع M '، وهو P' في G '، إلى مسار مُعزِّز من النوع M في G عن طريق عكس الانكماش بواسطة B بحيث يتم استبدال قطعة P' (إن وجدت) التي تمر عبر vB بقطعة مناسبة تمر عبر _B. ^{[ 8 ]} بمزيد من التفصيل:

• إذا مرّت النقطة P' عبر القطعة المستقيمة u → vB → w في _G ' ، فسيتم استبدال هذه القطعة بالقطعة المستقيمة u → ( u' → … → w' ) → w في G ، حيث يتم اختيار رؤوس الزهرة u' و w' وجانب B ، ( u' → … → w' ) ، الممتد من u' إلى w'، لضمان أن المسار الجديد لا يزال متناوبًا ( u' مكشوف بالنسبة إلى${\displaystyle M\cap B}$،${\displaystyle \{w',w\}\in E\setminus M}$).

• إذا كانت النقطة P' لها نهاية v _B ، فسيتم استبدال قطعة المسار u → v _B في G' بالقطعة u → ( u' → … → v' ) في G ، حيث يتم اختيار رؤوس الزهرة u' و v' وجانب B ، ( u' → … → v' ) ، المتجه من u' إلى v' لضمان أن يكون المسار متناوبًا ( v' مكشوفًا).${\displaystyle \{u',u\}\in E\setminus M}$).

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

يستخدم البحث عن مسار مُعزِّز بنية بيانات مساعدة تتكون من غابة F، حيث تتوافق أشجارها الفردية مع أجزاء محددة من الرسم البياني G. في الواقع، الغابة F هي نفسها المستخدمة لإيجاد أقصى تطابق في الرسوم البيانية ثنائية الأجزاء (دون الحاجة إلى تقليص الأزهار). في كل تكرار، إما أن تقوم الخوارزمية بما يلي: (1) إيجاد مسار مُعزِّز، (2) إيجاد زهرة والعودة إلى الرسم البياني المُختزل المقابل، أو (3) استنتاج عدم وجود مسارات مُعزِّزة. يتم بناء البنية المساعدة من خلال إجراء تزايدي سيتم شرحه لاحقًا. ^{[ 8 ]}

تُراعي عملية البناء الرؤوس v والحواف e في G وتُحدّث F تدريجيًا حسب الحاجة. إذا كان v في شجرة T من الغابة، فإننا نرمز root(v)إلى جذر T. إذا كان كل من u و v في نفس الشجرة T في F ، فإننا distance(u,v)نرمز إلى طول المسار الوحيد من u إلى v في T.

 المدخلات: الرسم البياني G ، ومطابقة M على G. المخرجات: إضافة المسار P إلى G أو مسار فارغ إذا لم يتم العثور على مسار. B01 دالة find_augmenting_path ( G , M ) : P B02 F ← غابة فارغة B03 قم بإلغاء تحديد جميع الرؤوس والحواف في G ، وقم بتحديد جميع حواف M. B05 لكل رأس مكشوف v ، قم بما يلي : B06 أنشئ شجرة أحادية { v } وأضف الشجرة إلى F. B07 نهاية حلقة for. B08 طالما يوجد رأس غير مُحدد v في F بمسافة (v، جذر (v)) زوجية، قم بما يلي: B09 طالما توجد حافة غير مُحددة e = { v ، w } ، قم بما يلي: B10 إذا لم يكن w في F ، فهذا يعني أن w مُطابق ، لذا أضف e وحافة w المُطابقة إلى F. B11 x ← الرأس المُطابق لـ w في M. B12 أضف الحافتين { v ، w } و{ w ، x } إلى شجرة v. B13 وإلا B14 إذا كانت المسافة (w، جذر (w)) فردية، فقم بما يلي: // لا تفعل شيئاً. B15 وإلا B16 إذا كان جذر(v) ≠ جذر(w) ثم // أبلغ عن مسار مُعزز في F${\displaystyle \cup }${ هـ }. B17 P ← path ( root ( v ) → ... → v ) → ( w → ... → root ( w )) B18 return P B19 else // قم بتقليص الزهرة في G وابحث عن المسار في الرسم البياني المتقلص. B20 B ← زهرة تتشكل من e والحواف على المسار v → w في T B21 G'، M' ← انكماش G و M بواسطة B B22 P' ← إيجاد_المسار_المعزز ( G' ، M' ) B23 P ← ارفع P' إلى G B24 أعد P B25 نهاية الشرط B26 نهاية الشرط B27 نهاية الشرط B28 ضع علامة على الحافة e B29 نهاية الحلقة B30 ضع علامة على الرأس v B31 نهاية الحلقة B32 أعد مسارًا فارغًانهاية الدالة B33

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

يُقدّم X-Blossom ^{[ 12 ]} حلاً متوازياً فعالاً لحساب أقصى عدد من التطابقات في الرسوم البيانية العامة، ويتناول هذه التحديات بشكل مباشر. يبدأ بتقديم خوارزمية Blossom جديدة خالية من التكرار. في الخوارزمية التقليدية، يتم تقليص الزهرة أثناء البحث، ثم توسيعها عند العثور على مسار مُعزِّز. على النقيض من ذلك، تُزيل الخوارزمية الخالية من التكرار عملية التقليص والتوسيع هذه. الملاحظة الأساسية هي أنه عند إنشاء مسار مُعزِّز، لا داعي للاحتفاظ بسجل التقليص التكراري الكامل. المعلومة الأساسية هي المسار الزوجي المناسب عبر بنية الزهرة. بالتالي، بدلاً من تقليص الزهرة ثم توسيعها، تُسجّل الخوارزمية الخالية من التكرار المسار الزوجي من كل رأس ذي صلة في دورة الزهرة إلى قاعدة الزهرة ^{[ 12 ]} . عندما يمر مسار مُعزِّز عبر الزهرة، يُستخدم المسار المُسجّل لإعادة بناء المسار المُقابل في الرسم البياني الأصلي، كما هو موضح في الشكل أدناه. يحافظ هذا التمثيل على تأثير معالجة الأزهار مع الحفاظ على بنية الرسم البياني ثابتة أثناء البحث.

يُتيح هذا المتغير الخالي من التكرار فرصةً بالغة الأهمية للتوازي الهائل. فبما أن الرسم البياني لا يُعدَّل بشكل متكرر عن طريق الانكماش والرفع، يُمكن فحص رؤوس صالحة متعددة في غابة البحث الحالية في آنٍ واحد. يستغل X-Blossom هذه الخاصية لتحديد مسارات مُوسِّعة متعددة منفصلة الرؤوس في تكرار بحث واحد، مما يسمح بزيادة حجم المطابقة بأكثر من واحد في كل تكرار.

في تطبيقها، تستبدل خوارزمية X-Blossom هياكل الأشجار المتناوبة بجدول مسارات. يسجل هذا الجدول المسارات ذات الطول الزوجي للرؤوس، بغض النظر عما إذا كانت تنتمي إلى زهرة أم لا. ونتيجة لذلك، تتجنب الخوارزمية إنشاء وتفكيك الأشجار المتناوبة والرسوم البيانية المنكمشة بشكل متكرر. هذا يقلل من عبء تتبع المسارات ويجعل الخوارزمية أكثر ملاءمة للتنفيذ المتوازي. أظهرت التجارب المذكورة في دراسة X-Blossom أن تصميمها الخالي من الاستدعاءات المتكررة يحسن الأداء التسلسلي بشكل ملحوظ، وأن نسختها المتوازية تحقق تسارعًا وقابلية للتوسع على منصات متعددة النوى عبر مجموعات بيانات حقيقية واصطناعية ^{[ 12 ]} .

عندما يكون الرسم البياني G ثنائي الأجزاء ، لا توجد دورات فردية فيه . في هذه الحالة، لن يتم العثور على أي تجمعات، ويمكن ببساطة حذف الأسطر من B20 إلى B24 من الخوارزمية. وبالتالي، تُختزل الخوارزمية إلى الخوارزمية القياسية لإنشاء متطابقات ذات عدد عناصر أقصى في الرسوم البيانية ثنائية الأجزاء ^{[ 7 ]،} حيث نبحث بشكل متكرر عن مسار مُعزز من خلال اجتياز بسيط للرسم البياني : وهذا، على سبيل المثال، هو حال خوارزمية فورد-فولكرسون .

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

• إكس-بلوسوم