C प्रोग्राम फॉर मिनिमम कॉस्ट पाथ

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

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

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

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

उदाहरण

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

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

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

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

दिया गया - arrA[][]। प्रत्येक सेल पर, हमारे पास 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] = (0, 0) से (i, j) तक पहुंचने का न्यूनतम मान

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

minimumCostPath[0][0] = costMatrix[0][0]
minimumCostPath[i][0] = minimumCostPath[i-1][0] + costMatrix[i][0], for all i > 0
minimumCostPath[0][j] = minimumCostPath[0][j-1] + costMatrix[0][j], for all j > 0

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

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

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

डायनामिक प्रोग्रामिंग एल्गोरिदम की समय जटिलता 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