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

แก้ปัญหา Minimum Cost Path ใน C บนเมทริกซ์ 2D ที่แต่ละเซลล์มีต้นทุนเดินทาง หาเส้นทางจากมุมซ้ายบน (0,0) ไปมุมขวาล่าง (m,n) ต้นทุนรวมน้อยที่สุด เดินได้เฉพาะลงและขวา

Dynamic Programming ดีกว่า Recursion สำหรับปัญหานี้

Given cost matrix cost[][] และตำแหน่ง (m,n) เขียนฟังก์ชันคืนค่าต้นทุนต่ำสุดจาก (0,0) ถึง (m,n) ต้นทุนรวม = ผลรวมต้นทุนบนเส้นทาง (รวมต้นทางและปลายทาง)

สมมติฐาน: ต้นทุนเป็นบวกทั้งหมด ไม่มี negative cost cycles

ตัวอย่าง

หา minimum cost path ถึง (2,2)

เส้นทาง: (0,0) → (0,1) → (1,2) → (2,2) ค่า = 8 (1+2+2+3)

แนวทาง

สร้าง solution matrix ขนาดเท่าเดิม เติมแบบ bottom-up

solution[i][j] = A[0][j] if i=0 (แถวแรก)
               = A[i][0] if j=0 (คอลัมน์แรก)
               = A[i][j] + Min(solution[i-1][j], solution[i][j-1]) if i>0 && j>0

สร้าง minimumCostPath table ขนาด m,n

minimumCostPath[0][0] = costMatrix[0][0]
minimumCostPath[i][0] = minimumCostPath[i-1][0] + costMatrix[i][0]  (i>0)
minimumCostPath[0][j] = minimumCostPath[0][j-1] + costMatrix[0][j]  (j>0)
minimumCostPath[i][j] = costMatrix[i][j] + min(minimumCostPath[i-1][j-1], minimumCostPath[i-1][j], minimumCostPath[i][j-1])

Time complexity: O(mn)

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

#include <iostream>
using namespace std;

int min_(int a, int b, int c) {
    if (a < b) return (a < c) ? a : c;
    else return (b < c) ? b : c;
}

int min_cost(int cost[4][4], int m, int n) {
    int i, j;
    int tot_cost[4][4];
    tot_cost[0][0] = cost[0][0];
    for (i = 1; i <= m; i++) tot_cost[i][0] = tot_cost[i-1][0] + cost[i][0];
    for (j = 1; j <= n; j++) tot_cost[0][j] = tot_cost[0][j-1] + cost[0][j];
    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            tot_cost[i][j] = min_(tot_cost[i-1][j-1], tot_cost[i-1][j], tot_cost[i][j-1]) + cost[i][j];
    return tot_cost[m][n];
}

int main() {
    int cost[4][4] = {{9, 9, 4}, {8, 0, 9}, {1, 2, 8}};
    cout << "The minimum cost is " << min_cost(cost, 2, 2);
    return 0;
}

เอาต์พุต

The minimum cost is 17