Dynamic Programming and Python

Dynamic programming (DP) ใช้หลักการแบ่งปัญหา (problem) ออกเป็นปัญหาย่อย (sub problems) เพื่อให้ง่ายต่อการแก้ปัญหา แล้วนำผลลัพธ์ของแต่ละส่วนมาประกอบกัน [1][2][3]

ตัวอย่างมักถูกยกขึ้นเพื่อทำความเข้าใจคือการหา Fibonacci Number [4] ใน Fibonacci sequence ซึ่งหาได้จากสมการ

\( X_{n} = X_{n-1} + X_{n-2} \)

เมื่อ \( X_{n} \) คือ ค่าของตัวเลขในตำแหน่งที่ n

Fibonacci Sequence จะเริ่มต้นด้วย 0,1 ซึ่งเป็นตัวเลขในตำแหน่งที่ 1 และ 2  ดังนั้นตัวเลขในตำแหน่งที่ 3 ก็คือ 1+0 = 1  ตำแหน่งที่ 4 คือ 1+1 = 2 เป็นอย่างนี้เรื่อย ๆ ไป ดังนั้น Fibonacci Sequence จะเป็น 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

เขียน Python Script เพื่อหา Fibonacci Number แบบ Recursive

def Fibonacci(pos):
     if pos == 0 :
          return 0
     elif pos == 1 :
          return 1
     else :
          return Fibonacci(pos - 1) + Fibonacci(pos - 2)

การเขียนในลักษณะนี้ใช้งานได้ดีในกรณีที่ค่า pos ที่ส่งให้ไม่มากนัก หากมีค่ามากขึ้นไปจะต้องใช้การ recursive มากขึ้นไปเรื่อย ประสิทธิภาพจะลดลง

การนำแนวคิดของ DP มาใช้ จะทำให้ประสิทธิภาพการทำงานค่อนข้างคงที่ โดยการแยกปัญหาออกเป็นปัญหาย่อยโดยดูจากความสัมพันธ์ที่กำหนดไว้ด้วยสมการข้างบน

def Fibonacci(pos):
     fib = [0] * (pos +1) # create list with size = pos+1
     # from prior knowledge 
     fib[0] = 0
     fib[1] = 1
     for i in range(2,pos + 1):
           fib[i] = fib[i-1]+fib[i-2]
     return fib[-1]

จะเห็นว่ามีการใช้ array หรือ List มาใช้แทนการทำ recursive ซึ่งจะทำให้มีการทำงานเร็วขึ้นกว่า แต่ก็พึงระวังเรื่องขนาดของ array ด้วย ในกรณีที่ต้องการจัดการกับตัวเลขที่มีขนาดใหญ่ก็ควรใช้การแบ่งจำนวนออกเป็นส่วน ๆ (sub problems)

เอกสารประกอบ
[1] http://smo.sogang.ac.kr/doc/dy_birth.pdf
[2] https://en.wikipedia.org/wiki/Dynamic_programming
[3] https://en.wikipedia.org/wiki/Shortest_path_problem
[4] https://en.wikipedia.org/wiki/Fibonacci