กำหนดการพลวัต
ภาพรวม > กำหนดการพลวัตในการเขียนโปรแกรมคอมพิวเตอร์

คุณลักษณะสำคัญ 2 ประการที่ต้องมีในการทำกำหนดการพลวัตคือโครงสร้างย่อยที่เหมาะที่สุด และ ปัญหาย่อยที่ทับซ้อนกัน ถ้าปัญหาที่ต้องการจะแก้นั้นมีโครงสร้างย่อยที่เหมาะที่สุด แต่ปัญหาย่อยนั้นไม่ทับซ้อนกันเลย จะเรียกวิธีการในการแก้ไขปัญหานี้ว่าการแบ่งแยกและเอาชนะ ดังนั้น ถึงแม้การเรียงลำดับแบบเร็ว และ การเรียงลำดับแบบผสานจะมีคุณสมบัติโครงสร้างย่อยที่เหมาะที่สุด แต่ก็ไม่จัดให้เป็นวิธีการกำหนดการพลวัต เพราะไม่มีปัญหาย่อยที่ทับซ้อนกัน แต่จัดให้เป็นวิธีการการแบ่งแยกและเอาชนะแทน
โครงสร้างย่อยที่เหมาะที่สุด หมายความว่าคำตอบที่ดีที่สุดของปัญหาย่อยหนึ่ง สามารถเกิดจากการนำคำตอบที่ดีที่สุดของปัญหาย่อยที่เล็กกว่าทั้งหลายมาประกอบกันได้ ดังนั้นขั้นตอนการประดิษฐ์วิธีการกำหนดการพลวัตก็จะเริ่มจากการค้นหาก่อนว่าปัญหาที่จะแก้มีโครงสร้างย่อยที่เหมาะที่สุดหรือไม่ ซึ่งโดยส่วนใหญ่แล้วจะอธิบายโครงสร้างย่อยที่เหมาะที่สุดด้วยสมการการเรียกซ้ำ (สมการเวียนเกิด) ยกตัวอย่างเช่น กำหนดกราฟ G = (V, E) มาให้ วิถีสั้นสุด p จากจุดยอด u ถึงจุดยอด v แสดงให้เห็นถึงคุณสมบัติโครงสร้างย่อยที่เหมาะที่สุด ด้วยความจริงที่ว่า ถ้า p เป็นวิถีสั้นสุดจริง ๆ แล้ว สำหรับทุก ๆ จุดยอด w ที่อยู่ระหว่างทางของวิถีสั้นสุด p จะทำให้ ระยะทางของวิถีสั้นสุดจาก u ถึง w รวมกับระยะทางของวิถีสั้นสุดจาก w ถึง v มีค่าเท่ากับระยะทางของวิถีสั้นสุดจาก u ถึง v ดังนั้นจึงสามารถประดิษฐ์ขั้นตอนวิธีกำหนดการพลวัตโดยอิงจากข้อเท็จจริงนี้ขึ้นได้ ซึ่งก็คือ ขั้นตอนวิธีของเบลแมน-ฟอร์ด หรือ ขั้นตอนวิธีของฟลอยด์-วอร์แชล
ปัญหาย่อยที่ทับซ้อนกัน หมายความว่าอัตราส่วนระหว่างจำนวนปัญหาย่อยที่แตกต่างกันกับจำนวนปัญหาย่อยทั้งหมดต้องต่ำมาก หรือนั่นก็คือในการคำนวณหาคำตอบจะต้องเกิดการคำนวณปัญหาย่อยเดิม ๆ ซ้ำกันหลาย ๆ รอบ แทนที่จะเกิดปัญหาย่อยใหม่ที่ไม่เกิดการคำนวณซ้ำกันเลยมากมาย ยกตัวอย่างเช่นการคำนวณหาเลขฟีโบนัชชีตามความสัมพันธ์เวียนเกิด Fi = Fi−1 + Fi−2 โดยมีกรณีฐานคือ F0 = 0 และ F1 = 1 จะเห็นได้ว่า F5 = F4 + F3 และ F4 = F3 + F2 สังเกตว่า F3 นั้นเป็นพจน์ที่จะต้องคำนวณในการหาทั้ง F5 และ F4 ซึ่ง F3 ก็คือปัญหาย่อยที่ทับซ้อนกันนั่นเอง
ถึงแม้ว่าจำนวนครั้งที่ปัญหาย่อยที่ทับซ้อนกันต้องคำนวณซ้ำจะดูเหมือนน้อย แต่หากเกิดการคำนวณเวียนเกิดโดยไม่ได้ใช้กำหนดการพลวัต จำนวนครั้งที่ปัญหาย่อยที่ทับซ้อนกันในชั้นล่างของการคำนวณเวียนเกิดจะมีจำนวนมหาศาล โดยจะมีจำนวนเติบโตแบบฟังก์ชันเลขชี้กำลังเทียบกับขนาดของข้อมูลนำเข้า เช่นในการคำนวณ F5 อาจจะมีการคำนวณ F2 เพียงแค่ 3 ครั้ง แต่เมื่อขนาดข้อมูลนำเข้าเพิ่มขึ้นเช่นต้องในคำนวณ F20 จะมีการคำนวณ F2 ถึง 4181 ครั้ง การใช้วิธีการกำหนดการพลวัตจะทำให้การแก้ไขปัญหาย่อยนั้นเกิดขึ้นเพียงแค่ครั้งเดียวเสมอ หรือนั่นก็คือจะไม่เกิดการแก้ไขปัญหาย่อยเดิมซ้ำเลย
วิธีการกำหนดการพลวัตอาจอิมพลีเมนต์ได้ 2 วิธี
วิธีการจากบนลงล่าง โดยเป็นการเรียกใช้ฟังก์ชันเวียนเกิดคล้ายกับการแก้ไขปัญหาโดยไม่ใช้กำหนดการพลวัต แต่หากพบว่าเป็นการแก้ไขปัญหาย่อยนั้นครั้งแรกก็ให้จำคำตอบของปัญหาย่อยดังกล่าวไว้ในตาราง จากนั้นเมื่อมีการเรียกใช้ฟังก์ชันให้แก้ไขปัญหาย่อยดังกล่าวอีกรอบก็สามารถนำค่าจากตารางมาเป็นคำตอบได้เลยโดยไม่ต้องคำนวณใหม่อีกรอบ และเรียกกระบวนการในการจำคำตอบในตารางขณะเรียกใช้ฟังก์ชันเวียนเกิดว่า "การจำ" (memoization)
วิธีการจากล่างขึ้นบน เป็นวิธีการที่สังเกตทิศทางของการแก้ไขปัญหาแบบเวียนเกิด แล้วมาเขียนโปรแกรมให้แก้ไขปัญหาย่อยที่สุดก่อนไปเรื่อย ๆ จนได้คำตอบ ซึ่งเป็นทิศทางที่สวนทางกันกับวิธีการจากบนลงล่างนั่นเอง ยกตัวอย่างเช่นสังเกตว่าหากมีค่า F5 กับ F6 ก็จะสามารถหา F7 ได้อย่างง่ายดาย ดังนั้นทิศทางของการหาเลขฟีโบนัชชีก็คือคำนวณ F1, F2, F3 ไปเรื่อย ๆ จนถึง Fn ซึ่งเป็นคำตอบนั่นเอง
ในการเขียนโปรแกรม บางภาษาโปรแกรมสามารถทำการจำได้โดยอัตโนมัติ โดยอาจเป็นความสามารถพื้นฐาน (เช่นภาษาโปรล็อก และภาษาเจ โดยใช้คีย์เวิร์ดว่า M.) หรืออาจเป็นไลบรารีมาตรฐาน (เช่นภาษาเพิร์ล ภาษา Scheme ภาษาคอมมอนลิสป์) หรืออาจเป็นส่วนเสริม (เช่นภาษาซีพลัสพลัส ดูที่)
การหาวิถีสั้นสุดภายในกราฟโดยใช้คุณสมบัติโครงสร้างย่อยที่เหมาะสมที่สุด เส้นตรงแสดงถึงเส้นเชื่อมของกราฟ เส้นโค้งแสดงถึงวิถีสั้นสุดระหว่างจุดยอด เส้นหนาแสดงถึงวิถีสั้นสุดจากจุดยอดเริ่มต้นถึงจุดยอดเป้าหมาย
แผนผังการคำนวณหาเลขฟีโบนัชชี โดยรวบปัญหาย่อยที่ทับซ้อนเข้าด้วยกัน ทำให้ได้แผนผังไม่เป็นกราฟต้นไม้
แผนผังการคำนวณหาเลขฟีโบนัชชีพจน์ที่ 5 โดยไม่ได้ใช้กำหนดการพลวัต