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

บทความนี้เกี่ยวกับกระบวนการแก้ไขปัญหา สำหรับประเภทภาษาโปรแกรมขั้นสูง ดูที่ ภาษาเชิงกำหนดการพลวัต

ในคณิตศาสตร์ วิทยาการคอมพิวเตอร์ และเศรษฐศาสตร์ กำหนดการพลวัต (อังกฤษ: dynamic programming) คือกระบวนการหาค่าเหมาะที่สุด โดยแก้ไขปัญหาที่ซับซ้อนโดยการแบ่งปัญหาให้เป็นปัญหาย่อยที่สามารถแก้ได้ง่ายกว่าในลักษณะของการเรียกซ้ำ คุณสมบัติพื้นฐานของปัญหาที่จะใช้กำหนดการพลวัตได้คือจะต้องมีปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblem) และโครงสร้างย่อยที่เหมาะสมที่สุด (optimal substructure) ปัญหาที่ใช้กำหนดการพลวัตในการแก้ปัญหาจะใช้เวลาแก้รวดเร็วกว่าการแก้ปัญหาโดยตรงเป็นอย่างมาก

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

ประวัติ

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

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

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 และ F₁ = 1 จะเห็นได้ว่า F₅ = F₄ + F₃ และ F₄ = F₃ + F₂ สังเกตว่า F₃ นั้นเป็นพจน์ที่จะต้องคำนวณในการหาทั้ง F₅ และ F₄ ซึ่ง F₃ ก็คือปัญหาย่อยที่ทับซ้อนกันนั่นเอง

 

แผนผังการคำนวณหาเลขฟีโบนัชชีพจน์ที่ 5 โดยไม่ได้ใช้กำหนดการพลวัต

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

วิธีการกำหนดการพลวัตอาจอิมพลีเมนต์ได้ 2 วิธี

• วิธีการจากบนลงล่าง โดยเป็นการเรียกใช้ฟังก์ชันเวียนเกิดคล้ายกับการแก้ไขปัญหาโดยไม่ใช้กำหนดการพลวัต แต่หากพบว่าเป็นการแก้ไขปัญหาย่อยนั้นครั้งแรกก็ให้จำคำตอบของปัญหาย่อยดังกล่าวไว้ในตาราง จากนั้นเมื่อมีการเรียกใช้ฟังก์ชันให้แก้ไขปัญหาย่อยดังกล่าวอีกรอบก็สามารถนำค่าจากตารางมาเป็นคำตอบได้เลยโดยไม่ต้องคำนวณใหม่อีกรอบ และเรียกกระบวนการในการจำคำตอบในตารางขณะเรียกใช้ฟังก์ชันเวียนเกิดว่า "การจำ" (memoization)
• วิธีการจากล่างขึ้นบน เป็นวิธีการที่สังเกตทิศทางของการแก้ไขปัญหาแบบเวียนเกิด แล้วมาเขียนโปรแกรมให้แก้ไขปัญหาย่อยที่สุดก่อนไปเรื่อย ๆ จนได้คำตอบ ซึ่งเป็นทิศทางที่สวนทางกันกับวิธีการจากบนลงล่างนั่นเอง ยกตัวอย่างเช่นสังเกตว่าหากมีค่า F₅ กับ F₆ ก็จะสามารถหา F₇ ได้อย่างง่ายดาย ดังนั้นทิศทางของการหาเลขฟีโบนัชชีก็คือคำนวณ F₁, F₂, F₃ ไปเรื่อย ๆ จนถึง F_n ซึ่งเป็นคำตอบนั่นเอง

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

อ้างอิง

1. S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, 'Algorithms', p 173, available at http://www.cs.berkeley.edu/~vazirani/algorithms.html
2. http://www.wu-wien.ac.at/usr/h99c/h9951826/bellman_dynprog.pdf
3. "M. Memo". J Vocabulary. J Software. สืบค้นเมื่อ 28 October 2011.
4. . คลังข้อมูลเก่า เก็บจาก แหล่งเดิม เมื่อ 2006-09-02. สืบค้นเมื่อ 2013-02-11.