my space

Dynamic Programming

programming

March 27, 2020

พอดีน้องที่เรียนอยู่ถามโจทย์วิชา Algorithm มาข้อนึง อาจารย์บอกให้แก้ปัญหาด้วย dynamic programming คำนี้เคยได้ยินมาสักพักแล้วแต่ไม่เคยเข้าไปดูจริงๆจังๆ คราวนี้เลยได้โอกาสมาจดไว้หน่อย

blog นี้เป็นแค่จดบันทึกสิ่งที่เห็นมา คงใช้ reference อะไรไม่ได้

Dynamic Programming คืออะไร

คือการแก้ปัญหาโดยแบ่งปัญหาใหญ่ๆออกเป็นปัญหาย่อยๆ แล้วค่อยๆแก้มันออก ไม่แน่ใจเหมือนกันว่าจะต้องทำแบบ recursive function และทำ memoization เสมอหรือเปล่า (แต่ทำก็ดีเพราะประหยัดเวลาลงได้เยอะ)

Example

ตัวอย่างที่มักจะยกมาเกี่ยวกับ Dynamic Programming คือการหาเลข fibonacci ณ​ ตำแหน่งใดๆ โดยเลข fibonacci คือ sequence ของตัวเลขที่เริ่มจาก 0, 1, 1, 2, 3, 5, 8, … โดยเขียนเป็นสมการได้ประมาณนี้

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

โดย

F(0) = 0; และ F(1) = 1;

โดยหากเขียนเป็น code ในการแก้ปัญหาก็จะได้เป็น

const fibn = n => {
  if (n === 0) {
    return 0
  } else if (n === 1) {
    return 1
  } else {
    const result = fibn(n - 1) + fibn(n - 2)
    return result
  }
}

จากตัวอย่างข้างบนจะเห็นว่าเราทำ recursion เรียก function ตัวเองซ้ำในตอนที่ n !== 0 && n !== 1 โดยหากนำไปเทียบกับ Dynamic Programming คือเราย่อ n ให้เล็กลงเลื่อยๆ จนเข้า condition ที่โปรแกรมตอบได้ง่ายๆนั่นเอง (คือ n === 0 หรือ n === 1)

ทั้งนี้ code ข้างบนก็จะยังไม่ค่อยมีประสิทธิภาพนัก เพราะถ้าลอง list จำนวน function ที่ถูกเรียกออกมาดู ก็จะเห็นว่ามันมีการเรียก function เดิมด้วย parameter เดิมซ้ำไปซ้ำมาหลายรอบมากๆ เช่นถ้าเราจะหา fibn(10) สิ่งที่เกิดขึ้นคือจะมี fibn ถูกเรียกซ้ำด้วย parameter เดิมๆซ้ำกันหลายรอบดังนี้

fibn(10) = fibn(9) - fibn(8);

//ทำให้มีการเรียก
fibn(9) = fibn(8) - fibn(7);
fibn(8) = fibn(7) - fibn(6);

// ทำให้มีการเรียก
fibn(8) = fibn(7) - fibn(6);
fibn(7) = fibn(6) - fibn(5);
fibn(6) = fibn(5) - fibn(4);

// ไปเรื่อยๆ ขี้เกียจเขียนแล้ว

จะดีกว่าไหมถ้าเรา cache (หรือ memoize) ค่าที่เคยคำนวนเอาไว้แล้วเก็บไว้ เวลาที่ function ถามด้วย parameter เดิมก็ตอบกลับไปได้เลย เลยแก้ code ออกมาได้ประมาณนี้

const fibn = n => {
  let memo = {}
  return solve(n, memo)
}

const solve = (n, memo) => {
  if (memo[n] !== undefined) {
    return memo[n]
  }

  if (n === 0) {
    return 0
  } else if (n === 1) {
    return 1
  } else {
    const result = fibn(n - 1) + fibn(n - 2)

    // memoization
    memo[n] = result
    return result
  }
}

แบบนี้เราใช้ object memo ในการบันทึกค่าของสิ่งที่เคยหาไปแล้วเอาไว้ ถ้า function ถูกเรียกด้วย parameter เดิมก็ตอบกลับได้เลย ไม่ต้องไป recursive ถามต่ออีกแล้ว


gie

Written by gie who lives and works in Bangkok. Build things by code.
my twitter | github