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

ขั้นตอนวิธีโบรน-เคอร์โบสท์ (อังกฤษ: 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) และกราฟอื่น ๆ ในโลกแห่งความเป็นจริง

ตัวอย่าง

 

กราฟที่มีกลุ่มพรรคพวกที่ใหญ่ที่สุด 5 กลุ่ม ประกอบด้วย 4 เส้นเชื่อมและ 1 สามเหลี่ยม

ในกราฟตัวอย่างที่ได้แสดง จะเริ่มขั้นตอนวิธีจากการกำหนดให้ 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^n/3 กลุ่ม และมีเวลาการทำงานในกรณีแย่สุด (โดยใช้แบบมีแกนหลักที่จะลดจำนวนการเรียกการเวียนเกิดให้เหลือน้อยที่สุดในแต่ละขั้นตอน) เป็น O(3^n/3)

สำหรับกราฟเบาบาง (sparse graph) การทำให้ขอบเขตแคบลงนั้นเป็นไปได้ โดยเฉพาะแบบมีการลำดับจุดยอดสามารถทำงานได้ภายในเวลา O(dn 3^d/3) เมื่อ d เป็นความเสื่อมของกราฟซึ่งเป็นการบ่งบอกถึงความเบาบางของกราฟ กราฟใด ๆ ที่มีความเสื่อมเป็น d ซึ่งทำให้ผลรวมของจำนวนกลุ่มพรรคพวกที่ใหญ่ที่สุดเป็น (n - d )3^d/3 จะทำให้ขอบเขตแคบมาก

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

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

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

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

อ้างอิง

• Akkoyunlu, E. A. (1973), "The enumeration of maximal cliques of large graphs", SIAM Journal on Computing, 2: 1–6, doi:10.1137/0202001.
• Chen, Lingran (2004), "Substructure and maximal common substructure searching", ใน Bultinck, Patrick (บ.ก.), Computational Medicinal Chemistry for Drug Discovery, CRC Press, pp. 483–514, ISBN 9780824747749.
• Bron, Coen; Kerbosch, Joep (1973), "Algorithm 457: finding all cliques of an undirected graph", Commun. ACM, ACM, 16 (9): 575–577, doi:10.1145/362342.362367.
• Cazals, F.; Karande, C. (2008), "A note on the problem of reporting maximal cliques" (PDF), Theoretical Computer Science, 407 (1): 564–568, doi:10.1016/j.tcs.2008.05.010.
• Eppstein, David; Löffler, Maarten; Strash, Darren (2010), "Listing all maximal cliques in sparse graphs in near-optimal time", ใน Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (บ.ก.), 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, Lecture Notes in Computer Science, 6506, Springer-Verlag, pp. 403–414, arXiv:1006.5440, doi:10.1007/978-3-642-17517-6_36.
• Eppstein, David; Strash, Darren (2011), "Listing all maximal cliques in large sparse real-world graphs", 10th International Symposium on Experimental Algorithms, arXiv:1103.0318.
• Johnston, H. C. (1976), "Cliques of a graph—variations on the Bron–Kerbosch algorithm", International Journal of Parallel Programming, 5 (3): 209–238, doi:10.1007/BF00991836.
• Koch, Ina (2001), "Enumerating all connected maximal common subgraphs in two graphs", Theoretical Computer Science, 250 (1–2): 1–30, doi:10.1016/S0304-3975(00)00286-3.
• Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel J. Math., 3: 23–28, doi:10.1007/BF02760024, MR0182577.
• Tomita, Etsuji; Tanaka, Akira; Takahashi, Haruhisa (2006), "The worst-case time complexity for generating all maximal cliques and computational experiments", Theoretical Computer Science, 363 (1): 28–42, doi:10.1016/j.tcs.2006.06.015.

แหล่งข้อมูลอื่น

• Bron-Kerbosh algorithm implementation in Python
• Finding all cliques of an undirected graph. Seminar notes by Michaela Regneri, January 11, 2007.