ในบทความนี้ เราจะทำความเข้าใจความแตกต่างระหว่าง greedy algorithm และ dynamic programming methods
Greedy Algorithm (อัลกอริทึมขี้หนา)
เป็น paradigm ของอัลกอริทึมที่สร้างคำตอบเป็นส่วนๆ ทีละขั้นตอน ขั้นตอนถัดไปจะถูกเลือกโดยที่ให้ประโยชน์ที่ชัดเจนและทันทีที่สุด
- ปัญหาที่เกี่ยวข้องกับการเลือกค่าที่เหมาะสมที่สุดในพื้นที่ (local optimal) จะช่วยให้เลือกค่าที่เหมาะสมที่สุดในภาพรวม (global optimal) ได้ ปัญหาแบบนี้เกี่ยวข้องกับ greedy algorithm
- ไม่มีความมั่นใจว่า greedy algorithm จะนำไปสู่ optimal solution
- มีการเลือก optimal choice ในทุกขั้นตอนของปัญหา กล่าวคือ local optimal solution
- มีประสิทธิภาพด้านการใช้หน่วยความจำ เนื่องจากไม่ต้องย้อนกลับหรือเปลี่ยนแปลงคำตอบ/ค่าก่อนหน้า
- โดยทั่วไป เร็วกว่า dynamic programming techniques
- ตัวอย่าง: Dijkstra's shortest path algorithm ใช้เวลา O(ELogV + VLogV)
- คำตอบใน greedy algorithm คำนวณด้วยวิธี forward ไม่เคยไปเยี่ยมค่าก่อนหน้าหรือเปลี่ยนแปลง
Dynamic Programming (การเขียนโปรแกรมแบบไดนามิก)
เป็นเทคนิคการเพิ่มประสิทธิภาพที่ช่วยเก็บผลลัพธ์ของ sub-problems ไว้ เพื่อไม่ต้องคำนวณซ้ำเมื่อต้องการในอนาคต สามารถดึงจากชุดที่คำนวณไว้ล่วงหน้าได้ ลดความซับซ้อนด้านเวลาจาก exponential เป็น polynomial complexity
- ตัวอย่าง: recursive solution สามารถเปลี่ยนเป็น dynamic programming problem โดยการคำนวณ
- ในที่นี้ การตัดสินใจในแต่ละขั้นตอนทำโดยพิจารณาปัญหาปัจจุบันและคำตอบของ sub-problem ที่แก้ไว้ก่อนหน้า จะใช้คำนวณค่า/คำตอบที่ optimal
- รับประกันว่า dynamic programming problem จะมี optimal solution
- ที่นี่ optimal solution ที่เลือกเป็น globally optimal ใช้สูตรบางอย่างที่เคยใช้เก็บค่าสถานะที่คำนวณไว้ก่อนหน้า
- ต้องการตาราง dynamic programming สำหรับ memorization เพิ่มความซับซ้อนด้านหน่วยความจำ
- ช้ากว่าเมื่อเปรียบเทียบ
- ตัวอย่าง: Bellman Ford algorithm ใช้เวลา O(VE)
- Dynamic programming หาคำตอบด้วย bottom-up หรือ top-down approach โดยพัฒนาจาก sub-problems ที่มี optimal solutions
