กำหนดการพลวัต

 


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