Skip to main content

dynamic-programming

การทำความเข้าใจเกี่ยวกับ Dynamic Programming (DP)​

Dynamic Programming (DP) เป็นเทคนิคที่ใช้ในการแก้ปัญหาที่ซับซ้อน โดยการแบ่งปัญหาหลักให้กลายเป็นปัญหาย่อย ๆ ซึ่งสามารถแก้ไขได้อย่างมีประสิทธิภาพ โดยการเก็บผลลัพธ์ของปัญหาย่อยที่ได้คำนวณแล้ว เพื่อหลีกเลี่ยงการคำนวณซ้ำซ้อนในภายหลัง (การทำ Memoization หรือ Tabulation) จึงทำให้สามารถลดเวลาในการคำนวณจาก O(2^n) เป็น O(n) หรือ O(n^2) ขึ้นอยู่กับปัญหาที่กำลังแก้ไข

1. หลักการของ Dynamic Programming​

การใช้ Dynamic Programming จะมีสองวิธีหลักคือ Memoization และ Tabulation ซึ่งทั้งสองวิธีมีแนวคิดพื้นฐานในการแก้ปัญหาดังนี้:

  1. Memoization (Top-Down Approach):

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

  2. Tabulation (Bottom-Up Approach):

    • เริ่มจากการแก้ปัญหาย่อย ๆ ก่อน แล้วค่อย ๆ รวมผลลัพธ์เหล่านั้นเพื่อให้ได้ผลลัพธ์ของปัญหาหลัก
    • ไม่ใช้การเรียกฟังก์ชันซ้ำ (ไม่มี Recursion)
    • ใช้ Iteration ในการคำนวณ

2. ลักษณะของปัญหาที่เหมาะกับ Dynamic Programming​

การใช้ Dynamic Programming จะเหมาะสมกับปัญหาที่มีคุณสมบัติสองประการหลัก คือ:

  1. Overlapping Subproblems (ปัญหาย่อยที่ซ้ำกัน):

    • ปัญหาหลักสามารถแบ่งออกเป็นปัญหาย่อยหลาย ๆ ครั้ง ซึ่งบางปัญหาย่อยจะถูกคำนวณซ้ำหลายครั้ง
    • Dynamic Programming จะช่วยเก็บผลลัพธ์ของปัญหาย่อยเหล่านี้เพื่อนำกลับมาใช้ใหม่แทนที่จะคำนวณใหม่ทุกครั้ง

  2. Optimal Substructure (โครงสร้างที่ดีที่สุดของปัญหาย่อย):

    • ผลลัพธ์ของปัญหาหลักสามารถคำนวณได้จากผลลัพธ์ของปัญหาย่อยที่ดีที่สุด
    • Dynamic Programming จะคำนวณผลลัพธ์ของปัญหาย่อยและใช้ผลลัพธ์เหล่านั้นในการคำนวณผลลัพธ์ของปัญหาหลัก

3. การใช้ Dynamic Programming: ตัวอย่างปัญหาคลาสสิก​

1. Fibonacci Sequence (ลำดับฟีโบนัชชี)​

ปัญหาคลาสสิกที่สุดใน Dynamic Programming คือการหาค่าลำดับฟีโบนัชชี:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2)

โดยปกติแล้ว เราสามารถใช้ Recursion ในการหาค่าฟีโบนัชชีได้ แต่การคำนวณจะซ้ำซ้อนมากและช้า โดยเฉพาะเมื่อ n มีค่ามาก

การใช้ Memoization (Top-Down)​

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(10))  # ผลลัพธ์: 55

การใช้ Tabulation (Bottom-Up)​

def fibonacci_tab(n):
    if n <= 1:
        return n
    fib = [0] * (n + 1)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]

print(fibonacci_tab(10))  # ผลลัพธ์: 55

2. Knapsack Problem (ปัญหายัดกระเป๋า)​

ปัญหา Knapsack เป็นปัญหาคลาสสิกใน Dynamic Programming ที่เราต้องเลือกไอเท็มบางอย่างจากชุดของไอเท็มที่มีขนาดและมูลค่าต่างกัน เพื่อให้รวมมูลค่าสูงสุดโดยไม่เกินน้ำหนักที่กำหนด

ปัญหาคลาสสิก:​

  • เรามีชุดของไอเท็มที่แต่ละชิ้นมีน้ำหนักและมูลค่า
  • เรามี capacity ของกระเป๋าที่จำกัด
  • เราต้องเลือกไอเท็มที่สามารถบรรจุในกระเป๋าเพื่อให้ได้มูลค่าสูงสุด

การใช้ Tabulation (Bottom-Up)​

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]

weights = [1, 2, 3, 8, 7, 4]
values = [20, 5, 10, 40, 15, 25]
capacity = 10

print(knapsack(weights, values, capacity))  # ผลลัพธ์: 60

4. ข้อดีและข้อเสียของ Dynamic Programming​

ข้อดี:​

  • ประสิทธิภาพ: Dynamic Programming ช่วยลดการคำนวณซ้ำซ้อน โดยการเก็บผลลัพธ์ของปัญหาย่อยที่ได้คำนวณแล้วใน Memoization Table หรือ Tabulation Table
  • แก้ปัญหาที่ซับซ้อน: สามารถใช้ในการแก้ปัญหาที่ซับซ้อนได้ โดยการแบ่งปัญหาย่อย ๆ ที่สามารถคำนวณได้แยกกัน

ข้อเสีย:​

  • ใช้หน่วยความจำมาก: การใช้ Memoization หรือ Tabulation อาจจะใช้พื้นที่หน่วยความจำมาก โดยเฉพาะเมื่อมีจำนวนปัญหาย่อยมาก
  • ต้องมีโครงสร้างที่เหมาะสม: การใช้ Dynamic Programming ต้องมั่นใจว่าปัญหามี Optimal Substructure และ Overlapping Subproblems เพื่อให้การใช้เทคนิคนี้มีประสิทธิภาพ

5. สรุป​

Dynamic Programming เป็นเทคนิคการแก้ปัญหาที่ใช้ในการคำนวณปัญหาที่มีลักษณะของ Overlapping Subproblems และ Optimal Substructure โดยการแบ่งปัญหาหลักให้กลายเป็นปัญหาย่อย ๆ และเก็บผลลัพธ์ของปัญหาย่อยเพื่อหลีกเลี่ยงการคำนวณซ้ำ การใช้ Memoization หรือ Tabulation จะช่วยให้การคำนวณปัญหาที่ซับซ้อนสามารถทำได้เร็วขึ้นและมีประสิทธิภาพมากขึ้น