Ở đây, chúng ta sẽ giải quyết vấn đề đường dẫn chi phí tối thiểu trong C. Hàm ý được thực hiện trên ma trận 2D trong đó mỗi ô có một chi phí di chuyển. Chúng ta phải tìm một con đường từ góc trên cùng bên trái đến góc dưới cùng bên phải với chi phí đi lại tối thiểu. Bạn chỉ có thể duyệt xuống các ô thấp hơn và sang phải từ một ô nhất định.
Để giải quyết vấn đề cụ thể này, lập trình động tốt hơn nhiều so với phương pháp đệ quy.
Cho trước ma trận chi phí c ost [] [] và một vị trí (m, n) , chúng ta phải viết một hàm trả về chi phí của con đường tối thiểu để đến (m, n) từ (0,0). Tổng chi phí của một con đường để đến (m, n) là tổng của tất cả các chi phí trên con đường đó (bao gồm cả nguồn và đích).
Giả định - Tất cả các chi phí đều dương. Chu kỳ chi phí âm không tồn tại trong ma trận đầu vào
Ví dụ
Tìm đường dẫn chi phí tối thiểu đến (2,2)
Các chi phí được đưa ra trong chính hình ảnh. Đường đi sẽ là (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2). Giá trị của đường dẫn là tám (1 + 2 + 2 + 3).
Phương pháp tiếp cận - Tạo ma trận câu trả lời có kích thước tương tự như ma trận đã cho.
Điền vào ma trận này theo cách từ dưới lên.
Đã cho - arrA [] []. Tại mỗi ô, chúng tôi có 2 tùy chọn (đi sang phải hoặc xuống dưới) và chúng tôi có thể chọn tối thiểu 2 tùy chọn đó cho bất kỳ ô thứ i, j nào.
solution[i][j]=A[0][j] if i=0, 1st row =A[i][0] if j=0, 1st column =A[i][j]+Min(solution[i=1],[j],solution[i][j-1]) if i>0 && j>0
Cách tiếp cận theo sau trong các câu trả lời thuật toán có thể được sử dụng để giải quyết vấn đề này một cách hiệu quả bằng cách áp dụng lập trình động. Tạo bảng đường dẫn chi phí tối thiểu có kích thước m, n và xác định−
minimumCostPath[i][j] = minimum value to achieve (i, j) from (0, 0)
Rõ ràng,
minimumCostPath[0][0] = costMatrix[0][0] minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0], for all values of i > zero minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j], for all values of j >zero
Tiếp theo, chúng tôi sẽ điền vào ma trận đường dẫn chi phí tối thiểu bằng cách áp dụng một công thức tương tự mà chúng tôi đã áp dụng trong thuật toán. Vì tất cả các giá trị trước đó đã được tính toán trong ma trận đường dẫn chi phí tối thiểu, chúng tôi sẽ không tính toán lại những giá trị này như đã làm trong câu trả lời theo thuật toán.
minimumCostPath[i][j] = costMatrix[i][j] +minimum(minimumCostPath[i - 1][j - 1],minimumCostPath[i - 1][j],minimumCostPath[i][j - 1])
Ở đây, để tính toán đường dẫn tối thiểu [i] [j], chúng tôi có xu hướng sử dụng đường dẫn tối thiểu [i - 1] [j - 1], đường dẫn tối thiểu [i - 1] [j] và đường dẫn tối thiểu [i] [j - 1], đây là những ô duy nhất được phép mà từ đó chúng ta sẽ đạt tới MinimumCostPath [i] [j]. Cuối cùng, chúng tôi trả về MinimumCostPath [m] [n].
Độ phức tạp về thời gian của thuật toán lập trình động là O (mn).
Ví dụ
#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;
} Đầu ra
The minimum cost is 17