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

ในคณิตศาสตร์ วิทยาการคอมพิวเตอร์ และเศรษฐศาสตร์ กำหนดการพลวัต  คือกระบวนการหาค่าเหมาะที่สุด โดยแก้ไขปัญหาที่ซับซ้อนโดยการแบ่งปัญหาให้เป็นปัญหาย่อยที่สามารถแก้ได้ง่ายกว่าในลักษณะของการเรียกซ้ำ คุณสมบัติพื้นฐานของปัญหาที่จะใช้กำหนดการพลวัตได้คือจะต้องมีปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblem) และโครงสร้างย่อยที่เหมาะสมที่สุด (optimal substructure) ปัญหาที่ใช้กำหนดการพลวัตในการแก้ปัญหาจะใช้เวลาแก้รวดเร็วกว่าการแก้ปัญหาโดยตรงเป็นอย่างมาก
หลักสำคัญของกำหนดการพลวัตมาจากการสังเกตว่าในการแก้ปัญหาที่ซับซ้อนนั้น จำเป็นที่จะต้องแก้ปัญหาที่เล็กกว่า (ปัญหาย่อย) และนำคำตอบของปัญหาย่อยเหล่านั้นมารวมกันเป็นคำตอบของปัญหาใหญ่ และในการดำเนินการแก้ปัญหาย่อยนี้ มีหลายปัญหาที่ปัญหาย่อยบางส่วน"เหมือนกันทุกประการ" ดังนั้นแทนที่จะแก้ไขปัญหาย่อยเหล่านี้ซ้ำอีกรอบ กระบวนการกำหนดการพลวัตจะใช้วิธีแก้ไขปัญหาย่อยเหล่านี้เพียงแค่ครั้งเดียว และเก็บคำตอบไว้ หรือที่เรียกว่าการจำ (memoization; ระวังสะกดเป็น memorization) เมื่อพบปัญหาย่อยดังกล่าวอีกครั้งก็ไม่จำเป็นต้องคำนวณซ้ำใหม่ แต่สามารถเรียกคำตอบที่เก็บไว้มาใช้ได้เลย กระบวนการนี้จะมีประสิทธิภาพดีเป็นอย่างยิ่งเมื่อปัญหาที่จะแก้มีจำนวนปัญหาย่อยที่ทับซ้อนกันเป็นจำนวนมาก ซึ่งหากไม่ได้ใช้กำหนดการพลวัตจะทำให้จำนวนครั้งในการแก้ปัญหาย่อยเติบโตแบบฟังก์ชันเลขชี้กำลัง ส่งผลให้เวลาในการแก้ไขปัญหาเพิ่มขึ้นเป็นอย่างมาก
ประวัติ.
ริชาร์ด เบลแมนเป็นผุ้เริ่มใช้คำว่า"กำหนดการพลวัต" (dynamic programming) ในทศวรรตที่ 1940 และเปลี่ยนความหมายให้สมบูรณ์ยิ่งขึ้นในปี 1953
เบลแมนอธิบายที่มาของคำว่า"กำหนดการพลวัต" (dynamic programming) ในประวัติส่วนตัวของเขาชื่อ "Eye of the Hurricane: An Autobiography" ในปี 1984 ดังนี้
<templatestyles src="แม่แบบ:คำพูด/style.css" />I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, “programming” I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying I thought, lets kill two birds with one stone. Lets take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is its impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. Its impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.
ภาพรวม.
กำหนดการพลวัตในการเขียนโปรแกรมคอมพิวเตอร์.
คุณลักษณะสำคัญ 2 ประการที่ต้องมีในการทำกำหนดการพลวัตคือโครงสร้างย่อยที่เหมาะที่สุด และ ปัญหาย่อยที่ทับซ้อนกัน ถ้าปัญหาที่ต้องการจะแก้นั้นมีโครงสร้างย่อยที่เหมาะที่สุด แต่ปัญหาย่อยนั้น"ไม่ทับซ้อน"กันเลย จะเรียกวิธีการในการแก้ไขปัญหานี้ว่าการแบ่งแยกและเอาชนะ ดังนั้น ถึงแม้การเรียงลำดับแบบเร็ว และ การเรียงลำดับแบบผสานจะมีคุณสมบัติ"โครงสร้างย่อยที่เหมาะที่สุด" แต่ก็ไม่จัดให้เป็นวิธีการกำหนดการพลวัต เพราะไม่มีปัญหาย่อยที่ทับซ้อนกัน แต่จัดให้เป็นวิธีการ"การแบ่งแยกและเอาชนะ"แทน
"โครงสร้างย่อยที่เหมาะที่สุด" หมายความว่าคำตอบที่ดีที่สุดของปัญหาย่อยหนึ่ง สามารถเกิดจากการนำคำตอบที่ดีที่สุดของปัญหาย่อยที่เล็กกว่าทั้งหลายมาประกอบกันได้ ดังนั้นขั้นตอนการประดิษฐ์วิธีการกำหนดการพลวัตก็จะเริ่มจากการค้นหาก่อนว่าปัญหาที่จะแก้มี"โครงสร้างย่อยที่เหมาะที่สุด"หรือไม่ ซึ่งโดยส่วนใหญ่แล้วจะอธิบาย"โครงสร้างย่อยที่เหมาะที่สุด"ด้วยสมการการเรียกซ้ำ (สมการเวียนเกิด) ยกตัวอย่างเช่น กำหนดกราฟ "G" = ("V", "E") มาให้ วิถีสั้นสุด "p" จากจุดยอด "u" ถึงจุดยอด "v" แสดงให้เห็นถึงคุณสมบัติโครงสร้างย่อยที่เหมาะที่สุด ด้วยความจริงที่ว่า ถ้า "p" เป็นวิถีสั้นสุดจริง ๆ แล้ว สำหรับทุก ๆ จุดยอด "w" ที่อยู่ระหว่างทางของวิถีสั้นสุด "p" จะทำให้ ระยะทางของวิถีสั้นสุดจาก "u" ถึง "w" รวมกับระยะทางของวิถีสั้นสุดจาก "w" ถึง "v" มีค่าเท่ากับระยะทางของวิถีสั้นสุดจาก "u" ถึง "v" ดังนั้นจึงสามารถประดิษฐ์ขั้นตอนวิธีกำหนดการพลวัตโดยอิงจากข้อเท็จจริงนี้ขึ้นได้ ซึ่งก็คือ ขั้นตอนวิธีของเบลแมน-ฟอร์ด หรือ ขั้นตอนวิธีของฟลอยด์-วอร์แชล
"ปัญหาย่อยที่ทับซ้อนกัน" หมายความว่าอัตราส่วนระหว่างจำนวนปัญหาย่อยที่แตกต่างกันกับจำนวนปัญหาย่อยทั้งหมดต้องต่ำมาก หรือนั่นก็คือในการคำนวณหาคำตอบจะต้องเกิดการคำนวณปัญหาย่อยเดิม ๆ ซ้ำกันหลาย ๆ รอบ แทนที่จะเกิดปัญหาย่อยใหม่ที่ไม่เกิดการคำนวณซ้ำกันเลยมากมาย ยกตัวอย่างเช่นการคำนวณหาเลขฟีโบนัชชีตามความสัมพันธ์เวียนเกิด "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 ก็คือปัญหาย่อยที่ทับซ้อนกันนั่นเอง
ถึงแม้ว่าจำนวนครั้งที่ปัญหาย่อยที่ทับซ้อนกันต้องคำนวณซ้ำจะดูเหมือนน้อย แต่หากเกิดการคำนวณเวียนเกิดโดยไม่ได้ใช้กำหนดการพลวัต จำนวนครั้งที่ปัญหาย่อยที่ทับซ้อนกันในชั้นล่างของการคำนวณเวียนเกิดจะมีจำนวนมหาศาล โดยจะมีจำนวนเติบโตแบบฟังก์ชันเลขชี้กำลังเทียบกับขนาดของข้อมูลนำเข้า เช่นในการคำนวณ "F"5 อาจจะมีการคำนวณ "F"2 เพียงแค่ 3 ครั้ง แต่เมื่อขนาดข้อมูลนำเข้าเพิ่มขึ้นเช่นต้องในคำนวณ "F"20 จะมีการคำนวณ "F"2 ถึง 4181 ครั้ง การใช้วิธีการกำหนดการพลวัตจะทำให้การแก้ไขปัญหาย่อยนั้นเกิดขึ้นเพียงแค่ครั้งเดียวเสมอ หรือนั่นก็คือจะไม่เกิดการแก้ไขปัญหาย่อยเดิมซ้ำเลย
วิธีการกำหนดการพลวัตอาจอิมพลีเมนต์ได้ 2 วิธี
ในการเขียนโปรแกรม บางภาษาโปรแกรมสามารถทำการจำได้โดยอัตโนมัติ โดยอาจเป็นความสามารถพื้นฐาน (เช่นภาษาโปรล็อก และภาษาเจ โดยใช้คีย์เวิร์ดว่า "M.") หรืออาจเป็นไลบรารีมาตรฐาน (เช่นภาษาเพิร์ล ภาษา Scheme ภาษาคอมมอนลิสป์) หรืออาจเป็นส่วนเสริม (เช่นภาษาซีพลัสพลัส ดูที่)