सी न्यूनतम लागत पथ के लिए कार्यक्रम

यहां, हम सी में न्यूनतम लागत पथ की समस्या को हल करेंगे। निहितार्थ 2 डी-मैट्रिक्स पर किया जाता है जहां प्रत्येक सेल में यात्रा करने की लागत होती है। हमें न्यूनतम यात्रा लागत के साथ बाएं शीर्ष कोने से नीचे दाएं कोने तक का रास्ता खोजना होगा। आप किसी दिए गए सेल से केवल नीचे और दाएँ निचले सेल को पार कर सकते हैं।

इस विशेष समस्या को हल करने के लिए डायनेमिक प्रोग्रामिंग रिकर्सन की तुलना में बेहतर है।

दिया गया लागत मैट्रिक्स c ost[ ][ ] और एक स्थिति (m,n) , हमें एक फ़ंक्शन लिखना है जो (0,0) से (एम, एन) तक पहुंचने के लिए न्यूनतम पथ की लागत लौटाता है। पहुंचने के लिए पथ की कुल लागत (एम, एन) उस पथ पर सभी लागतों का योग है (स्रोत और गंतव्य दोनों सहित)।

धारणा - सभी लागत सकारात्मक हैं। इनपुट मैट्रिक्स में नकारात्मक लागत चक्र मौजूद नहीं हैं

उदाहरण

(2,2) के लिए न्यूनतम लागत पथ खोजें

लागत छवि के भीतर ही दी गई है। पथ होगा (0, 0) (0, 1) ⇒ (1, 2) ⇒ (2, 2)। पथ का मान आठ (1 +2+2+ 3) है।

दृष्टिकोण - दिए गए मैट्रिक्स के समान आकार का एक उत्तर मैट्रिक्स बनाएं।

इस मैट्रिक्स को बॉटम-अप तरीके से भरें।

दिया गया - गिरफ्तारी[ ][ ]. प्रत्येक सेल में, हमारे पास 2 विकल्प होते हैं (दाएं या नीचे जाएं) और हम किसी भी i,j सेल के लिए उन 2 में से न्यूनतम का चयन कर सकते हैं।

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

एल्गोरिथम उत्तरों में अपनाए गए दृष्टिकोण का उपयोग गतिशील प्रोग्रामिंग को लागू करके इस समस्या को कुशलतापूर्वक हल करने के लिए किया जा सकता है। m,n आकार की न्यूनतम लागत पथ तालिका बनाएं और परिभाषित करें−

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

स्पष्ट रूप से,

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

इसके बाद, हम एक समान फॉर्मूला लागू करके न्यूनतम लागत पथ मैट्रिक्स भरेंगे जिसे हमने एल्गोरिदम में लागू किया था। चूंकि पिछले सभी मानों की गणना पहले से ही न्यूनतम लागत पथ मैट्रिक्स के भीतर की जा चुकी होगी, हम इनकी पुनर्गणना नहीं करेंगे जैसा कि हमने एल्गोरिथम उत्तर में किया था।

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

यहां, न्यूनतम कॉस्टपाथ [i] [जे] की गणना के लिए हम न्यूनतम कॉस्टपाथ [i - 1] [जे -1], न्यूनतम कॉस्टपाथ [आई -1] [जे] और न्यूनतम कॉस्टपाथ [आई] [जे -1] का उपयोग करते हैं। ये एकमात्र अनुमेय सेल हैं जिनसे हम न्यूनतम कॉस्टपाथ [i] [j] तक पहुंचेंगे। अंत में, हम न्यूनतम कॉस्टपाथ [एम] [एन] लौटाते हैं।

डायनेमिक प्रोग्रामिंग एल्गोरिथम की समय जटिलता O(mn) है।

उदाहरण

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

आउटपुट

The minimum cost is 17