de algorismoKratui++
DP I : Overlapping Subproblem
  • Dynamic Programming หรือย่อว่า DP คือแบบแผนของการเขียนอัลกอริทึมที่แบ่งปัญหาใหญ่ออกเป็นปัญหาย่อย ๆ และเก็บคำตอบของปัญหาเหล่านั้นไว้เพื่อป้องกันการคำนวนสิ่งเดิมซ้ำอีก

    ในตอนนี้เราจะพูดถึงการแก้ปัญหาที่มี Overlapping Subproblem ซึ่งเป็นปัญหาที่ตรงกับนิยามที่ให้ไปข้างบนเลย คือมีการคำนวนที่ซ้ำซ้อน  ตัวอย่างคลาสสิกของ DP คือเรื่องของการหาลำดับ Fibonacci (คิดว่าทุกคนคงรู้จัก Fibonacci อยู่แล้ว) นั้นคือลำดับที่เกิดจากการบวกกันของสองตัวก่อนหน้า

    0, 1, 1, 2, 3, 5, 8, 13, ...
    (ในทางคอมพิวเตอร์จะเพิ่ม 0 ขึ้นมาเป็นตัวแรก)

    เราสามารถเขียนโปรแกรมหาเลข Fibonacci ในลำดับต่าง ๆ ได้ด้วยฟังก์ชัน Recurrsive ง่าย ๆ ดังนี้

    1. int fibonacci(int n) {
    2. if(n==0 || n==1)
    3. return n;
    4. return fibonacci(n-1)+fibonacci(n-2);
    5. }

    ฟังก์ชันนี้ทำงานได้นะ เว้นเสียแต่พอค่า n เริ่มมากขึ้น เอาสัก 40 กว่าก็พอ เราจะสังเกตุได้เลยว่าโปรแกรมทำงานช้ามาก ทำไม? มาดูกัน  สมมุติเราเรียก fibonacci(6) สิ่งที่โปรแกรมนี้เรียกใช้คือ

    สังเหตุว่าฟังก์ชันจะถูกเรียกขึ้นทีละสองครั้ง ๆ ดังนั้นจะมี O(2^n) แน่นอนว่ามันห่วยบรม

    ด้วยหลัักของ DP คือเราจะเก็บคำตอบของปัญหาย่อย ๆ เอาไวัเพื่อที่จะได้ไม่ต้องคำนวนใหม่ ซึ่งในนี้ก็มีฟังก์ชันที่ถูกเรียกใช้หลายครั้งอยู่เต็มไปหมด งั้นเราลองแก้ไขปัญหานี้กัน โดยเราจะเก็บค่าของ fibonacci(n) ไว้ในอาเรย์ val ตำแหน่งที่ n และจะส่งค่า val[n] กลับไป

    1. int fibonacci(int n) {
    2. static int val[50] = {};
    3. if(n==0 || n==1)
    4. val[n] = n;
    5. else if(val[n] == 0)
    6. val[n] = fibonacci(n-1)+fibonacci(n-2);
    7. return val[n];
    8. }

    (ที่กำหนดขนาดแค่ 50 เพราะแค่นี้ก็เกิน int ธรรมดาแล้ว)

    พอเป็นแบบนี้แล้ว อัลกอของเราจะเหลือเพียง O(n) เท่านั้น วิธีนี้เรียกว่า Memoization ซึ่งเป็นการแก้ปัญหาแบบ Top-Down คือทำจากข้างหน้าลงไป ซึ่งเราก็มีวิธีอีกวิธีหนึ่ง คือแบบ Tabulation หรือ Bottom-Up เริ่มทำจากส่วนท้ายของปัญหาก่อน คือเรารู้ว่าสุดท้ายแล้วมันจะมาจบที่ fibonacci(0) = 0 และ fibonacci(1) = 1 ดังนั้นเราจะเริ่มทำจากตรงนี้

    1. int fibonacci(int n) {
    2. int val[50];
    3. val[0] = 0;
    4. val[1] = 1;
    5. for (int i = 2; i <= n; i++)
    6. val[i] = val[i-1]+val[i-2];
    7. return val[n];
    8. }

    ซึ่งทั้งสองวิธีต่างก็จำคำตอบย่อยทั้งสิ้น และทำงานในเวลาที่ใกล้เคียงกัน แต่ Tabulation จะมีข้อได้เปรียบตรงที่ในวีธี memoization เมื่อจำนวน stack ของการ recursive มีมาก ๆ แล้วบางทีจะเกิด error ขึ้นได้  แต่สำหรับ tabulation จะมีเยอะเพียงใดก็ได้ตราบที่ตัวแปรที่ใช้ลูปเก็บไหว

    ในตอนต่อไปเราจะพูดถึงเรื่องของ Optimal Substructure ซึ่งเป็นปัญหาอีกรูปแบบหนึ่งที่การทำ DP จะมีประโยชน์อย่างมาก

    ติดตามต่อใน  DP II : Optimal Substructure
    อ้างอิงจาก https://www.geeksforgeeks.org/dynamic-programming-set-1/

Views

เข้าสู่ระบบเพื่อแสดงความคิดเห็น

Log in