Chương trình C cho bài toán Đường đi chi phí tối thiểu (Minimum Cost Path)

Giải bài toán Minimum Cost Path trên ma trận 2D, mỗi ô có chi phí di chuyển. Tìm đường từ góc trên-trái (0,0) đến góc dưới-phải (m,n) với chi phí nhỏ nhất. Chỉ được đi xuống hoặc sang phải.

Quy hoạch động tốt hơn đệ quy cho bài này.

Cho ma trận cost[][], vị trí (m,n). Hàm trả về chi phí nhỏ nhất từ (0,0) đến (m,n). Tổng chi phí = tổng chi phí các ô trên đường đi (kể cả đầu và cuối).

Giả định: Tất cả chi phí > 0. Không có chu trình chi phí âm.

Ví dụ

Tìm đường chi phí nhỏ nhất đến (2,2):

Đường đi: (0,0) → (0,1) → (1,2) → (2,2). Chi phí = 1+2+2+3 = 8.

Cách tiếp cận

Tạo ma trận giải (solution) cùng kích thước. Điền theo bottom-up.

solution[i][j] = A[0][j] nếu i=0 (hàng 1)
               = A[i][0] nếu j=0 (cột 1)
               = A[i][j] + Min(solution[i-1][j], solution[i][j-1]) nếu i>0 && j>0

Tạo bảng minimumCostPath[m][n]:

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

Độ phức tạp: O(m·n).

Ví dụ mã nguồn (C++)

#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 << "Chi phi nho nhat la: " << min_cost(cost, 2, 2);
    return 0;
}

Kết quả đầu ra

Chi phi nho nhat la: 17