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

ในคณิตศาสตร์ วิทยาการคอมพิวเตอร์ และเศรษฐศาสตร์ กำหนดการพลวัต () คือกระบวนการหาค่าเหมาะที่สุด โดยแก้ไขปัญหาที่ซับซ้อนโดยการแบ่งปัญหาให้เป็นปัญหาย่อยที่สามารถแก้ได้ง่ายกว่าในลักษณะของการเรียกซ้ำ คุณสมบัติพื้นฐานของปัญหาที่จะใช้กำหนดการพลวัตได้คือจะต้องมีปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblem)S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, 'Algorithms', p 173, available at http://www.cs.berkeley.edu/~vazirani/algorithms.html และโครงสร้างย่อยที่เหมาะสมที่สุด (optimal substructure) ปัญหาที่ใช้กำหนดการพลวัตในการแก้ปัญหาจะใช้เวลาแก้รวดเร็วกว่าการแก้ปัญหาโดยตรงเป็นอย่างมาก

หลักสำคัญของกำหนดการพลวัตมาจากการสังเกตว่าในการแก้ปัญหาที่ซับซ้อนนั้น จำเป็นที่จะต้องแก้ปัญหาที่เล็กกว่า (ปัญหาย่อย) และนำคำตอบของปัญหาย่อยเหล่านั้นมารวมกันเป็นคำตอบของปัญหาใหญ่ และในการดำเนินการแก้ปัญหาย่อยนี้ มีหลายปัญหาที่ปัญหาย่อยบางส่วนเหมือนกันทุกประการ ดังนั้นแทนที่จะแก้ไขปัญหาย่อยเหล่านี้ซ้ำอีกรอบ กระบวนการกำหนดการพลวัตจะใช้วิธีแก้ไขปัญหาย่อยเหล่านี้เพียงแค่ครั้งเดียว และเก็บคำตอบไว้ หรือที่เรียกว่าการจำ (memoization; ระวังสะกดเป็น memorization) เมื่อพบปัญหาย่อยดังกล่าวอีกครั้งก็ไม่จำเป็นต้องคำนวณซ้ำใหม่ แต่สามารถเรียกคำตอบที่เก็บไว้มาใช้ได้เลย กระบวนการนี้จะมีประสิทธิภาพดีเป็นอย่างยิ่งเมื่อปัญหาที่จะแก้มีจำนวนปัญหาย่อยที่ทับซ้อนกันเป็นจำนวนมาก ซึ่งหากไม่ได้ใช้กำหนดการพลวัตจะทำให้จำนวนครั้งในการแก้ปัญหาย่อยเติบโตแบบฟังก์ชันเลขชี้กำลัง ส่งผลให้เวลาในการแก้ไขปัญหาเพิ่มขึ้นเป็นอย่างมาก

 ประวัติ 
ริชาร์ด เบลแมนเป็นผุ้เริ่มใช้คำว่ากำหนดการพลวัต (dynamic programming) ในทศวรรตที่ 1940 และเปลี่ยนความหมายให้สมบูรณ์ยิ่งขึ้นในปี 1953

เบลแมนอธิบายที่มาของคำว่ากำหนดการพลวัต (dynamic programming) ในประวัติส่วนตัวของเขาชื่อ Eye of the Hurricane: An Autobiography ในปี 1984 ดังนี้

 ภาพรวม 
200px|right|thumb|การหาวิถีสั้นสุดภายในกราฟโดยใช้คุณสมบัติโครงสร้างย่อยที่เหมาะสมที่สุด เส้นตรงแสดงถึงเส้นเชื่อมของกราฟ เส้นโค้งแสดงถึงวิถีสั้นสุดระหว่างจุดยอด เส้นหนาแสดงถึงวิถีสั้นสุดจากจุดยอดเริ่มต้นถึงจุดยอดเป้าหมาย

 กำหนดการพลวัตในการเขียนโปรแกรมคอมพิวเตอร์ 
คุณลักษณะสำคัญ 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 ภาษาคอมมอนลิสป์) หรืออาจเป็นส่วนเสริม (เช่นภาษาซีพลัสพลัส ดูที่)

 อ้างอิง 

หมวดหมู่:กำหนดการพลวัต
หมวดหมู่:การหาค่าเหมาะที่สุดทางคณิตศาสตร์
หมวดหมู่:วิธีการหาค่าเหมาะที่สุด
หมวดหมู่:สมการ
หมวดหมู่:วิศวกรรมระบบ
หมวดหมู่:การวิจัยดำเนินการ