d(s,t,m) = min1≤k≤n{ d(s,k,m-1) + g[k][t] }
โดยที่ g คือ adjacency matrix เมื่อนำ recurrence นี้ไปเขียนแบบตรงไปตรงมา จะได้โปรแกรมที่ทำงานช้ามาก ๆ n = 15 ก็ทนรอคำตอบไม่ไหว ถ้าดูให้ดีจะเห็นว่ามี overlapping subproblems เต็มไปหมด ก็เลยปรับแก้ด้วย memoization สั่งทำงาน แล้วเปรียบเทียบดูดังแสดงข้างล่างนี้
คราวนี้ปรับมาเขียนเป็น bottom-up dynamic programming จากแบบ memoization แล้วลองสั่งทำงานเพื่อเปรียบเทียบ แต่มาดูแบบ bottom-up นี้ พบว่า ความจริงแล้วคล้ายอัลกอริทึมของ Bellman-Ford มาก ๆ ซึ่งก็คือการ relax เส้นเชื่อมทุกเส้นที่ตึง เป็นจำนวน n-1 รอบ แต่เมื่อใดที่พบว่าไม่มีเส้นตึงแล้ว ก็เลิกได้ไม่ต้องทำต่อ จะพบว่าได้คำตอบที่เร็วกว่า (แต่ต้องเน้นว่า ในการทดลองนี้ เราสร้างกราฟที่มีเส้นเชื่อมสุ่มนะ)
ผู้อ่านลองคิดจากโปรแกรม และลองปรับ f(n,c) ดูว่า เป็นฟังก์ชันอะไร
สมชาย ประสิทธิ์จูตระกูล