خوارزمية MaxCliqueDyn

خوارزمية MaxCliqueDyn هي خوارزمية لإيجاد أكبر مجموعة في رسم بياني غير موجه.

تعتمد مكتبة MaxCliqueDyn على خوارزمية MaxClique، التي تحدد أكبر زمرة ذات حجم محدود. ويتم تحديد هذا الحد باستخدام خوارزمية تلوين . وتُوسّع MaxCliqueDyn نطاق MaxClique ليشمل حدودًا متغيرة ديناميكيًا.

صُممت هذه الخوارزمية بواسطة يانيز كونك، ونُشر وصفها عام ٢٠٠٧. ^{[ ١ ]} بالمقارنة مع الخوارزميات السابقة، تتميز MaxCliqueDyn بخوارزمية تلوين مُحسّنة (ColorSort)، وتُطبق حدودًا عليا أكثر دقة وتكلفة حسابية أعلى على جزء من مساحة البحث. ^{[ ١ ]} يُقلل كلا التحسينين من الوقت اللازم لإيجاد الزمرة القصوى. إضافةً إلى تقليل الوقت، تُقلل خوارزمية التلوين المُحسّنة أيضًا من عدد الخطوات اللازمة لإيجاد الزمرة القصوى.

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

تُعدّ خوارزمية MaxClique ^{[ 2 ]} الخوارزمية الأساسية التي تم توسيع خوارزمية MaxCliqueDyn منها. الشفرة الزائفة للخوارزمية هي:

الإجراء MaxClique(R, C) هو Q = Ø، Q _max = Ø بينما R ≠ Ø افعل اختر رأسًا p بلون أقصى C(p) من المجموعة R R := R\{p} إذا كان |Q| + C ( p)>|Q _max | Q := Q ⋃ {p} إذا كان R ⋂ Γ(p) ≠ Ø فإن الحصول على تلوين الرؤوس C' لـ G(R ⋂ Γ(p)) MaxClique(R ⋂ Γ(p), C') أما إذا كانت القيمة المطلقة لـ Q أكبر من القيمة المطلقة لـ Q _max ، فإن Q _max تساوي Q Q := Q\{p} وإلا، ارجع. نهاية الحلقة.

حيث Q هي مجموعة رؤوس الزمرة المتنامية حاليًا، _وQmax هي مجموعة رؤوس أكبر زمرة تم العثور عليها حاليًا، و R هي مجموعة الرؤوس المرشحة، و Γ(p) هي مجموعة جميع الرؤوس المجاورة للرأس p، و C هي مجموعة فئات الألوان المقابلة لها. تبحث خوارزمية MaxClique بشكل متكرر عن أكبر زمرة عن طريق إضافة رؤوس إلى Q وإزالتها منها .

خوارزميات التلوين

خوارزمية التلوين التقريبية

يستخدم MaxClique خوارزمية تلوين تقريبية ^{[ 2 ]} للحصول على مجموعة من فئات الألوان C. في خوارزمية التلوين التقريبية، يتم تلوين الرؤوس واحدًا تلو الآخر بنفس الترتيب الذي تظهر به في مجموعة من الرؤوس المرشحة R ، بحيث إذا كان الرأس التالي p غير مجاور لجميع الرؤوس في نفس فئة اللون، فإنه يُضاف إلى هذه الفئة، وإذا كان p مجاورًا لرأس واحد على الأقل في كل فئة من فئات الألوان الموجودة، فإنه يوضع في فئة لون جديدة.

تُعيد خوارزمية MaxClique الرؤوس R مرتبة حسب ألوانها. الرؤوس $v\in R$ بألوان $C(v)<{|Q_{max}|}-{|Q|}+1$ لا تتم إضافتها أبدًا إلى المجموعة الحالية Q. لذلك، فإن فرز تلك الرؤوس حسب اللون لا يفيد خوارزمية MaxClique.

فرز الألوان

تُحسّن خوارزمية ColorSort خوارزمية التلوين التقريبي من خلال مراعاة الملاحظة المذكورة أعلاه. يتم تعيين كل رأس إلى فئة لونية. $C_{k}$ . لو $k<{|Q_{max}|}-{|Q|}+1$ يتم نقل الرأس إلى المجموعة R (خلف الرأس الأخير في R ). إذا $k\geq {|Q_{max}|}-{|Q|}+1$ ثم يبقى الرأس في $C_{k}$ ولا يتم نقلها إلى R. في النهاية، جميع الرؤوس المتبقية في $C_{k}$ (أين $k\geq {|Q_{max}|}-{|Q|}+1$ تُضاف ) إلى الجزء الخلفي من R كما تظهر في كل $C_{k}$ وبالترتيب التصاعدي بالنسبة للمؤشر $k$ في خوارزمية ColorSort، يتم تخصيص الألوان لهذه الرؤوس فقط $C(v)=k$ .

الشفرة الزائفة لخوارزمية ColorSort هي: ^{[ 1 ]}

الإجراء ColorSort(R, C) هو max_no := 1; k _min := |Q _max | − |Q| + 1; إذا كانت قيمة k _min ≤ 0 فإن قيمة k _min := 1؛ j := 0; C ₁ := Ø; C ₂ := Ø; for i := 0 to |R| − 1 do p := R[i]; {الرأس رقم i في R} k := 1; بينما C _k ⋂ Γ(p) ≠ Ø do k := k+1; إذا كان k > max_no max_no := k; C _{max_no+1} := Ø; end if C _k := C _k ⋃ {p}; if k < k _minthen R[j] := R[i]; j := j+1; نهاية الشرط نهاية الحلقة C[j−1] := 0; for k := k _min to max_no do for i := 1 to |C _k | do R[j] := C _k [i]; C[j] := k; j := j+1; نهاية لنهاية لـ

مثال

يمكن وصف الرسم البياني أعلاه بأنه مجموعة مرشحة من الرؤوس R = {7 ⁽⁵⁾ ، 1 ⁽⁴⁾ ، 4 ⁽⁴⁾ ، 2 ⁽³⁾ ، 3 ⁽³⁾ ، 6 ⁽³⁾ ، 5 ⁽²⁾ ، 8 ⁽²⁾ }، ويمكن استخدامها كمدخل لكل من خوارزمية التلوين التقريبي وخوارزمية فرز الألوان. يمكن استخدام أي من الخوارزميتين لإنشاء الجدول التالي:

ك	سي _ك
1	7 ⁽⁵⁾ ، 5 ⁽²⁾
2	1 ⁽⁴⁾ ، 6 ⁽³⁾ ، 8 ⁽²⁾
3	4 ⁽⁴⁾ ، 2 ⁽³⁾ ، 3 ⁽³⁾

تُعيد خوارزمية التلوين التقريبي مجموعة الرؤوس R = {7 ⁽⁵⁾ , 5 ⁽²⁾ , 1 ⁽⁴⁾ , 6 ⁽³⁾ , 8 ⁽²⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³⁾ } ومجموعة فئات الألوان المقابلة لها C = {1,1,2,2,2,3,3,3}. أما خوارزمية فرز الألوان ColorSort فتُعيد مجموعة الرؤوس R = {7 ⁽⁵⁾ , 1 ⁽⁴⁾ , 6 ⁽³⁾ , 5 ⁽²⁾ , 8 ⁽²⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³⁾ } ومجموعة فئات الألوان المقابلة لها C = {–,–,–,–,–,3,3,3}، حيث يُمثل الرمز – فئة لون غير معروفة مع k < 3.

خوارزمية MaxCliqueDyn

تُوسّع خوارزمية MaxCliqueDyn خوارزمية MaxClique باستخدام خوارزمية ColorSort بدلاً من خوارزمية التلوين التقريبي لتحديد فئات الألوان. في كل خطوة من خطوات MaxClique، تُعيد خوارزمية MaxCliqueDyn حساب درجات الرؤوس في R بالنسبة للرأس الذي تعمل عليه الخوارزمية حاليًا. ثم تُرتّب هذه الرؤوس تنازليًا وفقًا لدرجاتها في الرسم البياني G(R) . بعد ذلك، تُراعي خوارزمية ColorSort الرؤوس في R مُرتّبة حسب درجاتها في الرسم البياني المُستحث G(R) بدلاً من G. وبذلك، يُقلّل عدد الخطوات اللازمة لإيجاد الزمرة القصوى إلى الحد الأدنى. مع ذلك، لا يتحسّن وقت التشغيل الإجمالي لخوارزمية MaxClique، نظرًا للتكلفة الحسابية. $O(|R|^{2})$ يبقى تحديد درجات وفرز الرؤوس في R كما هو.

الشفرة الزائفة لخوارزمية MaxCliqueDyn هي: ^{[ 1 ]}

الإجراء MaxCliqueDyn(R, C, level) هو S[level] := S[level] + S[level−1] − S _old [level]; S _old [level] := S[level−1]; بينما R ≠ Ø افعل اختر رأسًا p مع أقصى قيمة لـ C(p) (الرأس الأخير) من R؛ R := R\{p}; إذا كان |Q| + C[مؤشر p في R] > | Q _max | Q := Q ⋃ {p}; إذا كان R ⋂ Γ(p) ≠ Ø، فإذا كان S[level]/ALL STEPS < T _limit، احسب درجات الرؤوس في G(R ⋂ Γ(p)); رتب الرؤوس في R ⋂ Γ(p) بترتيب تنازلي فيما يتعلق بدرجاتهم؛ نهاية الشرط ColorSort(R ⋂ Γ(p), C') S[level] := S[level] + 1; جميع الخطوات := جميع الخطوات + 1؛ MaxCliqueDyn(R ⋂ Γ(p), C', المستوى + 1); وإلا إذا كانت |Q| > |Q _max | فإن Q _max := Q; Q := Q\{p}; وإلا، ارجع. نهاية الحلقة.

يمكن تحديد قيمة _الحدT من خلال التجربة على رسوم بيانية عشوائية. وقد تبين في المقالة الأصلية أن الخوارزمية تعمل بشكل أفضل عند _قيمةT = 0.025.

مراجع

1 2 3 4 يانيز كونك؛ دوسانكا يانيزيتش (2007). "خوارزمية محسّنة للتفرع والتقييد لمسألة الزمرة القصوى" (ملف PDF) . مجلة MATCH للاتصالات في الرياضيات والكيمياء الحاسوبية . 58 (3): 569-590 .شفرة المصدر
1 2 توميتا، إتسوجي؛ سيكي، توموكازو (2003). "خوارزمية فعّالة للتفرع والتقييد لإيجاد زمرة قصوى" (ملف PDF) . في: كالود، سي إس؛ دينين، إم جيه؛ فاجنوفسكي، في (محررون). DMTCS 2003. LNCS. الصفحات 278-289 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 11 سبتمبر 2016. انظر أيضًا: إي. توميتا؛ تي. سيكي (2007). "خوارزمية فعّالة للتفرع والتقييد لإيجاد زمرة قصوى". مجلة التحسين العالمي . 37 : 95-111 . doi : 10.1007/s10898-006-9039-7 .

[Konc2007-1] 1 2 3 4 يانيز كونك؛ دوسانكا يانيزيتش (2007). "خوارزمية محسّنة للتفرع والتقييد لمسألة الزمرة القصوى" (ملف PDF) . مجلة MATCH للاتصالات في الرياضيات والكيمياء الحاسوبية . 58 (3): 569-590 .شفرة المصدر

[Tomita2003-2] 1 2 توميتا، إتسوجي؛ سيكي، توموكازو (2003). "خوارزمية فعّالة للتفرع والتقييد لإيجاد زمرة قصوى" (ملف PDF) . في: كالود، سي إس؛ دينين، إم جيه؛ فاجنوفسكي، في (محررون). DMTCS 2003. LNCS. الصفحات 278-289 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 11 سبتمبر 2016. انظر أيضًا: إي. توميتا؛ تي. سيكي (2007). "خوارزمية فعّالة للتفرع والتقييد لإيجاد زمرة قصوى". مجلة التحسين العالمي . 37 : 95-111 . doi : 10.1007/s10898-006-9039-7 .

[ ١ ]

[ 2 ]

اللغة	العربية (RTL)
روابط موسوعية	6 رابطاً
المصدر الأصلي	ويكيبيديا ↗