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

ในคณิตศาสตร์ วิทยาการคอมพิวเตอร์ และเศรษฐศาสตร์ **กำหนดการพลวัต** () คือกระบวนการหาค่าเหมาะที่สุด โดยแก้ไขปัญหาที่ซับซ้อนโดยการแบ่งปัญหาให้เป็นปัญหาย่อยที่สามารถแก้ได้ง่ายกว่าในลักษณะของการเรียกซ้ำ คุณสมบัติพื้นฐานของปัญหาที่จะใช้กำหนดการพลวัตได้คือจะต้องมีปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblem) และโครงสร้างย่อยที่เหมาะสมที่สุด (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* ดังนั้นจึงสามารถประดิษฐ์ขั้นตอนวิธีกำหนดการพลวัตโดยอิงจากข้อเท็จจริงนี้ขึ้นได้ ซึ่งก็คือ ขั้นตอนวิธีของเบลแมน-ฟอร์ด หรือ ขั้นตอนวิธีของฟลอยด์-วอร์แชล

[left|thumb|108px|แผนผังการคำนวณหาเลขฟีโบนัชชี โดยรวบปัญหาย่อยที่ทับซ้อนเข้าด้วยกัน ทำให้ได้แผนผังไม่เป็น[กราฟต้นไม้]]
*ปัญหาย่อยที่ทับซ้อนกัน* หมายความว่าอัตราส่วนระหว่างจำนวนปัญหาย่อยที่แตกต่างกันกับจำนวนปัญหาย่อยทั้งหมดต้องต่ำมาก หรือนั่นก็คือในการคำนวณหาคำตอบจะต้องเกิดการคำนวณปัญหาย่อยเดิม ๆ ซ้ำกันหลาย ๆ รอบ แทนที่จะเกิดปัญหาย่อยใหม่ที่ไม่เกิดการคำนวณซ้ำกันเลยมากมาย ยกตัวอย่างเช่นการคำนวณหาเลขฟีโบนัชชีตามความสัมพันธ์เวียนเกิด *F**i* = *F**i*−1 + *F**i*−2 โดยมีกรณีฐานคือ *F*0 = 0 และ *F*1 = 1 จะเห็นได้ว่า *F*5 = *F*4 + *F*3 และ *F*4 = *F*3 + *F*2 สังเกตว่า *F*3 นั้นเป็นพจน์ที่จะต้องคำนวณในการหาทั้ง *F*5 และ *F*4 ซึ่ง *F*3 ก็คือปัญหาย่อยที่ทับซ้อนกันนั่นเอง

[thumb|แผนผังการคำนวณหา[เลขฟีโบนัชชีพจน์ที่ 5 โดยไม่ได้ใช้กำหนดการพลวัต]]
ถึงแม้ว่าจำนวนครั้งที่ปัญหาย่อยที่ทับซ้อนกันต้องคำนวณซ้ำจะดูเหมือนน้อย แต่หากเกิดการคำนวณเวียนเกิดโดยไม่ได้ใช้กำหนดการพลวัต จำนวนครั้งที่ปัญหาย่อยที่ทับซ้อนกันในชั้นล่างของการคำนวณเวียนเกิดจะมีจำนวนมหาศาล โดยจะมีจำนวนเติบโตแบบฟังก์ชันเลขชี้กำลังเทียบกับขนาดของข้อมูลนำเข้า เช่นในการคำนวณ *F*5 อาจจะมีการคำนวณ *F*2 เพียงแค่ 3 ครั้ง แต่เมื่อขนาดข้อมูลนำเข้าเพิ่มขึ้นเช่นต้องในคำนวณ *F*20 จะมีการคำนวณ *F*2 ถึง 4181 ครั้ง การใช้วิธีการกำหนดการพลวัตจะทำให้การแก้ไขปัญหาย่อยนั้นเกิดขึ้นเพียงแค่ครั้งเดียวเสมอ หรือนั่นก็คือจะไม่เกิดการแก้ไขปัญหาย่อยเดิมซ้ำเลย

วิธีการกำหนดการพลวัตอาจอิมพลีเมนต์ได้ 2 วิธี
* *วิธีการจาก[[บนลงล่าง]]* โดยเป็นการเรียกใช้ฟังก์ชันเวียนเกิดคล้ายกับการแก้ไขปัญหาโดยไม่ใช้กำหนดการพลวัต แต่หากพบว่าเป็นการแก้ไขปัญหาย่อยนั้นครั้งแรกก็ให้จำคำตอบของปัญหาย่อยดังกล่าวไว้ในตาราง จากนั้นเมื่อมีการเรียกใช้ฟังก์ชันให้แก้ไขปัญหาย่อยดังกล่าวอีกรอบก็สามารถนำค่าจากตารางมาเป็นคำตอบได้เลยโดยไม่ต้องคำนวณใหม่อีกรอบ และเรียกกระบวนการในการจำคำตอบในตารางขณะเรียกใช้ฟังก์ชันเวียนเกิดว่า "การจำ" (memoization)
* *วิธีการจาก[[ล่างขึ้นบน]]* เป็นวิธีการที่สังเกตทิศทางของการแก้ไขปัญหาแบบเวียนเกิด แล้วมาเขียนโปรแกรมให้แก้ไขปัญหาย่อยที่สุดก่อนไปเรื่อย ๆ จนได้คำตอบ ซึ่งเป็นทิศทางที่สวนทางกันกับ*วิธีการจากบนลงล่าง*นั่นเอง ยกตัวอย่างเช่นสังเกตว่าหากมีค่า *F*5 กับ *F*6 ก็จะสามารถหา *F*7 ได้อย่างง่ายดาย ดังนั้นทิศทางของการหาเลขฟีโบนัชชีก็คือคำนวณ *F*1, *F*2, *F*3 ไปเรื่อย ๆ จนถึง *F*n ซึ่งเป็นคำตอบนั่นเอง

ในการเขียนโปรแกรม บางภาษาโปรแกรมสามารถทำการจำได้โดยอัตโนมัติ โดยอาจเป็นความสามารถพื้นฐาน (เช่นภาษาโปรล็อก และภาษาเจ โดยใช้คีย์เวิร์ดว่า *M.*) หรืออาจเป็นไลบรารีมาตรฐาน (เช่นภาษาเพิร์ล ภาษา Scheme ภาษาคอมมอนลิสป์) หรืออาจเป็นส่วนเสริม (เช่นภาษาซีพลัสพลัส ดูที่)

## อ้างอิง

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