Programme C pour le chemin à coût minimum

Ici, nous allons résoudre le problème du chemin du coût minimum en langage C. Ceci est censé être fait sur une matrice 2D où chaque cellule a un coût de mouvement. Nous devons trouver un chemin du coin supérieur gauche au coin inférieur droit avec le coût de déplacement minimum. Vous ne pouvez parcourir les cellules que vers le bas et vers la droite à partir d’une cellule donnée.

Pour résoudre ce problème spécifique, la programmation dynamique vaut mieux que la récursivité.

Étant donné la matrice de coût c ost[ ][ ] et la position (m,n), nous devons écrire une fonction qui renvoie le coût minimum du chemin de (0,0) à (m,n) à ( m Le coût total d'un chemin, n), est la somme de tous les coûts sur ce chemin (y compris la source et la destination).

Supposons− que tous les coûts sont positifs. Il n'y a pas de cycle de coût négatif dans la matrice d'entrée

Exemple

Trouvez le chemin du coût minimum vers (2,2)

Le coût est donné dans l'image elle-même. Le chemin sera (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2). Le chemin a une valeur de 8 (1 +2+2+ 3).

Méthode− Crée une matrice de réponses de taille similaire à la matrice donnée.

Remplissez cette matrice de bas en haut.

Étant donné − arrA[ ][ ]. Dans chaque cellule, nous avons 2 options (droite ou bas) et pour toute cellule i,j, nous pouvons choisir le minimum de ces 2 options.

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

L'approche suivie dans la réponse de l'algorithme peut résoudre ce problème efficacement en appliquant une programmation dynamique. Créez une table de chemin de coût minimum de taille m,n et définissez -

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

Évidemment,

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

Ensuite, nous remplirons la matrice de chemin de coût minimum en appliquant une formule similaire à celle appliquée dans l'algorithme. Étant donné que toutes les valeurs précédentes ont été calculées dans la matrice du chemin de coût minimum, nous ne recalculons pas ces valeurs comme dans la réponse de l'algorithme.

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

Ici, afin de calculer minimumCostPath[i][j], nous avons tendance à utiliser minimumCostPath[i - 1][j - 1], minimumCostPath[i - 1][j] et minimumCostPath[i][j - 1] Par conséquent, ce sont les seules cellules autorisées où nous atteignons minimumCostPath[i][j]. Enfin, nous renvoyons minimumCostPath[m][n].

La complexité temporelle de l'algorithme de programmation dynamique est O(mn).

Exemple

Démonstration en temps réel

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

Sortie

The minimum cost is 17

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!