การโปรแกรมเชิงพลวัต
- ผู้เสนอ
- Richard Bellman
- ปี
- 1957
- ประเภท
- Exact combinatorial optimization via recursive decomposition
- กลุ่มวิธี
- Mathematical programming
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การโปรแกรมเชิงพลวัต (DP) เป็นเทคนิคการหาค่าเหมาะสมที่สุดแบบแม่นตรงที่ริชาร์ด เบลล์แมน คิดค้นขึ้นในปี 1957 เพื่อแก้ปัญหาการตัดสินใจหลายขั้นตอน โดยจะแยกย่อยปัญหาที่ซับซ้อนออกเป็นปัญหาย่อยที่ง่ายกว่าและทับซ้อนกัน แก้ไขปัญหาย่อยแต่ละครั้งและเก็บผลลัพธ์ไว้เพื่อหลีกเลี่ยงการคำนวณซ้ำซ้อน DP ตั้งอยู่บนหลักการของความเหมาะสมที่สุด (Principle of Optimality) ซึ่งรับประกันผลลัพธ์ที่เหมาะสมที่สุดทั่วโลกเมื่อปัญหามีลักษณะของปัญหาย่อยที่ทับซ้อนกันและโครงสร้างย่อยที่เหมาะสมที่สุด
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพการวางแผนเส้นทางที่สั้นที่สุดทั่วเมือง โดยเริ่มจากการหาเส้นทางที่สั้นที่สุดระหว่างทุกคู่ของทางแยกที่อยู่ใกล้เคียง จากนั้นจึงรวมคำตอบเล็กๆ เหล่านั้นขึ้นไป แทนที่จะสำรวจเส้นทางเต็มรูปแบบที่เป็นไปได้ทั้งหมดใหม่ตั้งแต่ต้น คุณจะใช้คำตอบเฉพาะที่คำนวณไว้ล่วงหน้า การโปรแกรมเชิงพลวัตทำงานในลักษณะเดียวกัน คือการเก็บคำตอบของปัญหาย่อยเล็กๆ ไว้ เพื่อให้การสร้างคำตอบเต็มรูปแบบต้องอาศัยเพียงการค้นหาในตาราง แทนที่จะต้องคำนวณซ้ำๆ ที่หนักหน่วง
ประวัติศาสตร์
ริชาร์ด เบลล์แมน เป็นผู้บัญญัติศัพท์ 'dynamic programming' ในปี 1957 ขณะทำงานที่ RAND Corporation โดยจงใจเลือกคำว่า 'programming' เพื่อหมายถึงการวางแผน แทนที่จะเป็นการเขียนโค้ดคอมพิวเตอร์ หลักการของความเหมาะสมที่สุดที่เขากล่าวไว้ได้กลายเป็นรากฐานทางทฤษฎีสำหรับทฤษฎีการควบคุม การวิจัยดำเนินงาน และต่อมาคือการเรียนรู้แบบเสริมกำลัง อัลกอริทึม DP แบบคลาสสิก เช่น เส้นทางที่สั้นที่สุดของ Dijkstra, อัลกอริทึม Viterbi และตัวจัดแนวลำดับ Needleman-Wunsch ล้วนมีที่มาจากกรอบการทำงานของเบลล์แมนโดยตรง
ควรใช้เมื่อใด
การโปรแกรมเชิงพลวัตมีความเหมาะสมเมื่อปัญหามีปัญหาย่อยที่ทับซ้อนกันและโครงสร้างย่อยที่เหมาะสมที่สุด ซึ่งเป็นคุณสมบัติที่พบได้ทั่วไปในการตัดสินใจตามลำดับ การจัดสรรทรัพยากร การจัดตารางเวลา และงานการจัดแนวสตริง จำเป็นต้องสามารถแจงนับปริภูมิสถานะได้อย่างสมบูรณ์และมีขนาดที่จัดการได้ วิธีนี้จะประสบปัญหาคำสาปแห่งมิติ (curse of dimensionality) เมื่อตัวแปรสถานะมีจำนวนมากหรือต่อเนื่อง สำหรับปัญหาที่มีปริภูมิสถานะที่แก้ไขไม่ได้ การโปรแกรมเชิงพลวัตแบบประมาณ (approximate DP) หรือการเรียนรู้แบบเสริมกำลัง (reinforcement learning) เป็นทางเลือกที่ดีกว่า
ข้อจำกัดและข้อควรพิจารณา
- ประสบปัญหาคำสาปแห่งมิติ: ข้อกำหนดด้านหน่วยความจำและเวลาเพิ่มขึ้นแบบเอกซ์โพเนนเชียลตามจำนวนตัวแปรสถานะ
- ต้องการความรู้เบื้องต้นที่สมบูรณ์เกี่ยวกับโครงสร้างการเปลี่ยนผ่านและฟังก์ชันรางวัล ไม่สามารถนำไปใช้กับสภาพแวดล้อมที่ไม่รู้จักได้หากไม่มีการประมาณค่า
- ปริภูมิสถานะต้องเป็นแบบไม่ต่อเนื่องหรือสามารถทำให้ไม่ต่อเนื่องได้ ปัญหาที่มีมิติสูงและต่อเนื่องต้องการแผนการประมาณค่าที่ยอมสละความแม่นยำ
- การกำหนดรูปแบบปัญหาการแสดงสถานะและความสัมพันธ์เวียนเกิดที่ถูกต้องต้องอาศัยความเข้าใจเชิงลึกเฉพาะปัญหาอย่างมาก
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รับประกันผลลัพธ์ที่เหมาะสมที่สุดทั่วโลกอย่างแม่นยำสำหรับปัญหาที่สอดคล้องกับหลักการของความเหมาะสมที่สุด
- กำจัดการคำนวณซ้ำซ้อนผ่านการจำ ทำให้ได้เวลาพหุนามตามจำนวนสถานะ
- สร้างนโยบายที่เหมาะสมที่สุดที่ชัดเจน ไม่ใช่เพียงแค่ค่าที่เหมาะสมที่สุด ทำให้การสนับสนุนการตัดสินใจเป็นไปอย่างตรงไปตรงมา
- สามารถนำไปประยุกต์ใช้ได้อย่างกว้างขวางในหลากหลายสาขา รวมถึงทฤษฎีการควบคุม ชีวสารสนเทศศาสตร์ เศรษฐศาสตร์ และการวิจัยดำเนินงาน
การประยุกต์ใช้
- ปัญหาเส้นทางที่สั้นที่สุดและปัญหาการหาเส้นทางในเครือข่าย (Bellman-Ford, Dijkstra variants)
- การจัดแนวลำดับในชีววิทยาเชิงคำนวณ (อัลกอริทึม Needleman-Wunsch, Smith-Waterman)
- การจัดสรรทรัพยากรที่เหมาะสมที่สุดและปัญหาการจัดกลุ่มประเภทกระเป๋าเป้ (knapsack-type) ในการวิจัยดำเนินงาน
- การรู้จำเสียงพูดและลายมือผ่านอัลกอริทึม Viterbi บนแบบจำลองมาร์คอฟซ่อนเร้น (Hidden Markov Models)
- การควบคุมที่เหมาะสมที่สุดและการปรับพอร์ตโฟลิโอหลายช่วงเวลาในเศรษฐศาสตร์และวิศวกรรมศาสตร์
วิธีการทำงาน
วิธีการทำงาน
ปัญหาการหาค่าเหมาะสมที่สุดโดยรวมจะแสดงในรูปของความสัมพันธ์เวียนเกิด สำหรับแต่ละสถานะ s และขั้นตอนการตัดสินใจ n ฟังก์ชันค่า V_n(s) จะเท่ากับรางวัลทันทีที่ดีที่สุด บวกกับค่าที่ลดทอนของสถานะถัดไปที่เกิดขึ้น สมการเบลล์แมน (Bellman equation) นี้ทำให้หลักการของความเหมาะสมที่สุดเป็นรูปธรรม: เส้นทางย่อยใดๆ ของเส้นทางที่เหมาะสมที่สุดจะต้องเหมาะสมที่สุดในตัวเอง
สูตร
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]ความสัมพันธ์เวียนเกิดจะถูกแก้ไขซ้ำๆ หรือเรียกซ้ำ ในการวนซ้ำค่า (value iteration) V^*(s) จะถูกอัปเดตซ้ำๆ ในทุกสถานะจนกว่าจะบรรจบกัน โดยใช้ค่าประมาณปัจจุบันของค่าสถานะข้างเคียง การอัปเดตแต่ละครั้งจะแทนที่ค่าเก่าด้วยรางวัลบวกค่าในอนาคตที่ดีที่สุดที่สามารถทำได้ ซึ่งเป็นการเผยแพร่ข้อมูลความเหมาะสมที่สุดผ่านปริภูมิสถานะ
สูตร
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)ค่าที่คำนวณได้จะถูกเก็บไว้ในตารางที่จัดทำดัชนีตามสถานะ สถานะสุดท้ายจะได้รับค่าพื้นฐานเป็นศูนย์ (หรือรางวัลที่ทราบ) และรายการอื่นๆ ทั้งหมดจะถูกเติมเมื่อปัญหาย่อยได้รับการแก้ไข การจำ (Memoization) ทำให้แน่ใจว่าแต่ละสถานะจะถูกประเมินอย่างมากที่สุดเพียงครั้งเดียว ลดการค้นหาแบบเรียกซ้ำแบบเอกซ์โพเนนเชียลให้เป็นเวลาพหุนามตามจำนวนสถานะและขั้นตอน
สูตร
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}เมื่อตารางค่าเสร็จสมบูรณ์ นโยบายที่เหมาะสมที่สุด pi^*(s) จะถูกกู้คืนโดยการผ่านแบบละโมบ (greedy pass) อย่างง่าย: สำหรับแต่ละสถานะ ให้เลือกการกระทำที่เพิ่มรางวัลทันที บวกกับค่าที่เก็บไว้ของสถานะถัดไป การดึงข้อมูลแบบผ่านครั้งเดียวนี้มีค่าใช้จ่ายในการคำนวณต่ำและให้กฎการตัดสินใจที่แน่นอนและเหมาะสมที่สุดทั่วโลก
สูตร
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]ข้อผิดพลาดที่พบบ่อย
- การกำหนดรูปแบบการแสดงสถานะที่ไม่เพียงพอจะนำไปสู่ความสัมพันธ์เวียนเกิดที่ไม่ถูกต้องและผลลัพธ์ที่ไม่เหมาะสมที่สุด
- การสับสนระหว่างการจำแบบบนลงล่าง (top-down memoization) กับการจัดตารางแบบล่างขึ้นบน (bottom-up tabulation) อาจทำให้เกิดข้อผิดพลาด stack overflow หรือลำดับการประเมินปัญหาย่อยที่ไม่ถูกต้อง
- การใช้ DP กับปัญหาที่ขาดโครงสร้างย่อยที่เหมาะสมที่สุด (เช่น เส้นทางที่ยาวที่สุดในกราฟทั่วไป) จะให้ผลลัพธ์ที่ไม่ถูกต้องโดยไม่มีการเตือน
- การละเลยความแม่นยำของตัวเลขในการคำนวณรางวัลสะสมอาจทำให้เกิดข้อผิดพลาดความเหมาะสมที่สุดที่ซับซ้อนในการใช้งานแบบจุดลอยตัว
คำถามที่พบบ่อย
อะไรคือความแตกต่างระหว่างการโปรแกรมเชิงพลวัตกับการแบ่งแยกและเอาชนะ (divide-and-conquer)?
ทั้งสองวิธีแยกย่อยปัญหาออกเป็นปัญหาย่อย แต่การแบ่งแยกและเอาชนะจะสมมติว่าปัญหาย่อยเป็นอิสระและแก้ไขเพียงครั้งเดียวตามธรรมชาติ การโปรแกรมเชิงพลวัตมีเป้าหมายที่ปัญหาย่อยที่ทับซ้อนกัน — ปัญหาย่อยเดียวกันปรากฏในหลายสาขา — และทำการจำผลลัพธ์เพื่อหลีกเลี่ยงงานที่ซ้ำซ้อน หากไม่มีปัญหาย่อยที่ทับซ้อนกัน DP จะไม่ให้ข้อได้เปรียบในการคำนวณเหนือกว่าการเรียกซ้ำแบบตรงไปตรงมา
เมื่อใดที่ฉันควรใช้การจำแบบบนลงล่างเทียบกับการจัดตารางแบบล่างขึ้นบน?
การจำแบบบนลงล่างง่ายต่อการนำไปใช้โดยตรงจากความสัมพันธ์เวียนเกิดและคำนวณเฉพาะปัญหาย่อยที่จำเป็น ซึ่งเป็นประโยชน์ต่อปริภูมิสถานะที่เบาบาง การจัดตารางแบบล่างขึ้นบนหลีกเลี่ยงค่าใช้จ่ายในการเรียกซ้ำและข้อจำกัดของสแต็ก เหมาะสำหรับปริภูมิสถานะที่หนาแน่น และมักจะเร็วกว่าในทางปฏิบัติ เลือกแบบบนลงล่างเมื่อชุดปัญหาย่อยที่จำเป็นยากต่อการคาดการณ์ เลือกแบบล่างขึ้นบนเมื่อปัญหาย่อยทั้งหมดจะถูกต้องการ
การโปรแกรมเชิงพลวัตเกี่ยวข้องกับการเรียนรู้แบบเสริมกำลังอย่างไร?
DP แบบคลาสสิกต้องการแบบจำลองกระบวนการตัดสินใจของมาร์คอฟ (Markov Decision Process) ที่ทราบอย่างสมบูรณ์ (ความน่าจะเป็นในการเปลี่ยนสถานะและรางวัล) การเรียนรู้แบบเสริมกำลังขยายแนวคิด DP ไปยังสถานการณ์ที่แบบจำลองไม่เป็นที่รู้จัก โดยใช้ประสบการณ์ที่สุ่มตัวอย่างแทน อัลกอริทึมเช่น Q-learning และวิธีการไล่ระดับนโยบาย (policy gradient methods) เป็นขั้นตอน DP แบบประมาณที่เรียนรู้ฟังก์ชันค่าจากปฏิสัมพันธ์ แทนที่จะเรียนรู้จากแบบจำลองที่ชัดเจน
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
ISBN: 978-0-691-07951-6คัดลอกแล้ว