Skip to content
กลับไปยังผลการค้นหา

การโปรแกรมเชิงพลวัต

ผู้เสนอ
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)
  • การควบคุมที่เหมาะสมที่สุดและการปรับพอร์ตโฟลิโอหลายช่วงเวลาในเศรษฐศาสตร์และวิศวกรรมศาสตร์

วิธีการทำงาน

วิธีการทำงาน

1

ปัญหาการหาค่าเหมาะสมที่สุดโดยรวมจะแสดงในรูปของความสัมพันธ์เวียนเกิด สำหรับแต่ละสถานะ 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]
2

ความสัมพันธ์เวียนเกิดจะถูกแก้ไขซ้ำๆ หรือเรียกซ้ำ ในการวนซ้ำค่า (value iteration) V^*(s) จะถูกอัปเดตซ้ำๆ ในทุกสถานะจนกว่าจะบรรจบกัน โดยใช้ค่าประมาณปัจจุบันของค่าสถานะข้างเคียง การอัปเดตแต่ละครั้งจะแทนที่ค่าเก่าด้วยรางวัลบวกค่าในอนาคตที่ดีที่สุดที่สามารถทำได้ ซึ่งเป็นการเผยแพร่ข้อมูลความเหมาะสมที่สุดผ่านปริภูมิสถานะ

สูตร
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)
3

ค่าที่คำนวณได้จะถูกเก็บไว้ในตารางที่จัดทำดัชนีตามสถานะ สถานะสุดท้ายจะได้รับค่าพื้นฐานเป็นศูนย์ (หรือรางวัลที่ทราบ) และรายการอื่นๆ ทั้งหมดจะถูกเติมเมื่อปัญหาย่อยได้รับการแก้ไข การจำ (Memoization) ทำให้แน่ใจว่าแต่ละสถานะจะถูกประเมินอย่างมากที่สุดเพียงครั้งเดียว ลดการค้นหาแบบเรียกซ้ำแบบเอกซ์โพเนนเชียลให้เป็นเวลาพหุนามตามจำนวนสถานะและขั้นตอน

สูตร
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}
4

เมื่อตารางค่าเสร็จสมบูรณ์ นโยบายที่เหมาะสมที่สุด 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 แบบประมาณที่เรียนรู้ฟังก์ชันค่าจากปฏิสัมพันธ์ แทนที่จะเรียนรู้จากแบบจำลองที่ชัดเจน

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.

    ISBN: 978-0-691-07951-6
    คัดลอกแล้ว