ทำความเข้าใจ Divide and Conquer Algorithm ใน 1 นาที

“หากคุณมีเหรียญอยู่ตะกร้าหนึ่ง (มีเหรียญ 1, 5, 10 บาทปนกันอยู่) คุณจะใช้วิธีไหนในการนับมูลค่าของเหรียญในตะกร้านี้?”

บางคนก็อาจจะนับมูลค่าไปทีละเหรียญ หรือบางคนก็อาจจะแยกกองเหรียญแต่ละประเภทจากนั้นค่อยนับแยกทีละกอง

สำหรับในโพสนี้จะมานำเสนออีกหนึ่งวิธีการก็คือ “แยกเหรียญกองใหญ่ออกมาเป็นกองย่อย ๆ (จนเล็กพอจนสามารถนับได้สะดวก) จากนั้นทำการนับมัน”

เราอาจจะเริ่มจากคำถามว่า “กองเหรียญที่อยู่ตรงหน้าเราใหญ่เกินไปไหม?” ถ้าคำตอบคือ “ใช่” เราก็อาจจะแยกกองเหรียญใหญ่ของเราออกเป็น 2 กอง

…จากนั้นทำไปเรื่อย ๆ จนกระทั่งกองเหรียญของเราเล็กพอที่เราจะนับมันได้ พอเรานับแล้ว เราก็เอาผลรวมของกองย่อย ๆ มารวมกันเพื่อหาผลรวมมูลค่าของกองใหญ่

เราเรียกวิธีการนับเหรียญดังกล่าวว่า divide and conquer algorithm ครับ ซึ่งโดยหลัก ๆ แล้วจะแบ่งออกเป็นทั้งหมด 3 ขั้นตอน

1. Divide: คือการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อย ๆ (แบ่งเหรียญให้กองเล็กลง)
2. Conquer: เมื่อปัญหาเล็กพอแล้วก็แก้ปัญหานั้นซะ (นับมูลค่าเหรียญในกองเล็ก)
3. Combine: รวมทุกอย่างเข้าด้วยกันเพื่อแก้ปัญหาใหญ่ (รวมมูลค่าเหรียญกองเล็ก เพื่อหามูลค่ากองใหญ่)

ความน่าสนใจก็คือว่า ปัญหาย่อย ๆ ที่เราแบ่งออกมานั้นเป็น “ปัญหาย่อยที่เป็นอิสระจากกัน” (independent sub-problems)

นั่นหมายความว่าสมมุติเรามีเหรียญกองย่อย 10 กอง เราก็สามารถกระจายไปให้เพื่อน 10 คนช่วยกันนับพร้อมกันแบบ parallel ได้เลย พอใครได้คำตอบแล้วก็เอามูลค่ามารวมกันนั้นเอง

เรียกได้ว่าเร็วขึ้นไปอีกก~

(หรือลองนึกภาพเวลาต้อง process data ขนาดใหญ่ ถ้าหากว่าเราสามารถแบ่งปัญหาให้เป็นปัญหาเล็ก ๆ ที่เป็นอิสระจากกันได้ เราก็สามารถโยนปัญหาย่อย ๆ ไปให้คอมหลาย ๆ เครื่อง process พร้อม ๆ กันได้)