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

ขั้นตอนวิธีโบรน-เคอร์โบสท์  เป็นขั้นตอนวิธีการหากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟไม่ระบุทิศทาง (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"
รหัสเทียมของขั้นตอนวิธีสามารถเขียนได้ดังนี้
แบบมีแกนหลัก.
รูปแบบพื้นฐานของขั้นตอนวิธีดังที่ได้อธิบายข้างต้น จะไม่มีประสิทธิภาพในกรณีที่กราฟมีกลุ่มพรรคพวกที่ไม่ได้ใหญ่ที่สุดอยู่จำนวนมาก มันจะทำให้เกิดการเรียกการเวียนเกิดทุกกลุ่มพรรคพวก ไม่ว่าจะใหญ่ที่สุดหรือไม่ก็ตาม เพื่อที่จะประหยัดเวลาและให้ขั้นตอนวิธีดังกล่าวย้อนรอยได้อย่างรวดเร็วในแขนงของต้นไม้ค้นหาที่ไม่มีพรรคพวกที่ใหญ่ที่สุดอยู่ โบรนและเคอร์โบสท์ได้นำเสนอขั้นตอนวิธีที่ต่างออกไปเกี่ยวกับ จุดยอดแกนหลัก (pivot vertex) "u" ซึ่งถูกเลือกจาก "P" (หรือกล่าวโดยทั่วไปคือ จาก "P" ⋃&hairsp;"X"&hairsp;) กลุ่มพรรคพวกที่ใหญ่ที่สุดใด ๆ ต้องประกอบด้วย "u" หรือ จุดยอดหนึ่งที่ไม่ใช่เพื่อนบ้านของ "u" นอกนั้น กลุ่มพรรคพวกสามารถที่จะขยายโดยเพิ่ม "u" เข้าไป ดังนั้น เฉพาะ "u" และจุดยอดที่ไม่ใช่เพื่อนบ้านของมันต้องถูกทดสอบเพื่อเป็นตัวเลือกสำหรับจุดยอด "v" ที่จะถูกรวมเข้ากับ "R" ในแต่ละครั้งของการเรียกการเวียนเกิด ในรหัสเทียมถ้าแกนหลัก (pivot) ถูกเลือกเพื่อลดจำนวนการเรียกการเวียนเกิดให้เหลือน้อยที่สุดแล้ว จะลดเวลาการทำงานลงได้มากเมื่อเทียบกับแบบไม่ใช้แกนหลัก
รหัสเทียมแสดงขั้นตอนวิธีโบรน-เคอร์โบสท์แบบมีแกนหลัก
แบบมีการลำดับจุดยอด.
เป็นอีกวิธีสำหรับการปรับปรุงรูปแบบพื้นฐานของขั้นตอนวิธีโบรน-เคอร์โบสท์เกี่ยวกับการไม่เลือกแกนหลักที่ชั้นนอกสุดของการเวียนเกิด และเลือกลำดับของการเรียกการเวียนเกิดแทนเพื่อพยายามลดขนาดของเซต "P" ที่เป็นตัวแทนของจุดยอดภายในแต่ละการเรียกการเวียนเกิดแต่ละรอบลงให้มากที่สุด
ความเสื่อม (degeneracy) ของกราฟ "G" คือจำนวนที่น้อยที่สุดที่ทุกกราฟย่อย (subgraph) ของ "G" มีจุดยอดที่มีระดับขั้น "d" หรือน้อยกว่า ในทุกกราฟจะมีการลำดับความเสื่อม ซึ่งเป็นการลำดับของจุดยอดที่แต่ละจุดยอดจะมีเพื่อนบ้านจำนวน "d" หรือน้อยกว่า ซึ่งมาทีหลังในการลำดับ การลำดับความเสื่อมอาจถูกพบได้ในเวลาเป็นเชิงเส้นโดยการเลือกจุดยอดที่มีระดับขั้นต่ำสุดในจุดยอดที่เหลืออยู่ซ้ำ ๆ ถ้าลำดับของจุดยอด "v" ซึ่งขั้นตอนวิธีโบรน-เคอร์โบสท์ได้วงวนผ่านไป เป็นลำดับความเสื่อมแล้ว เซต "P" ของตัวแทนจุดยอดในแต่ละการเรียก (เพื่อนบ้านของ "v" ซึ่งมาทีหลังในการลำดับ) จะรับประกันว่าจะใช้ขนาดอย่างมาก "d" เซต "X" ซึ่งเก็บจุดยอดที่ถูกแยกออกมาจะประกอบด้วยเพื่อนบ้านก่อนหน้านี้ของ "v" และอาจจะใหญ่กว่า "d" ในการเรียกการเวียนเกิดในขั้นตอนวิธีนี้ชั้นของการเวียนเกิดที่อยู่ต่ำกว่าชั้นบนสุดยังคงต้องใช้แบบมีแกนหลักอยู่
รหัสเทียมของขั้นตอนวิธีนี้มีดังต่อไปนี้
ขั้นตอนวิธีดังกล่าวถูกพิสูจน์แล้วว่ามีประสิทธิภาพสำหรับกราฟที่มีความเสื่อมน้อย ๆ และจากการทดลองแสดงให้เห็นว่ามันทำงานได้ดีในทางปฏิบัติกับเครือข่ายสังคมขนาดใหญ่แบบเบาบาง (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,5}, {1}, Ø)
 BronKerbosch2({4}, {3,5,6}, Ø)
 BronKerbosch2({6}, Ø, {4}): ไม่ให้ผลลัพธ์
กราฟในตัวอย่างมีความเสื่อมเป็น 2 ซึ่งหนึ่งในการลำดับที่เป็นไปได้คือ 6,4,3,1,2,5 ถ้าเป็นแบบที่มีการลำดับจุดยอดของขั้นตอนวิธีโบรน-เคอร์โบสท์ จะได้ต้นไม้ของการเรียกเป็นดังนี้
 BronKerbosch3(G)
 BronKerbosch2({6}, {4}, Ø)
 BronKerbosch2({4}, {3,5}, {6})
 BronKerbosch2({3}, {2}, {4})
 BronKerbosch2({1}, {2,5}, Ø)
 BronKerbosch2({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"&hairsp;3"d"/3) เมื่อ "d" เป็นความเสื่อมของกราฟซึ่งเป็นการบ่งบอกถึงความเบาบางของกราฟ กราฟใด ๆ ที่มีความเสื่อมเป็น "d" ซึ่งทำให้ผลรวมของจำนวนกลุ่มพรรคพวกที่ใหญ่ที่สุดเป็น ("n" - "d"&hairsp;)3"d"/3 จะทำให้ขอบเขตแคบมาก
ความรู้เพิ่มเติมเกี่ยวกับขั้นตอนวิธี.
กลุ่มพรรคพวกที่ใหญ่ที่สุด (maximal clique) คือ กลุ่มพรรคพวกที่ไม่สามารถขยายได้โดยการเพิ่มจุดยอดที่ติดกันไปอีกหนึ่งจุดหรือมากกว่านั้นอีกแล้ว ซึ่งหมายความว่าจะไม่มีกลุ่มพรรคพวกที่ปรากฏในเซตของจุดยอดของกลุ่มพรรคพวกที่ใหญ่กว่านี้อีก โดยในวงการวิทยาศาสตร์คอมพิวเตอร์ ขั้นตอนวิธีดังกล่าวเป็นปัญหาในการหากลุ่มพรรคพวกที่ใหญ่ที่สุดจัดเป็นปัญหากลุ่มพรรคพวก ปัญหากลุ่มพรรคพวกถือว่าเป็นปัญหาเอ็นพีบริบูรณ์ (NP-complete) ซึ่งเป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี ทำการควบคุมตัวแปรคงที่ได้ยากและยากที่จะประมาณค่า โดยเวลาการทำงานของขั้นตอนวิธีประเภทนี้จะใช้เวลาการทำงานเป็นแบบยกกำลัง (exponential) ซึ่งถือว่าช้ามาก
ปัญหาที่เกี่ยวข้อง.
ปัญหากลุ่มพรรคพวก