โปรแกรม Python สำหรับ Min Cost Path (เส้นทางต้นทุนต่ำสุด)

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — กำหนดเมทริกซ์ต้นทุน (cost matrix) และตำแหน่ง (m, n) ให้หาต้นทุนของเส้นทางต่ำสุดเพื่อไปถึง (m, n) จาก (0, 0) แต่ละเซลล์แทนต้นทุนในการเดินทางจากเซลล์หนึ่งไปอีกเซลล์หนึ่ง

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

# วิธี Dynamic Programming
R = 3
C = 3

def minCost(cost, m, n):
    # เริ่มต้น
    tc = [[0 for x in range(C)] for x in range(R)]
    # กรณีฐาน
    tc[0][0] = cost[0][0]
    # อาร์เรย์ total cost (tc) - คอลัมน์แรก
    for i in range(1, m + 1):
        tc[i][0] = tc[i-1][0] + cost[i][0]
    # อาร์เรย์ tc - แถวแรก
    for j in range(1, n + 1):
        tc[0][j] = tc[0][j-1] + cost[0][j]
    # ส่วนที่เหลือของอาร์เรย์ tc
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j]
    return tc[m][n]

# โปรแกรมหลัก
cost = [[1, 5, 3],
        [7, 7, 4],
        [8, 5, 3]]
print("Total Cost:", minCost(cost, 2, 1))

ผลลัพธ์

Total Cost: 13

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ Min Cost Path โดยใช้ Dynamic Programming