ไดนามิกโปรแกรมมิงไม่ใช่มนตร์ดำ

ไดนามิกโปรแกรมมิงไม่ใช่เวทมนตร์

• ไดนามิกโปรแกรมมิงเป็นเทคนิคที่ใช้แก้ปัญหาซับซ้อน โดยแบ่งปัญหาออกเป็นปัญหาย่อย ๆ แล้วค่อยจัดการ
• เทคนิคนี้เป็นสิ่งที่เป็นธรรมชาติ และอัลกอริทึมทั่วไปจำนวนมากก็เป็นการนำไดนามิกโปรแกรมมิงไปใช้กับปัญหาเฉพาะอย่างหนึ่ง
• เพื่อช่วยให้เข้าใจไดนามิกโปรแกรมมิงมากขึ้น จึงมีการอธิบายแบบเกริ่นนำที่ง่ายกว่าและคำอธิบายอย่างละเอียด

คำบ่น

• วิศวกรรมซอฟต์แวร์มักตั้งชื่อสิ่งต่าง ๆ ได้แย่มาก
• คำอย่าง 'bootstrap', 'daemon', 'cascading style sheets', 'cookie', 'artificial intelligence' เป็นต้น ล้วนกำกวมหรือชวนให้เข้าใจผิด
• คำว่า 'ไดนามิกโปรแกรมมิง' เองก็ไม่ได้เกี่ยวข้องกับความ "ไดนามิก" ตามชื่อ แต่แท้จริงแล้วเป็นแนวคิดที่ใช้ในการออกแบบอัลกอริทึม

การแคชพื้นฐาน

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

การแคชแบบเพิ่มประสิทธิภาพ

• เมื่อใช้ memoization เราสามารถคงรูปแบบรีเคอร์ชันไว้ได้ แต่จะคำนวณเฉพาะสิ่งที่จำเป็นในเวลาที่ต้องใช้
• แต่อีกแนวทางหนึ่งคือคำนวณทุกอย่างที่ต้องใช้ไว้ล่วงหน้า
• วิธีนี้แก้ปัญหาได้โดยไม่ต้องเรียกรีเคอร์ชัน และนี่เองคือไดนามิกโปรแกรมมิง

ระยะห่างการแก้ไข

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

Advent of Code, Day 12

• ในโจทย์ Advent of Code วันที่ 12 ธันวาคม 2023 ต้องแก้ปัญหาโนโนแกรมแบบ 1 มิติ
• จะใช้วิธี brute force ก็ได้ แต่มีความซับซ้อนแบบเอ็กซ์โพเนนเชียล
• ทางเลือกที่ดีกว่าคือใช้ไดนามิกโปรแกรมมิงเพื่อแก้ปัญหาอย่างมีประสิทธิภาพ

บทสรุป

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

ความเห็นของ GN⁺

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

[GN⁺]

ความคิดเห็นจาก Hacker News

• บทความอธิบายอัลกอริทึม dynamic programming (DP) ว่าเป็นการทำแคชให้กับการเรียกซ้ำ ซึ่งเป็นจุดที่ดี

  • การหาวิธีแก้แบบเรียกซ้ำเป็นจุดเริ่มต้นที่เหมาะที่สุดในการหาคำตอบแบบ DP
  • การทำ memoization ให้กับวิธีแก้แบบเรียกซ้ำอาจช่วยเพิ่มความเร็วได้มาก
  • สิ่งสำคัญไม่ใช่ว่ามีปัญหาย่อยจำนวนมากใน call tree แต่คือต้องมีปัญหาย่อยที่ แตกต่างกันจริง ๆ อยู่ในจำนวนที่ค่อนข้างน้อย

• ชอบแนวทางของบทความที่เริ่มจากจัดการปัญหาแบบเรียกซ้ำก่อน แล้วค่อย ๆ เพิ่มแคชเข้าไป จากนั้นลดขนาดให้เหลือเท่าที่จำเป็น

  • เคยมีประสบการณ์ที่พยายามหาคำตอบแบบ dynamic programming โดยตรงแล้วตัน หรือไม่ก็ต้องใช้ความพยายามมาก
  • ต่อไปจะบังคับตัวเองให้ใช้วิธีเข้าหาแบบเป็นลำดับขั้นนี้

• หนึ่งในการประยุกต์ใช้ dynamic programming ที่ยอดเยี่ยมคือการจัดแนวลำดับแบบเป็นคู่ของลำดับกรดนิวคลีอิก/โปรตีน

  • ตัวอย่างเช่น sequence alignment, อัลกอริทึม Needleman–Wunsch, อัลกอริทึม Smith–Waterman

• มีการเล่าประสบการณ์เกี่ยวกับอาจารย์ด้านอัลกอริทึมที่เก่งมาก

  • อาจารย์ท่านนั้นเรียนที่ UCLA และการสอนเรื่อง dynamic programming นั้นยอดเยี่ยมมาก
  • เริ่มจากปัญหาง่าย ๆ แต่มีความซับซ้อนแบบ exponential จากนั้นแยกปัญหาออกเป็นปัญหาเล็ก ๆ ลดความซับซ้อนลงเป็น polynomial แล้วจึงใช้ memoization จนลดลงเหลือ linear
  • อยากจำได้ว่าใช้ปัญหาอะไรบ้าง

• แชร์ลิงก์ไปยังบทความ Dynamic Programming is not Black Magic

  • บทความดังกล่าวเข้าถึงได้ยากเพราะมีคนเข้าใช้งานจำนวนมาก (hug of death)

• มีความเห็นว่าถ้าเป็นคนที่เรียนเขียนโปรแกรมด้วยตัวเองเป็นหลัก ตอนหางานถ้าในสัมภาษณ์บอกให้ใช้ dynamic programming ก็คงจะไม่รู้จักมัน

  • โชคดีที่ไม่เคยเจอแบบนั้น และเพราะรู้เทคนิคนี้จึงได้ใช้มันในหลายการสัมภาษณ์

• ชื่อว่า "dynamic programming" อาจฟังดูเหมือนไม่ได้มาจากวงการ programming โดยตรง

  • ที่จริงแล้วมันเกี่ยวข้องกับ optimization และเป็นวิธีแก้ปัญหาการตัดสินใจในเวลาไม่ต่อเนื่อง
  • dynamic programming คือวิธีลดมิติของปัญหา optimization ลงอย่างมากด้วยการนิยาม value function V*

• มีการตั้งคำถามว่าการนึกถึงแค่ "memoization" เมื่อได้ยินคำว่า "dynamic programming" นั้นผิดหรือไม่

  • ส่วนที่อาจขาดไปคือการแบ่งปัญหาอย่างชาญฉลาดเพื่อให้ใช้ memoization ได้อย่างมีประสิทธิภาพ

• dynamic programming ไม่ใช่ black magic แต่สิ่งที่ยากคือการพิสูจน์ว่าปัญหานั้นสามารถทำเป็น dynamic programming ได้ และพิสูจน์ความถูกต้องของมัน

  • เช่นเดียวกับ greedy algorithm จำเป็นต้องมีการพิสูจน์อย่างเป็นทางการโดยใช้ mathematical induction

• มีการแนะนำหนังสืออัลกอริทึม DPV และคอร์สของ Udacity จาก Georgia Tech เพื่อให้เชี่ยวชาญ dynamic programming

  • สามารถเรียนรู้ dynamic programming ได้ด้วยการฝึกแก้โจทย์