เรื่องจิ๊บๆ กับ Dynamic programming

วันนี้นึกครึ้ม... ⛅ อยากเขียนเรื่องพื้นๆ Dynamic programming ไว้สักหน่อย... 😃

Dynamic programming (DP) เป็นเทคนิคหนึ่งสำหรับแก้ปัญหาที่ซับซ้อน โดยการแก้ปัญหาย่อย (ปัญหาที่มีขนาดเล็กลงมา) ตั้งแต่ปัญหาขนาดย่อยที่สุดขึ้นมาก่อน แล้วค่อย ๆ เพิ่มขอบเขตขึ้นมาจนถึงปัญหาที่มีขนาดใหญ่ที่สุด

เนื่องจากตัว ปัญหาย่อย (Subproblem) ที่แก้เป็นปัญหาที่มีลักษณะเหมือนกัน แค่มีข้อมูลให้จัดการน้อยกว่า ดังนั้นวิธีการแก้ปัญหา Dynamic programming (DP) มักจะต้องแก้ด้วย recursive function หรือไม่ก็ต้องใช้สูตรคณิตศาสตร์ทีมีลักษณะเป็นสมการเวียนเกิด (recurrence formula)

เริ่มจากหาคำตอบจากปัญหาย่อย มารวมกันจนได้คำตอบของปัญหาใหญ่

โจทย์ที่เราต้องใช้งาน DP ส่วนใหญ่แล้วตัวปัญหาย่อยจะมีลักษณะดังนี้

• ปัญหาย่อยที่ซ้อนทับกัน (Overlapping Subproblem) คือ เมื่อย่อยขนาดปัญหาใหญ่มาเป็นปัญหาย่อยแล้ว จะพบว่าได้ปัญหาย่อยเหมือนกันซ้ำกันมาก หากเราจดคำตอบไว้ (memoization) ก็จะทำให้เราไม่ต้องเสียเวลาคิดซ้ำ ๆ
• โครงสร้างย่อยที่เหมาะสมที่สุด (Optimal Substructure) หากคำตอบของปัญหาใหญ่เป็นคำตอบที่ดีที่สุด ตัวคำตอบของปัญหาย่อยก็ต้องดีที่สุดตามไปด้วย ดังนั้น ในการแก้โจทย์ เราทราบเพียงแค่คำตอบที่ดีที่สุดของปัญหาย่อยแต่ละปัญหาย่อย แล้วเลือกนำมาดัดแปลงเพิ่มเติมเป็นคำตอบของปัญหาใหญ่ก็พอแล้ว ไม่ต้องเก็บทุกคำตอบที่เป็นไปได้

ในการแก้ปัญหา DP จะมีขั้นตอนที่สามารถนำมาใช้แก้ได้ คือ

1. กำหนดปัญหาให้ชัดเจน (กำหนดเป็นฟังก์ชันว่าต้องรับข้อมูลอะไร และ return ข้อมูลอะไร ให้เอื้อกับการทำ recursive function)
2. หาคำตอบของปัญหาใหญ่จากปัญหาย่อย
3. เขียนสูตรออกมาในรูปทั่วไป (เขียน recurrence formula และกำหนด base case)
4. วิเคราะห์ Time Complexity และ Space Complexity
5. Implement! ทำได้สองวิธีคือ Top-down Approach และ Bottom-up Approach

Recursive Function

เรามาเริ่มทำความรู้จักมันให้ดีขึ้น ด้วย โจทย์สุด classic เลย คือ Fibonacci

Fibonacci sequence - Wikipedia

Wikimedia Foundation, Inc.Contributors to Wikimedia projects

อธิบายคร่าวๆ Fibonacci number คือ ลำดับ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 … โดยแต่ละหมายเลขในลำดับจะการบวกตัวเลขสองตัวที่อยู่ก่อนหน้ามัน

ถ้าเราเอามาเขียน code แบบ For Loop ธรรมดาๆ ก็จะเป็นแบบนี้

function fibonacciNoRecursion(n){
  if (n < 0) return undefined;
  if (n === 0) return 0;
  let previous = 1;
  let sum = 1;
  for (let i = 3; i <= n; i++){
    let temp = sum;
    sum += previous;
    previous = temp;
  }
  return sum
}

การเขียนแบบนี้ ถ้าเรามาดูเรื่องของความซับซ้อนของมัน (Big O ) มันจะอยู่ในรูปแบบของ O(n) หรือ linear time complexity

เมื่อเราเห็นความซ้ำซ้อนของมัน หรือ อาจจะจำโจทย์นี้ได้ เราก็จะคิดเลยว่า มันต้องใช้ Dynamic programming ก็เลยจัดโค๊ดไปหนึ่งชุด

function fib(n){
  if (n < 0) return undefined;
  if (n < 2) return n;
  return fib(n-1) + fib(n-2)
}

อย่างเจ๋ง... ดูเป็นคนเก่งไปอีกขั้น แต่เมื่อที่เรามาดูความซับซ้อนของมัน ดันเป็น O(2^n) หรือ exponential

หนักกว่าแบบไม่มี recursive อีก มันหมายความว่า เวลาที่เราใช้ recursive ถ้าค่ามันยิ่งเยอะ มันก็จะยิ่งใช้เวลานานขึ้น

ทำไมถึงเป็นอย่างนั้น ขออธิบายด้วยภาพ คิดว่าดูภาพนี้แล้วน่าจะเข้าใจ

ลองนึกภาพดูว่าถ้าตัวเลขเป็น 10,000 มันจะแตกเป็น tree ได้ขนาดไหน...

ส่วนใหญ่ เวลาให้ทำโจทย์ dynamic programming หลายๆ คนก็จะมาจบแค่ตรงนี้กัน

ถ้าเราเขียนแค่นี้ มันก็เป็นแค่ recursive function ธรรมดาๆ เท่านั้นเอง

Dynamic programming

ถ้าเราอยากใช้งาน dynamic programming (DP) จริงๆ จำง่ายๆ เลยว่า มัน คือ

recursive function + cache

แปลง่ายๆ ว่า "ทำ cache ให้มันด้วย"

เราอาจจะเจอเขาใช้คำว่า Memorization / Memory แต่ผมขอใช้คำว่า cache แทนละกัน อาจจะเข้าใจกันง่ายมากกว่า

function fibonacciWithCache(n, cache = {}) {
  if (n < 0) return undefined;
  if (n < 2) return n;

  if (!cache[n]) {
    cache[n] = fibonacciWithCache(n - 1) + fibonacciWithCache(n - 2);
  }
  return cache[n];
}

ถ้าการโยน cache ไปกับ function ด้วย มันดูเข้าใจยากไป ให้ลองเอาตัวแปล cache ออกมาเป็น global ดู เผื่อเข้าใจง่ายขึ้น

let cache = {};

function fibonacci(n) {
  if (n < 0) return undefined;
  if (n < 2) return n;

  if (!cache[n]) {
    cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
  }
  return cache[n];
}

เท่านี้การทำงานของ recursive function ของเราก็จะทำงานเร็วขึ้น เพราะมันไม่ต้องเรียก function เดิมซ้ำ เวลาทำงานก็จะกลับมาเป็น O(n) แล้ว

เมื่อเราทำการเก็บค่าที่คำนวนก่อนหน้าไว้แล้ว จาก tree ก็จะกลายเป็น linear หรือ เส้นตรงเลย โดยที่เราไม่จำเป็นต้องกลับไปคำนวนหาค่าที่เคยคำนวนไว้แล้ว

เท่านี้เราก็สามารถแก้โจทย์ที่เป็น dynamic programming ได้เกือบทั้งหมดแล้ว

แต่.... อย่าลืมว่า การทำ cache นั้น มันเป็นการเก็บข้อมูลลง memory

ดังนั้น ถ้าจะต้องคำนวนอะไรที่มันเยอะเกินไปมากๆ เมื่อถึงจุดหนึ่ง มันก็มีโอกาศเกิด Stack Overflow ได้

Stack Overflow

มันเป็นชื่อเรียกของ error ข้อผิดพลาดชนิดหนึ่งในการเขียนโปรแกรม ที่มีสาเหตุจากหน่วยความจำไม่พอ

ที่เราเรียกกันว่า stack มันระเบิด 💥

ดังนั้น ถ้าหากเราเอา recursive มาใช้งาน จนถึงจุดที่ทำให้ stack มันระเบิดแล้ว ก็ได้เวลาเอา recursive ออก แล้วไปใช้งาน For Loop แทน (ซึ่งมันจะเขียนยากกว่า)

โดยทั่วไปแล้ว พวกโจทย์ที่เป็น dynamic programming ถ้าเราเริ่มต้นที่ for loop เลย บางทีมันอาจจะยากไปและทำให้งงได้ แต่ถ้าเราเริ่มเขียนแบบ dynamic programming ก่อนแล้วค่อยเปลี่ยนเป็น for loop ทีหลังมันอาจจะง่ายกว่า (ส่วนนี้ขึ้นอยู่กับว่าใครถนัดแบบไหนด้วย)

คร่าวๆ ประมาณนี้สำหรับ dynamic programming จริงๆ ซึ่งด้านบนที่กล่าวมา มัน คือ เทคนิคที่เรียกว่า Memorization

และยังมีอีกตัวนึงที่ยังไม่ได้พูดถึงในบทความนี้ คือ Tabulation

หน้าตาโค๊ดมันจะประมาณนี้

function tabulatedFib(n){
  if (n === 1 || n === 2){
    return 1;
  }
  const fibNums = [0, 1, 1];
  for (let i = 3; i <= n; i++){
    fibNums[i] = fibNums[i-1] + fibNums[i-2];
  }
  return fibNums[n];
}

สรุปให้สั่นๆ คือ

• Memorization เหมาะกับการใช้แก้ปัญหาในรูปแบบ top-down เมื่อเรายังไม่รู้ว่าต้องแก้ปัญหาย่อยตัวไหนบ้าง โดยวิธีนี้มันจะแก้ปัญหาเฉพาะปัญหาย่อยที่ต้องการจริงๆ โดยเก็บผลลัพธ์ไว้เพื่อลดการคำนวณซ้ำ
• Tabulation เหมาะกับการใช้แก้ปัญหาในรูปแบบ bottom-up เมื่อเราต้องการหาคำตอบจากปัญหาย่อยเล็กที่สุดไปจนถึงปัญหาหลัก ใช้การบันทึกค่าผลลัพธ์ของทุกปัญหาย่อยตามลำดับในตาราง

ลองไปหาอ่านเพิ่มเติมกันได้ :)