เมนูนำทาง
กำหนดการพลวัต ภาพรวมคุณลักษณะสำคัญ 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 ก็คือปัญหาย่อยที่ทับซ้อนกันนั่นเอง
แผนผังการคำนวณหาเลขฟีโบนัชชีพจน์ที่ 5 โดยไม่ได้ใช้กำหนดการพลวัตถึงแม้ว่าจำนวนครั้งที่ปัญหาย่อยที่ทับซ้อนกันต้องคำนวณซ้ำจะดูเหมือนน้อย แต่หากเกิดการคำนวณเวียนเกิดโดยไม่ได้ใช้กำหนดการพลวัต จำนวนครั้งที่ปัญหาย่อยที่ทับซ้อนกันในชั้นล่างของการคำนวณเวียนเกิดจะมีจำนวนมหาศาล โดยจะมีจำนวนเติบโตแบบฟังก์ชันเลขชี้กำลังเทียบกับขนาดของข้อมูลนำเข้า เช่นในการคำนวณ F5 อาจจะมีการคำนวณ F2 เพียงแค่ 3 ครั้ง แต่เมื่อขนาดข้อมูลนำเข้าเพิ่มขึ้นเช่นต้องในคำนวณ F20 จะมีการคำนวณ F2 ถึง 4181 ครั้ง การใช้วิธีการกำหนดการพลวัตจะทำให้การแก้ไขปัญหาย่อยนั้นเกิดขึ้นเพียงแค่ครั้งเดียวเสมอ หรือนั่นก็คือจะไม่เกิดการแก้ไขปัญหาย่อยเดิมซ้ำเลย
วิธีการกำหนดการพลวัตอาจอิมพลีเมนต์ได้ 2 วิธี
ในการเขียนโปรแกรม บางภาษาโปรแกรมสามารถทำการจำได้โดยอัตโนมัติ โดยอาจเป็นความสามารถพื้นฐาน (เช่นภาษาโปรล็อก และภาษาเจ โดยใช้คีย์เวิร์ดว่า M.[3]) หรืออาจเป็นไลบรารีมาตรฐาน (เช่นภาษาเพิร์ล ภาษา Scheme ภาษาคอมมอนลิสป์) หรืออาจเป็นส่วนเสริม (เช่นภาษาซีพลัสพลัส ดูที่[4])
เมนูนำทาง
กำหนดการพลวัต ภาพรวมใกล้เคียง
กำหนดการพลวัต กำหนดการเชิงเส้น กำหนดค่า กำหนดการปกครองของตนเอง การกำหนดที่ตั้งวัตถุด้วยเสียงสะท้อนในมนุษย์ การกำหนดรู้การทรงตัว การกำหนดช่วงเวลาของอียิปต์โบราณ การกำหนดอาหาร การกำหนดความสมเหตุสมผลโดยอัตวิสัย การกำหนดเพศแหล่งที่มา
WikiPedia: กำหนดการพลวัต http://www.wu-wien.ac.at/usr/h99c/h9951826/bellman... http://www.jsoftware.com/help/dictionary/dmcapdot.... http://www.cs.berkeley.edu/~vazirani/algorithms.ht... http://www.apl.jhu.edu/~paulmac/c++-memoization.ht...