นักพัฒนา:	อินซิลาบ (สถาบันเคมีแห่งชาติสโลวีเนีย)
สถานะการพัฒนา:	คล่องแคล่ว
เขียนด้วยภาษา:	ซี++
พิมพ์:	ทฤษฎีกราฟ , อัลกอริทึมคลิกสูงสุด , ปัญหาคลิก
ใบอนุญาต:	ใบอนุญาตสาธารณะทั่วไปของ GNU
เว็บไซต์:	insilab.org/maxclique/​​​

อัลกอริทึม MaxCliqueDynเป็นอัลกอริทึม สำหรับค้นหา คลิกสูงสุดในกราฟแบบไม่มีทิศทาง

MaxCliqueDyn พัฒนามาจากอัลกอริทึม MaxClique ซึ่งใช้ในการค้นหาคลิกสูงสุดที่มีขนาดจำกัด โดยใช้ อัลกอริทึมการระบายสีเพื่อหาขอบเขตนั้นMaxCliqueDyn ขยายขีดความสามารถของ MaxClique ให้ครอบคลุมถึงขอบเขตที่เปลี่ยนแปลงได้แบบไดนามิก

อัลกอริทึมนี้ได้รับการออกแบบโดยJanez Koncและคำอธิบายได้รับการตีพิมพ์ในปี 2550 ^{[ 1 ]}เมื่อเปรียบเทียบกับอัลกอริทึมก่อนหน้านี้ MaxCliqueDyn มีอัลกอริทึมการระบายสีที่ได้รับการปรับปรุง (ColorSort) และใช้ขอบเขตบนที่แน่นกว่าและมีค่าใช้จ่ายด้านการคำนวณสูงกว่ากับพื้นที่การค้นหาเพียงบางส่วน^{[ 1 ]}การปรับปรุงทั้งสองอย่างช่วยลดเวลาในการค้นหาคลิกสูงสุด นอกจากการลดเวลาแล้ว อัลกอริทึมการระบายสีที่ได้รับการปรับปรุงยังช่วยลดจำนวนขั้นตอนที่จำเป็นในการค้นหาคลิกสูงสุดอีกด้วย

อัลกอริทึม 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ที่เรียงลำดับตามสี จุดยอดที่มีสีจะไม่ถูกเพิ่มเข้าไปในกลุ่มย่อย  Q ปัจจุบัน ดังนั้น การเรียงลำดับจุดยอดเหล่านั้นตามสีจึงไม่มีประโยชน์สำหรับอัลกอริทึม MaxClique ${\displaystyle v\in R}$${\displaystyle C(v)<{|Q_{max}|}-{|Q|}+1}$

อัลกอริทึม ColorSort ปรับปรุงอัลกอริทึมการระบายสีโดยประมาณโดยคำนึงถึงข้อสังเกตข้างต้น จุดยอดแต่ละจุดจะถูกกำหนดให้กับกลุ่มสีถ้าจุดยอดนั้นจะถูกย้ายไปยังเซต  R (อยู่หลังจุดยอดสุดท้ายใน  R ) ถ้าจุดยอดนั้นจะยังคงอยู่ในเซตและจะไม่ถูกย้ายไปยัง  Rในตอนท้าย จุดยอดทั้งหมดที่เหลืออยู่ในเซต(โดยที่) จะถูกเพิ่มเข้าไปด้านหลังของ  Rตามลำดับที่ปรากฏในแต่ละเซตและเรียงลำดับจากน้อยไปมากตามดัชนี  ในอัลกอริทึม ColorSort จะมีการกำหนด สี ให้กับจุดยอดเหล่านี้เท่านั้น${\displaystyle C_{k}}$${\displaystyle k<{|Q_{max}|}-{|Q|}+1}$${\displaystyle k\geq {|Q_{max}|}-{|Q|}+1}$${\displaystyle C_{k}}$${\displaystyle C_{k}}$${\displaystyle k\geq {|Q_{max}|}-{|Q|}+1}$${\displaystyle C_{k}}$${\displaystyle k}$${\displaystyle 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 1  := Ø; C 2  := Ø; สำหรับ i := 0 ถึง |R| − 1 ทำ 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 min then R[j] := R[i]; j := j+1; จบถ้าจบสำหรับ C[j−1] := 0; สำหรับ k := k minถึง max_no ทำซ้ำสำหรับ i := 1 ถึง |C k | ทำซ้ำ R[j] := C k [i]; C[j] := k; j := j+1; ต่อ ต่อต่อ สำหรับ

ตัวอย่าง

กราฟด้านบนสามารถอธิบายได้ว่าเป็นเซตของจุดยอดที่เป็นไปได้R  = {7 ⁽⁵⁾ , 1 ⁽⁴⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³ ) , 6 ⁽³⁾ , 5 ⁽²⁾ , 8 ⁽²⁾ } และใช้เป็นอินพุตสำหรับทั้งอัลกอริทึมการระบายสีโดยประมาณและอัลกอริทึม ColorSort อัลกอริทึมใดก็ได้สามารถใช้สร้างตารางต่อไปนี้ได้:

อัลกอริทึมการระบายสีโดยประมาณจะส่งคืนเซตของจุดยอดR  = {7 ⁽⁵⁾ , 5 ( ^{2 )} , 1 ⁽⁴⁾ , 6 ⁽³⁾ , 8 (2 ⁾ , 4 (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 พัฒนาต่อยอดจากอัลกอริทึม MaxClique โดยใช้อัลกอริทึม ColorSort แทนอัลกอริทึมการระบายสีโดยประมาณในการกำหนดคลาสสี ในแต่ละขั้นตอนของ MaxClique อัลกอริทึม MaxCliqueDyn จะคำนวณดีกรีของจุดยอดในRใหม่โดยอ้างอิงจากจุดยอดที่อัลกอริทึมกำลังทำงานอยู่ จากนั้นจุดยอดเหล่านี้จะถูกเรียงลำดับจากมากไปน้อยตามดีกรีในกราฟG(R)จากนั้นอัลกอริทึม ColorSort จะพิจารณาจุดยอดในRที่เรียงลำดับตามดีกรีในกราฟG(R) ที่สร้างขึ้น แทนที่จะเป็นในGด้วยวิธีนี้ จำนวนขั้นตอนที่จำเป็นในการค้นหาคลิกสูงสุดจะลดลงเหลือน้อยที่สุด ถึงกระนั้น เวลาการทำงานโดยรวมของอัลกอริทึม MaxClique ก็ไม่ได้ดีขึ้น เนื่องจากค่าใช้จ่ายในการคำนวณสำหรับการกำหนดดีกรีและการเรียงลำดับจุดยอดในRยังคงเท่าเดิม ${\displaystyle O(|R|^{2})}$

รหัสเทียมของอัลกอริทึม MaxCliqueDyn คือ: ^{[ 1 ]}

ขั้นตอน MaxCliqueDyn(R, C, level) คือ S[level] := S[level] + S[level−1] − S old [level]; S old [ระดับ] := S[ระดับ−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[ระดับ] := S[ระดับ] + 1; ทุกขั้นตอน := ทุกขั้นตอน + 1; MaxCliqueDyn(R ⋂ Γ(p), C', ระดับ + 1); มิฉะนั้น ถ้า |Q| > |Q max | แล้ว Q max  := Q; Q := Q\{p}; มิฉะนั้นให้ส่งคืนค่าสิ้นสุดในขณะที่

ค่า_{ขีดจำกัด}Tสามารถกำหนดได้โดยการทดลองกับกราฟแบบสุ่ม ในบทความต้นฉบับพบว่าอัลกอริทึมทำงานได้ดีที่สุดเมื่อ_{ค่าขีดจำกัด}T  เท่ากับ 0.025