Divide and Conquer คืออะไร ทำงานยังไง

แนะนำ สอบถาม ภาษา C สำหรับผู้เริ่มต้น ภาษา Java ภาษา Python

Moderator: mindphp, ผู้ดูแลกระดาน

ภาพประจำตัวสมาชิก
WKsoft
PHP Super Hero Member
PHP Super Hero Member
โพสต์: 872
ลงทะเบียนเมื่อ: 30/11/2021 9:35 am

Divide and Conquer คืออะไร ทำงานยังไง

โพสต์ที่ยังไม่ได้อ่าน โดย WKsoft »

ในการเขียนโปรแกรม เราจะเขียนโดยอาศัยอัลกอริทึม ซึ่งเจ้าอัลกอริทึมนี้จะเป็นขั้นตอนวิธีการทำงานหรือการแก้ปัญหาอย่างใดอย่างหนึ่ง
ที่จะช่วยเพิ่มประสิทธิภาพการทำงานของโปรแกรมที่เราเขียนมา โดยประสิทธิภาพที่จะช่วยคือในด้านการใช้หน่วยความจำที่น้อยลง
แต่ทำให้สามารถประมวลผลได้รวดเร็วขึ้น ซึ่ง Divide and Conquerเป็นหนึ่งในประเภทของอัลกอริทึมเหล่านั้น

Divide and Conquer คือ อัลกอริทึมประเภทหนึ่ง เรียกง่ายๆตามตัวเลยว่า แบ่งแยกและเอาชนะ
Divide and Conquer.png
Divide and Conquer.png (75.58 KiB) Viewed 2006 times
Divide คือ แบ่ง ปัญหาที่พบเป็นปัญหาประเภทเดียวกันแต่ที่เล็กลง ขั้นตอนนี้โดยทั่วไปจะใช้วิธีการแบบเรียกซ้ำไปเรื่อยๆ
เพื่อแบ่งปัญหาจนกว่าจะไม่สามารถแบ่งปัญหานั้นๆย่อยลงไปอีกได้ และปัญหาที่ถูกแบ่งไปนั้น
ต้องยังเป็นส่วนหนึ่งของปัญหาเดิมที่เราต้องการจะแก้ไข
Conquer คือ แก้ปัญหาย่อยซ้ำๆ ในขั้นตอนนี้จะได้รับปัญหาย่อยที่แบ่งแล้วจำนวนมาก จากในขั้นDivide
โดยทั่วไปในขั้นตอนนี้ปัญหาต่างๆที่ถูกแบ่งจนไม่สามารถแบ่งได้แล้ว จะสามารถแก้ปัญหาได้ด้วยตัวเอง
หลังจากทั้งแบ่งและแก้ปัญหาในส่วนย่อยต่างๆไปแล้ว ก็จะต้องนำผลลัพธ์ที่ได้จากการแก้ปัญหาส่วนย่อยเหล่านั้นมารวมกัน
กลับมาเป็นชิ้นใหญ่ ที่จะสามารถแก้ปัญหาดั้งเดิมที่เราต้องการแก้ได้

ในการเขียนอัลกอริทึมแบบ Divide and Conquer นิยมเขียนแบบ recursive เพราะง่ายต่อการใช้แต่ก็สามารถเขียนแบบไม่recursive ได้แต่โดยทั่วๆไปเขียนแบบ recursive จะง่ายกว่ามาก

ตัวอย่างปัญหาที่ใช้ Divide and Conquerในการช่วยแก้ไขปัญหา
  • Quicksort
  • Merge Sort
  • Binary Search
  • Closest Pair of Points
Divide and Conquer เป็นรูปแบบในการออกแบบอัลกอริทึมค่อนข้างที่จะมีประโยชน์ในการวิเคราะห์ปัญหาทั่วๆไป การใช้วิธีแก้ปัญหาแบบ Divide and Conquer
จะทำให้เราเข้าใจปัญหาได้มากขึ้น แม้ว่าท้ายสุดจะไม่ใช่วิธีการออกแบบวิธีแก้ปัญหาที่ดีที่สุด แต่หากเราเริ่มด้วยวิธีนี้จะช่วยให้เราเห็นภาพ และทำความเข้าใจปัญหา
ที่เราจะแก้ไขได้ง่าย และช่วยให้เขียนโปรแกรมได้มีประสิทธิภาพ

อ้างอิง
https://www.freecodecamp.org/news/divide-and-conquer-algorithms/
https://baannapleangthai.com/algorithm-design-4-1-divide-conquer-%E0%B8%84%E0%B8%AD%E0%B8%99%E0%B9%80%E0%B8%8B%E0%B9%87%E0%B8%9B-%E0%B8%84%E0%B8%B7%E0%B8%AD/
https://marupatnote.home.blog/2021/06/25/4600/

ผู้ใช้งานขณะนี้

สมาชิกกำลังดูบอร์ดนี้: ไม่มีสมาชิกใหม่ และบุคลทั่วไป 44