ข้ามไปเนื้อหา

ขั้นตอนวิธีแบ่งแยกและเอาชนะ

จากวิกิพีเดีย สารานุกรมเสรี

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีแบ่งแยกและเอาชนะ (อังกฤษ: divide and conquer algorithm; D&C) เป็นวิธีการออกแบบขั้นตอนวิธีโดยมีพื้นฐานมาจากการเรียกซ้ำ ขั้นตอนวิธีแบ่งแยกและเอาชนะทำงานโดยแบ่งปัญหาออกเป็นปัญหาย่อย 2 ส่วนหรือมากกว่านั้นแบบเวียนเกิด ปัญหาถูกแบ่งไปเรื่อย ๆ จนเล็กและง่ายพอที่จะแก้อย่างง่ายดาย หลังจากแก้ปัญหาย่อยเล็ก ๆ เหล่านั้นแล้วก็จะนำคำตอบมารวมกันขึ้นไปเรื่อย ๆ จนสุดท้ายได้คำตอบของปัญหาดั้งเดิม

กลวิธีนี้เป็นพื้นฐานของขั้นตอนวิธีที่มีประสิทธิภาพจำนวนมากมาย เช่น การเรียงลำดับ (การเรียงลำดับแบบเร็ว การเรียงลำดับแบบผสาน) การคูณเลขขนาดใหญ่ (ขั้นตอนวิธีของคาราซูบา) การคำนวณการแปลงฟูรีเยไม่ต่อเนื่อง

ในอีกด้าน การที่จะเข้าใจและสามารถออกแบบขั้นตอนวิธีแบ่งแยกและเอาชนะได้นั้นต้องใช้ทักษะในระดับหนึ่ง เพราะในการที่จะทำให้ขั้นตอนวิธีมีการเรียกซ้ำต่อไปได้เรื่อย ๆ ในเวลาที่ต้องการ บางครั้งอาจจะต้องหาวิธีสร้างปัญหาย่อยซึ่งซับซ้อนและยากมาก นอกจากนี้ การสร้างขั้นตอนวิธีแบ่งแยกและเอาชนะนั้นไม่มีขั้นตอนอย่างเป็นระบบ ตัวอย่างความซับซ้อนจากการวิเคราะห์หรือออกแบบขั้นตอนวิธีแบ่งแยกและเอาชนะ เช่น การคำนวณหาจำนวนฟีโบนัชชีในเวลา โดยใช้รูปเมทริกซ์ร่วมกับการยกกำลังโดยการยกกำลังสอง

ขั้นตอนวิธีแบ่งแยกและเอาชนะ ยังรวมไปถึงขั้นตอนวิธีที่แต่ละปัญหาแบ่งออกเป็นปัญหาย่อยหลายส่วน แต่กลับใช้คำตอบหรือคำนวณคำตอบจากเพียงแค่ปัญหาย่อยเดียวเท่านั้น เช่น การค้นหาแบบทวิภาคบนแถวลำดับที่เรียงแล้ว (หรือขั้นตอนวิธีแบ่งครึ่ง สำหรับการหาคำตอบของรากในการวิเคราะห์เชิงจำนวน)[1] หากนิยามของขั้นตอนวิธีนี้รวมไปถึงขั้นตอนวิธีที่มีเพียงปัญหาย่อยเดียวด้วย อาจทำให้ทุก ๆ ขั้นตอนวิธีที่มีการเรียกซ้ำหรือมีวงวนกลายเป็น "การแบ่งแยกและเอาชนะ" ไปเสียหมด บางคนจึงนับว่าขั้นตอนวิธีจะเป็น "การแบ่งแยกและเอาชนะ" ก็ต่อเมื่อมีการแบ่งปัญหาออกเป็นปัญหาย่อย 2 ส่วนหรือมากกว่าเท่านั้น[2] และเรียก "การลดและเอาชนะ" (decrease and conquer) สำหรับขั้นตอนวิธีที่แบ่งแล้วได้ปัญหาย่อยเดียวเหมือนเดิมแทน[3]

โดยมากแล้ว ความถูกต้องของขั้นตอนวิธีแบ่งแยกและเอาชนะสามารถพิสูจน์ได้โดยการอุปนัยทางคณิตศาสตร์ ในขณะที่เวลาการคำนวณของขั้นตอนวิธีสามารถหาได้จากการแก้ความสัมพันธ์เวียนเกิด

ข้อได้เปรียบ

[แก้]

แก้ไขปัญหาที่ยาก

[แก้]

ขั้นตอนวิธีแบ่งแยกและเอาชนะเป็นวิธีในการแก้ปัญหาที่ยากบางปัญหาได้อย่างดี เช่น ปัญหาหอคอยแห่งฮานอย ในการที่จะแก้ปัญหานี้ สิ่งที่ต้องการมีเพียงวิธีการแบ่งปัญหาเป็นปัญหาย่อย และวิธีการในการประกอบคำตอบของปัญหาย่อยมาเป็นคำตอบของปัญหาดั้งเดิม

ประสิทธิภาพของขั้นตอนวิธี

[แก้]

ขั้นตอนวิธีแบ่งแยกและเอาชนะมักจะช่วยในการสร้างขั้นตอนวิธีที่มีประสิทธิภาพ เช่น การคูณอย่างรวดเร็วด้วยขั้นตอนวิธีของคาราซูบา การเรียงลำดับอย่างรวดเร็วด้วยการเรียงลำดับแบบเร็วหรือการเรียงลำดับแบบผสาน การคูณเมทริกซ์ด้วยขั้นตอนวิธีของสแตรสเซน หรือการคำนวณการแปลงฟูรีเยไม่ต่อเนื่องแบบเร็ว

ในตัวอย่างทั้งหมดที่กล่าวมา ขั้นตอนวิธีแบ่งแยกและเอาชนะช่วยในการลดความซับซ้อนในการคำนวณได้อย่างมีนัยยะสำคัญ ยกตัวอย่างเช่นการเรียงลำดับแบบผสาน ซึ่งคำนวณกรณีฐานได้ในเวลาคงที่ และการแบ่งและรวมปัญหาในแต่ละครั้งใช้เวลา เมื่อ n คือขนาดปัญหาที่กำลังแก้ในขณะนั้น จะได้ว่าประสิทธิภาพโดยรวมของขั้นตอนวิธี คือ ซึ่งดีกว่าการเรียงลำดับแบบอื่น ๆ ที่คิดค้นขึ้นมาก่อนหน้านั้น ซึ่งส่วนใหญ่จะใช้เวลา

อ้างอิง

[แก้]
  1. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).
  2. Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
  3. Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).