Program C untuk laluan kos minimum

Di sini kami akan menyelesaikan masalah laluan kos minimum dalam bahasa C. Ini bertujuan untuk dilakukan pada matriks 2D di mana setiap sel mempunyai kos pergerakan. Kita mesti mencari laluan dari sudut kiri atas ke sudut kanan bawah dengan kos perjalanan minimum. Anda hanya boleh melintasi sel ke bawah dan ke kanan dari sel tertentu.

Untuk menyelesaikan masalah khusus ini, pengaturcaraan dinamik adalah lebih baik daripada rekursi.

Memandangkan matriks kos c ost[ ][ ] dan kedudukan (m,n), kita perlu menulis fungsi yang mengembalikan kos laluan minimum dari (0,0) kepada (m,n) kepada (m Jumlah kos laluan, n), ialah jumlah semua kos pada laluan itu (termasuk sumber dan destinasi).

Anggap− bahawa semua kos adalah positif. Tiada kitaran kos negatif dalam matriks input

Contoh

Cari laluan kos minimum ke (2,2)

Kos diberikan dalam imej itu sendiri. Laluan akan menjadi (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2). Laluan mempunyai nilai 8 (1 +2+2+ 3).

Kaedah− Mencipta matriks jawapan yang serupa dengan saiz matriks yang diberikan.

Isi matriks ini dengan cara dari bawah ke atas.

Diberikan − arrA[ ][ ]. Dalam setiap sel kita mempunyai 2 pilihan (kanan atau bawah) dan untuk mana-mana sel i,j kita boleh memilih minimum 2 pilihan ini.

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

Pendekatan yang diikuti dalam jawapan algoritma boleh menyelesaikan masalah ini dengan cekap dengan menggunakan pengaturcaraan dinamik. Buat jadual laluan kos minimum bersaiz m,n dan tentukan -

minimumCostPath[i][j] = minimum value to achieve (i, j) from (0, 0)

Jelas sekali,

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

Seterusnya, kami akan mengisi matriks laluan kos minimum dengan menggunakan formula yang sama seperti yang digunakan dalam algoritma. Oleh kerana semua nilai sebelumnya telah dikira dalam matriks laluan kos minimum, kami tidak mengira semula nilai ini seperti dalam jawapan algoritma.

minimumCostPath[i][j] = costMatrix[i][j] +minimum(minimumCostPath[i - 1][j - 1],minimumCostPath[i - 1][j],minimumCostPath[i][j - 1])

Di sini, untuk mengira minimumCostPath[i][j], kami cenderung menggunakan minimumCostPath[i - 1][j - 1], minimumCostPath[i - 1][j] dan minimumCostPath[i][j - 1] Akibatnya, ini adalah satu-satunya sel yang dibenarkan di mana kita mencapai minimumCostPath[i][j]. Akhir sekali, kami mengembalikan minimumCostPath[m][n].

Kerumitan masa algoritma pengaturcaraan dinamik ialah O(mn).

Contoh

Demonstrasi masa nyata

#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;
}

Output

The minimum cost is 17

Atas ialah kandungan terperinci Program C untuk laluan kos minimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!