ขั้นตอนวิธีโบรน-เคอร์โบสท์

ขั้นตอนวิธีโบรน-เคอร์โบสท์ (อังกฤษ: Bron–Kerbosch algorithm) เป็นขั้นตอนวิธีการหากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟไม่ระบุทิศทาง (undirected graph) ซึ่งก็คือการระบุสับเซตทั้งหมดของจุดยอด (vertex) ประกอบด้วยคุณสมบัติสองประการคือ แต่ละคู่ของจุดยอดของสับเซตที่ถูกระบุแต่ละครั้งจะต้องถูกเชื่อมโดยเส้นเชื่อมเสมอและ ไม่มีสับเซตใดที่จะมีจุดยอดเพิ่มเติมถูกเพิ่มเข้าไปในสับเซตขณะที่มันเป็นการเชื่อมต่อที่บริบูรณ์ (complete connectivity) ขั้นตอนวิธีโบรน-เคอร์โบสท์ ถูกออกแบบโดย แยป เคอร์โบสท์ และ แคนรีด โบรน สองนักวิทยาศาสตร์ชาวดัตช์ ซึ่งตีพิมพ์เรื่องนี้ในปี ค.ศ.1973 แม้ว่าขั้นตอนวิธีอื่นๆ สำหรับการแก้ปัญหากลุ่มพรรคพวก (clique problem) จะมีเวลาการทำงานดีกว่าในทางทฤษฎีสำหรับข้อมูลขาเข้าที่เป็นเซตอิสระขนาดใหญ่สุด (maximal independent set) จำนวนน้อยๆ แต่ขั้นตอนวิธีโบรน-เคอร์โบสท์ และการปรับปรุงจากขั้นตอนวิธีนี้ถูกรายงานบ่อยครั้งว่ามีประสิทธิภาพดีกว่าแบบอื่นๆ ในทางปฏิบัติ ขั้นตอนวิธีนี้มีชื่อเสียงและถูกนำไปใช้อย่างกว้างขวางในการใช้งานที่ต้องใช้ขั้นตอนวิธีเกี่ยวกับกราฟ เช่น เคมีการคำนวณ (computational chemistry)
ขั้นตอนวิธีที่เกิดขึ้นในช่วงเดียวกันของอัคโคยันลู (Akkoyunlu) ในปี ค.ศ.1973 ซึ่งแม้ว่าอาจจะถูกนำเสนอในรูปแบบที่ต่างออกไป แต่ก็จะมีลักษณะที่เหมือนกับขั้นตอนวิธีโบรน-เคอร์โบสท์ เมื่อถูกสร้างเป็นต้นไม้ค้นหาแบบเวียนเกิดที่เหมือนกัน

แบบไม่มีแกนหลัก

รูปแบบพื้นฐานของขั้นตอนวิธีโบรน-เคอร์โบสท์ คือขั้นตอนวิธีการย้อนรอยแบบเวียนเกิด (recursive backtracking) ที่ค้นหากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟ G โดยทั่วไป กำหนดให้มีสามเซต R P และ X แล้วมันจะทำการหากลุ่มพรรคพวกที่ใหญ่ที่สุด ที่มีทุกจุดยอดอยู่ใน R บางจุดยอดใน P และไม่มีจุดยอดใดเลยในเซต X โดยภายในการเรียกการเวียนเกิด เซต P และ X จะถูกจำกัดไว้สำหรับจุดยอดที่สร้างเป็นกลุ่มพรรคพวกเมื่อถูกรวมเข้ากับเซต R ซึ่งจุดยอดเหล่านี้เท่านั้นที่จะถูกใช้เป็นส่วนหนึ่งของข้อมูลขาออก หรือป้องกันกลุ่มพรรคพวกบางกลุ่มที่จะถูกนำไปเป็นข้อมูลขาออก
การเวียนเกิดนี้เริ่มต้นโดยกำหนดให้เซต R และ X เป็นเซตว่าง และให้ P เป็นเซตของจุดยอดของกราฟ โดยภายในการเรียกการเวียนเกิดแต่ละครั้ง จะมีการพิจารณาจุดยอดใน P ถ้าไม่มีจุดยอดใดๆเลย ก็จะให้ R เป็นกลุ่มพรรคพวกที่ใหญ่ที่สุด (ในกรณีที่ X เป็นเซตว่าง) หรือให้ย้อนรอย สำหรับแต่ละจุดยอด v ที่ถูกเลือกจาก P มันจะทำการเรียกการเวียนเกิด ซึ่ง v ถูกเพิ่มเข้าไปใน R และ P กับ X ถูกจำกัดไว้สำหรับเพื่อนบ้านของ v เขียนว่า N(v) ซึ่งจะหาและรายงานส่วนเพิ่มของกลุ่มพรรคพวกของ R ซึ่งประกอบด้วย v หลังจากนั้นจะทำการย้าย v จาก P ไปยัง X และทำต่อไปเรื่อยๆ กับจุดยอดต่อไปใน P
รหัสเทียมของขั้นตอนวิธีสามารถเขียนได้ดังนี้

    BronKerbosch1(R,P,X):
        ถ้า P และ X เป็นเซตว่างทั้งคู่:
            รายงานว่า R เป็นกลุ่มพรรคพวกที่ใหญ่ที่สุด
        สำหรับทุกๆจุดยอด v ในเซต P:
            BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
            P := P \ {v}
            X := X ⋃ {v}

แบบมีแกนหลัก

รูปแบบพื้นฐานของขั้นตอนวิธีดังที่ได้อธิบายข้างต้น จะไม่มีประสิทธิภาพในกรณีที่กราฟมีกลุ่มพรรคพวกที่ไม่ได้ใหญ่ที่สุดอยู่จำนวนมาก มันจะทำให้เกิดการเรียกการเวียนเกิดทุกกลุ่มพรรคพวก ไม่ว่าจะใหญ่ที่สุดหรือไม่ก็ตาม เพื่อที่จะประหยัดเวลาและให้ขั้นตอนวิธีดังกล่าวย้อนรอยได้อย่างรวดเร็วในแขนงของต้นไม้ค้นหาที่ไม่มีพรรคพวกที่ใหญ่ที่สุดอยู่ โบรนและเคอร์โบสท์ได้นำเสนอขั้นตอนวิธีที่ต่างออกไปเกี่ยวกับ จุดยอดแกนหลัก (pivot vertex) u ซึ่งถูกเลือกจาก P (หรือกล่าวโดยทั่วไปคือ จาก P ⋃ X) กลุ่มพรรคพวกที่ใหญ่ที่สุดใดๆ ต้องประกอบด้วย u หรือ จุดยอดหนึ่งที่ไม่ใช่เพื่อนบ้านของ u นอกนั้น กลุ่มพรรคพวกสามารถที่จะขยายโดยเพิ่ม u เข้าไป ดังนั้น เฉพาะ u และจุดยอดที่ไม่ใช่เพื่อนบ้านของมันต้องถูกทดสอบเพื่อเป็นตัวเลือกสำหรับจุดยอด v ที่จะถูกรวมเข้ากับ R ในแต่ละครั้งของการเรียกการเวียนเกิด ในรหัสเทียมถ้าแกนหลัก (pivot) ถูกเลือกเพื่อลดจำนวนการเรียกการเวียนเกิดให้เหลือน้อยที่สุดแล้ว จะลดเวลาการทำงานลงได้มากเมื่อเทียบกับแบบไม่ใช้แกนหลัก

รหัสเทียมแสดงขั้นตอนวิธีโบรน-เคอร์โบสท์แบบมีแกนหลัก

    BronKerbosch2(R,P,X):
        ถ้า P และ X เป็นเซตว่างทั้งคู่:
            รายงานว่า R เป็นกลุ่มพรรคพวกที่ใหญ่ที่สุด
        เลือกแกนหลักเป็นจุดยอด u ใน P U X
        สำหรับทุกๆจุดยอด v ใน P \ N(u):
            BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
            P := P \ {v}
            X := X ⋃ {v}

แบบมีการลำดับจุดยอด

เป็นอีกวิธีสำหรับการปรับปรุงรูปแบบพื้นฐานของขั้นตอนวิธีโบรน-เคอร์โบสท์เกี่ยวกับการไม่เลือกแกนหลักที่ชั้นนอกสุดของการเวียนเกิด และเลือกลำดับของการเรียกการเวียนเกิดแทนเพื่อพยายามลดขนาดของเซต P ที่เป็นตัวแทนของจุดยอดภายในแต่ละการเรียกการเวียนเกิดแต่ละรอบลงให้มากที่สุด
ความเสื่อม (degeneracy) ของกราฟ G คือจำนวนที่น้อยที่สุดที่ทุกกราฟย่อย (subgraph) ของ G มีจุดยอดที่มีระดับขั้น d หรือน้อยกว่า ในทุกกราฟจะมีการลำดับความเสื่อม ซึ่งเป็นการลำดับของจุดยอดที่แต่ละจุดยอดจะมีเพื่อนบ้านจำนวน d หรือน้อยกว่า ซึ่งมาทีหลังในการลำดับ การลำดับความเสื่อมอาจถูกพบได้ในเวลาเป็นเชิงเส้นโดยการเลือกจุดยอดที่มีระดับขั้นต่ำสุดในจุดยอดที่เหลืออยู่ซ้ำๆ ถ้าลำดับของจุดยอด v ซึ่งขั้นตอนวิธีโบรน-เคอร์โบสท์ได้วงวนผ่านไป เป็นลำดับความเสื่อมแล้ว เซต P ของตัวแทนจุดยอดในแต่ละการเรียก (เพื่อนบ้านของ v ซึ่งมาทีหลังในการลำดับ) จะรับประกันว่าจะใช้ขนาดอย่างมาก d เซต X ซึ่งเก็บจุดยอดที่ถูกแยกออกมาจะประกอบด้วยเพื่อนบ้านก่อนหน้านี้ของ v และอาจจะใหญ่กว่า d ในการเรียกการเวียนเกิดในขั้นตอนวิธีนี้ชั้นของการเวียนเกิดที่อยู่ต่ำกว่าชั้นบนสุดยังคงต้องใช้แบบมีแกนหลักอยู่

รหัสเทียมของขั้นตอนวิธีนี้มีดังต่อไปนี้

    BronKerbosch3(G):
        P = V(G)
        R = X = เป็นเซตว่าง
        สำหรับทุกๆจุดยอด v ในการลำดับความเสื่อมของ G:
            BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
            P := P \ {v}
            X := X ⋃ {v}
ขั้นตอนวิธีดังกล่าวถูกพิสูจน์แล้วว่ามีประสิทธิภาพสำหรับกราฟที่มีความเสื่อมน้อยๆ และจากการทดลองแสดงให้เห็นว่ามันทำงานได้ดีในทางปฏิบัติกับเครือข่ายสังคมขนาดใหญ่แบบเบาบาง (sparse social networks) และกราฟอื่นๆ ในโลกแห่งความเป็นจริง

ตัวอย่าง

ในกราฟตัวอย่างที่ได้แสดง จะเริ่มขั้นตอนวิธีจากการกำหนดให้ R = Ø P = {1,2,3,4,5,6} และ X = Ø โดยแกนหลัก u ควรถูกเลือกจากหนึ่งในจุดยอดที่มีระดับขั้นเป็นสามเพื่อที่จะลดการเรียกการเวียนเกิดลง ยกตัวอย่างเช่น สมมติให้ u คือจุดยอด 2 หลังจากนั้นก็จะมีสามจุดยอดเหลืออยู่ใน P \ N(u) คือจุดยอด 2, 4, และ 6
การวนซ้ำของวงวนชั้นในของขั้นตอนวิธีสำหรับเมื่อ v = 2 ทำการเรียกการเวียนเกิดเมื่อ R = {2} P = {1,3,5} and X = Ø ภายในการเรียกการเวียนเกิดนี้ หนึ่งใน 1 หรือ 5 จะถูกเลือกเป็นแกนหลัก และจะมีการเรียกการเวียนเกิดในระดับที่สอง 2 ครั้ง ครั้งแรกสำหรับจุดยอด 3 และอีกครั้งสำหรับจุดยอดที่ไม่ได้ถูกเลือกเป็นแกนหลัก ในท้ายที่สุดแล้วการเรียกทั้งสองครั้งนี้จะรายงาน 2 กลุ่มพรรคพวกคือ {1,2,5} และ {2,3} หลังจากการคืนการทำงานจากการเรียกเหล่านี้แล้ว จุดยอด 2 จะถูกเพิ่มเข้าไปใน X และถูกลบจาก P
การวนซ้ำของวงวนชั้นในของขั้นตอนวิธีสำหรับเมื่อ v = 4 ทำการเรียกการเวียนเกิดเมื่อ R = {4} P = {3,5,6} and X = Ø (แม้ว่าจุดยอด 2 เป็นของเซต X ในการเรียกชั้นนอก มันก็ไม่ใช่เพื่อนบ้านของ v และถูกแยกออกจากสับเซตของ X ผ่านการเรียกการเวียนเกิด) การเรียกครั้งนี้จะจบลงด้วยการเรียกการเวียนเกิดระดับที่สอง อีก 3 ครั้ง ซึ่งจะรายงาน 3 กลุ่มพรรคพวกคือ {3,4}, {4,5} และ {4,6} หลังจากนั้นจุดยอด 4 จะถูกเพิ่มเข้าไปใน X และถูกลบจาก P
ในการวนซ้ำครั้งที่สามและครั้งสุดท้ายของวงวนชั้นในสำหรับเมื่อ v = 6 ทำการเรียกการเวียนเกิดเมื่อ R = {6} P = Ø and X = {4} เนื่องจากการเรียกครั้งนี้ P ว่างเปล่าแล้ว และ X ไม่ว่างเปล่า มันจะทำการย้อนรอยในทันทีโดยไม่รายงานกลุ่มพรรคพวกอื่นๆอีก เพราะมันไม่สามารถมีกลุ่มพรรคพวกที่ใหญ่ที่สุดที่ประกอบด้วยจุดยอด 6 และไม่มีจุดยอด 4 ประกอบอยู่

ดังนั้นต้นไม้การเรียกของขั้นตอนวิธีดังกล่าวจะมีลักษณะดังนี้

   BronKerbosch2(Ø, {1,2,3,4,5,6}, Ø)
       BronKerbosch2({2}, {1,3,5}, Ø)
           BronKerbosch2({2,3}, Ø, Ø): ให้ผลลัพธ์ {2, 3}
           BronKerbosch2({2,5}, {1}, Ø)
               BronKerbosch2({1,2,5}, Ø, Ø): ให้ผลลัพธ์ {1,2,5}
       BronKerbosch2({4}, {3,5,6}, Ø)
           BronKerbosch2({3,4}, Ø, Ø): ให้ผลลัพธ์ {3,4}
           BronKerbosch2({4,5}, Ø, Ø): ให้ผลลัพธ์ {4,5}
           BronKerbosch2({4,6}, Ø, Ø): ให้ผลลัพธ์ {4,6}
       BronKerbosch2({6}, Ø, {4}): ไม่ให้ผลลัพธ์
กราฟในตัวอย่างมีความเสื่อมเป็น 2 ซึ่งหนึ่งในการลำดับที่เป็นไปได้คือ 6,4,3,1,2,5 ถ้าเป็นแบบที่มีการลำดับจุดยอดของขั้นตอนวิธีโบรน-เคอร์โบสท์ จะได้ต้นไม้ของการเรียกเป็นดังนี้

   BronKerbosch3(G)
       BronKerbosch2({6}, {4}, Ø)
           BronKerbosch2({6,4}, Ø, Ø): ให้ผลลัพธ์ {6,4}
       BronKerbosch2({4}, {3,5}, {6})
           BronKerbosch2({4,3}, Ø, Ø): ให้ผลลัพธ์ {4,3}
           BronKerbosch2({4,5}, Ø, Ø): ให้ผลลัพธ์ {4,5}
       BronKerbosch2({3}, {2}, {4})
           BronKerbosch2({3,2}, Ø, Ø): ให้ผลลัพธ์ {3,2}
       BronKerbosch2({1}, {2,5}, Ø)
           BronKerbosch2({1,2}, {5}, Ø)
               BronKerbosch2({1,2,5}, Ø, Ø): ให้ผลลัพธ์ {1,2,5}
       BronKerbosch2({2}, {5}, {1,3}): ไม่ให้ผลลัพธ์
       BronKerbosch2({5}, Ø, {1,2,4}): ไม่ให้ผลลัพธ์

การวิเคราะห์เวลาการทำงานในกรณีแย่สุด

ขั้นตอนวิธีโบรน-เคอร์โบสท์ ไม่ใช่ขั้นตอนวิธีที่ปริมาณข้อมูลส่งออกมีผลต่อเวลาการทำงาน (output-sensitive algorithm) ไม่เหมือนกับขั้นตอนวิธีอื่นๆ สำหรับปัญหาการหากลุ่มพรรคพวก มันไม่ได้ทำงานเป็นเวลาแบบพหุนาม (polynomial time) ต่อกลุ่มพรรคพวกที่ใหญ่ที่สุดที่ถูกสร้างขึ้น อย่างไรก็ตามมันมีประสิทธิภาพในกรณีแย่สุด โดยจากผลของ มูนและมูสเซอร์ (ค.ศ.1965) กราฟที่มีจุดยอด n จุดยอดใดๆ จะมีกลุ่มพรรคพวกที่ใหญ่ที่สุดอย่างมาก 3ⁿ/3 กลุ่ม และมีเวลาการทำงานในกรณีแย่สุด (โดยใช้แบบมีแกนหลักที่จะลดจำนวนการเรียกการเวียนเกิดให้เหลือน้อยที่สุดในแต่ละขั้นตอน) เป็น O(3ⁿ/3)
สำหรับกราฟเบาบาง (sparse graph) การทำให้ขอบเขตแคบลงนั้นเป็นไปได้ โดยเฉพาะแบบมีการลำดับจุดยอดสามารถทำงานได้ภายในเวลา O(dn3ᵈ/3) เมื่อ d เป็นความเสื่อมของกราฟซึ่งเป็นการบ่งบอกถึงความเบาบางของกราฟ กราฟใดๆ ที่มีความเสื่อมเป็น d ซึ่งทำให้ผลรวมของจำนวนกลุ่มพรรคพวกที่ใหญ่ที่สุดเป็น (n - d)3ᵈ/3 จะทำให้ขอบเขตแคบมาก

ความรู้เพิ่มเติมเกี่ยวกับขั้นตอนวิธี

กลุ่มพรรคพวกที่ใหญ่ที่สุด (maximal clique) คือ กลุ่มพรรคพวกที่ไม่สามารถขยายได้โดยการเพิ่มจุดยอดที่ติดกันไปอีกหนึ่งจุดหรือมากกว่านั้นอีกแล้ว ซึ่งหมายความว่าจะไม่มีกลุ่มพรรคพวกที่ปรากฏในเซตของจุดยอดของกลุ่มพรรคพวกที่ใหญ่กว่านี้อีก โดยในวงการวิทยาศาสตร์คอมพิวเตอร์ ขั้นตอนวิธีดังกล่าวเป็นปัญหาในการหากลุ่มพรรคพวกที่ใหญ่ที่สุดจัดเป็นปัญหากลุ่มพรรคพวก ปัญหากลุ่มพรรคพวกถือว่าเป็นปัญหาเอ็นพีบริบูรณ์ (NP-complete) ซึ่งเป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี ทำการควบคุมตัวแปรคงที่ได้ยากและยากที่จะประมาณค่า โดยเวลาการทำงานของขั้นตอนวิธีประเภทนี้จะใช้เวลาการทำงานเป็นแบบยกกำลัง (exponential) ซึ่งถือว่าช้ามาก

ปัญหาที่เกี่ยวข้อง

ปัญหากลุ่มพรรคพวก