C-Programm für minimale Kostenpfad

Hier werden wir das Problem des minimalen Kostenpfads in der C-Sprache lösen. Dies soll auf einer 2D-Matrix erfolgen, in der jede Zelle Bewegungskosten hat. Wir müssen einen Weg von der oberen linken Ecke zur unteren rechten Ecke mit minimalen Reisekosten finden. Sie können Zellen von einer bestimmten Zelle aus nur nach unten und rechts durchlaufen.

Um dieses spezielle Problem zu lösen, ist dynamische Programmierung besser als Rekursion.

Angesichts der Kostenmatrix c ost[ ][ ] und der Position (m,n) müssen wir eine Funktion schreiben, die die minimalen Pfadkosten von (0,0) nach (m,n) zurückgibt (m Die Gesamtkosten eines Pfades, n), sind die Summe aller Kosten auf diesem Pfad (einschließlich Quelle und Ziel).

Gehen Sie davon aus−, dass alle Kosten positiv sind. In der Eingabematrix gibt es keinen negativen Kostenzyklus

Beispiel

Finden Sie den Pfad mit den minimalen Kosten zu (2,2)

Die Kosten sind im Bild selbst angegeben. Der Pfad ist (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2). Der Wert von path ist 8 (1 +2+2+3).

Methode− Erstellt eine Antwortmatrix, deren Größe der angegebenen Matrix ähnelt.

Füllen Sie diese Matrix von unten nach oben.

Gegeben − arrA[ ][ ]. In jeder Zelle haben wir zwei Optionen (rechts oder unten) und für jede i,j-Zelle können wir das Minimum dieser beiden Optionen auswählen.

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

Der in der Algorithmus-Antwort verfolgte Ansatz kann dieses Problem durch die Anwendung dynamischer Programmierung effizient lösen. Erstellen Sie eine Pfadtabelle mit minimalen Kosten der Größe m,n und definieren Sie -

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

Natürlich

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

Als nächstes füllen wir die Pfadmatrix mit minimalen Kosten, indem wir eine ähnliche Formel wie im Algorithmus anwenden. Da alle vorherigen Werte innerhalb der Minimalkostenpfadmatrix berechnet wurden, berechnen wir diese Werte nicht wie in der Algorithmusantwort neu.

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

Hier verwenden wir zur Berechnung von MinimumCostPath[i][j] in der Regel MinimumCostPath[i - 1][j - 1], MinimumCostPath[i - 1][j] und MinimumCostPath[i][j - 1] Infolgedessen sind dies die einzigen zulässigen Zellen, in denen wir MinimumCostPath[i][j] erreichen. Schließlich geben wir MinimumCostPath[m][n] zurück.

Die zeitliche Komplexität des dynamischen Programmieralgorithmus beträgt O(mn).

Beispiel

Echtzeitdemonstration

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

Ausgabe

The minimum cost is 17

Das obige ist der detaillierte Inhalt vonC-Programm für minimale Kostenpfad. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!