Dynamic programming — การโปรแกรมพลวัต

การโปรแกรมพลวัต (DP; อังกฤษ dynamic programming, DP) — คือวิธีการแก้ปัญหาการหาค่าเหมาะสมที่ซับซ้อน โดยอาศัยการแบ่งปัญหาเริ่มต้นออกเป็นลำดับของปัญหาย่อยที่ง่ายกว่า วิธีการนี้ประยุกต์ใช้กับกระบวนการตัดสินใจแบบหลายขั้นตอน ซึ่งคำตอบที่ดีที่สุดของปัญหาทั้งหมดสามารถสร้างขึ้นจากคำตอบที่ดีที่สุดของปัญหาย่อยของมัน

คำศัพท์นี้ถูกบัญญัติขึ้นโดยนักคณิตศาสตร์ชาวอเมริกัน Richard Bellman ในช่วงทศวรรษ 1950 ในบริบทนี้ คำว่า "programming" ใช้ในความหมายของ "การวางแผน" หรือ "การจัดทำแผนปฏิบัติการที่เหมาะสมที่สุด" มิใช่การเขียนโค้ดคอมพิวเตอร์

คุณสมบัติและทฤษฎีบทสำคัญ

ความสามารถในการประยุกต์ใช้การโปรแกรมพลวัตกับปัญหาหนึ่ง ๆ ถูกกำหนดโดยการมีอยู่ของคุณสมบัติพื้นฐานสองประการ

หลักการความเหมาะสมของ Bellman

แนวคิดหลักของวิธีการนี้คือ หลักการความเหมาะสมของ Bellman (อังกฤษ Bellman's principle of optimality) ซึ่งกล่าวว่า ไม่ว่าสถานะเริ่มต้นและการตัดสินใจเริ่มต้นจะเป็นอย่างไร การตัดสินใจในขั้นถัดไปจะต้องประกอบกันเป็นกลยุทธ์ที่เหมาะสมที่สุดเทียบกับสถานะที่ได้มาจากการตัดสินใจครั้งแรก

กล่าวอีกนัยหนึ่ง ส่วนใดก็ตามของเส้นทางที่เหมาะสมที่สุดก็เป็นเส้นทางที่เหมาะสมที่สุดในตัวมันเอง คุณสมบัตินี้ช่วยให้สามารถแบ่งปัญหาโดยรวมออกเป็นลำดับของปัญหาย่อยที่ง่ายกว่าและแก้ได้แบบ recursive

ปัญหาย่อยที่ทับซ้อนกัน

ปัญหาจะมีคุณสมบัติ ปัญหาย่อยที่ทับซ้อนกัน (อังกฤษ overlapping subproblems) หากในการแก้ปัญหาแบบ recursive ปัญหาย่อยเดิมเกิดขึ้นซ้ำหลายครั้ง DP ช่วยหลีกเลี่ยงการคำนวณซ้ำโดยการเก็บบันทึกคำตอบของปัญหาย่อยที่พบแล้ว (เทคนิคนี้เรียกว่า memoization หรือ tabulation) ซึ่งเพิ่มประสิทธิภาพได้อย่างมากเมื่อเทียบกับการค้นหาแบบ recursive แบบธรรมดา

สมการ Bellman

จากหลักการความเหมาะสมจะได้ความสัมพันธ์เวียนเกิดพื้นฐานของวิธีการ ซึ่งเรียกว่า สมการ Bellman มันเชื่อมโยง "มูลค่า" (ผลตอบแทนหรือต้นทุนที่เหมาะสมที่สุด) ของสถานะปัจจุบันกับมูลค่าของสถานะถัดไป ในรูปแบบทั่วไปสำหรับกระบวนการหลายขั้นตอนแบบ deterministic ที่มีฟังก์ชันเป้าหมายแบบ additive มีรูปแบบดังนี้:

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

โดยที่:

• $k$ — หมายเลขขั้นตอน (จาก $m$ ถึง 1);
• $x$ — สถานะของระบบที่ขั้นตอน $k-1$;
• $y$ — การตัดสินใจที่ควบคุมได้ซึ่งทำในขั้นตอน $k$;
• ${\phi }_k(x,y)$ — ผลตอบแทน (หรือต้นทุน) ที่ขั้นตอน k;
• $f_k(x,y)$ — ฟังก์ชันที่กำหนดสถานะใหม่ของระบบ;
• $V_k(s)$ — ค่าเหมาะสมที่สุดของฟังก์ชันเป้าหมายสำหรับปัญหาย่อยที่เริ่มต้นที่ขั้นตอน $k$ ในสถานะ $s$

สมการนี้แก้ตามลำดับ โดยทั่วไปจะแก้ "จากท้าย" โดยเคลื่อนจากขั้นตอนสุดท้ายไปยังขั้นตอนแรก

ตัวอย่างการประยุกต์ใช้

• ปัญหาเส้นทางสั้นที่สุดในกราฟ: ปัญหานี้มีคุณสมบัติโครงสร้างย่อยที่เหมาะสมที่สุด เนื่องจากส่วนใดก็ตามของเส้นทางสั้นที่สุดก็เป็นเส้นทางสั้นที่สุดในตัวเอง อัลกอริทึม Bellman-Ford และ Floyd-Warshall เป็นตัวอย่างคลาสสิกของการประยุกต์ใช้ DP เพื่อแก้ปัญหานี้
• ปัญหากระเป๋าเป้: ปัญหาการบรรจุกระเป๋าเป้ที่มีความจุจำกัดด้วยสิ่งของที่มีมูลค่าและน้ำหนักต่างกันให้เหมาะสมที่สุด DP ช่วยให้แก้ปัญหานี้ได้โดยพิจารณาสิ่งของทีละชิ้นและคำนวณมูลค่าสูงสุดสำหรับค่าความจุที่เหลือทุกค่าในแต่ละขั้นตอน
• ปัญหาการจัดสรรทรัพยากร: การจัดสรรทรัพยากรที่จำกัด (เช่น การลงทุน) ระหว่างโครงการหลายโครงการเพื่อให้ได้ผลรวมสูงสุด

ข้อจำกัด

ข้อจำกัดหลักของวิธีการนี้คือ คำสาปแห่งมิติ (อังกฤษ curse of dimensionality) — คำศัพท์ที่ Bellman บัญญัติขึ้นเพื่อบ่งบอกถึงการเพิ่มขึ้นแบบ exponential ของจำนวนสถานะ และด้วยเหตุนี้จึงเพิ่มความซับซ้อนในการคำนวณ เมื่อจำนวนตัวแปรที่อธิบายสถานะของระบบเพิ่มขึ้น สิ่งนี้จำกัดการประยุกต์ใช้งานจริงของ DP แบบแม่นยำสำหรับปัญหาที่มีขนาดใหญ่มาก

แนวคิดที่เกี่ยวข้อง

• การวิจัยเชิงปฏิบัติการ
• ทฤษฎีการควบคุมที่เหมาะสมที่สุด
• กระบวนการตัดสินใจแบบ Markov (การขยายแบบ stochastic)
• สมการ Hamilton–Jacobi–Bellman (สมการแอนะล็อกสำหรับเวลาต่อเนื่อง)

หมายเหตุ

</references>