C++ में अनवेटेड ग्राफ के लिए ट्रैवलिंग सेल्समैन प्रॉब्लम हल करना

ट्रैवलिंग सेल्समैन प्रॉब्लम का उपयोग सभी शहरों को कवर करने और मूल शहर पर वापस आने के लिए सबसे छोटे मार्ग की गणना के लिए किया जाता है। इस विधि का उपयोग ग्राफ के सभी नोड्स को कवर करने के लिए सबसे छोटा पथ खोजने के लिए किया जाता है।

यह अनवेटेड ग्राफ के सबसे छोटे मार्ग को खोजने का प्रोग्राम है।

एल्गोरिदम

Begin
    vr = 4 वेरिएबल को वैश्विक रूप से परिभाषित करें
    TSP इंटीजर फंक्शन घोषित करें ट्रैवलिंग सेल्समैन प्रॉब्लम लागू करने के लिए
    grph[][] को 2D मैट्रिक्स और p वेरिएबल को इंटीजर डेटाटाइप के रूप में घोषित करें
    उन्हें पैरामीटर के रूप में पास करें
    ver वेरिएबल को वेक्टर डेटाटाइप के रूप में घोषित करें
    for (int i = 0; i < vr; i++)
        if (i != p) then
            push_back(i) फंक्शन कॉल करें सोर्स वर्टेक्स को छोड़कर सभी वर्टेक्स का मान स्टोर करने के लिए
        m_p = INT_MAX इनिशियलाइज़ करें ग्राफ के न्यूनतम वजन को स्टोर करने के लिए
        do
            cur_pth, k को इंटीजर डेटाटाइप के रूप में घोषित करें
            cur_pth = 0 इनिशियलाइज़ करें
            k = p इनिशियलाइज़ करें
            for (int i = 0; i < ver.size(); i++)
                cur_pth += grph[k][ver[i]]
                k = ver[i]
            cur_pth += grph[k][p]
            m_p = min(m_p, cur_pth) न्यूनतम वजन का मान अपडेट करने के लिए
        while (next_permutation(ver.begin(), ver.end()))
        return m_p
    
    grph[][] को इंटीजर डेटाटाइप के 2D मैट्रिक्स के रूप में घोषित करें
        grph[][] ग्राफ के मान इनिशियलाइज़ करें
    p वेरिएबल को इंटीजर डेटाटाइप के रूप में घोषित करें
        p = 0 इनिशियलाइज़ करें
    "The result is: " प्रिंट करें
    TSP() फंक्शन का रिटर्न मान प्रिंट करें
End

उदाहरण

#include <bits/stdc++.h>
using namespace std;

#define vr 4

int TSP(int grph[][vr], int p) { // ट्रैवलिंग सेल्समैन प्रॉब्लम लागू करें
    vector<int> ver;
    for (int i = 0; i < vr; i++)
        if (i != p)
            ver.push_back(i);
    
    int m_p = INT_MAX; // ग्राफ के न्यूनतम वजन को स्टोर करें
    do {
        int cur_pth = 0;
        int k = p;
        for (int i = 0; i < ver.size(); i++) {
            cur_pth += grph[k][ver[i]];
            k = ver[i];
        }
        cur_pth += grph[k][p];
        m_p = min(m_p, cur_pth); // न्यूनतम वजन का मान अपडेट करें
    } while (next_permutation(ver.begin(), ver.end()));
    return m_p;
}

int main() {
    int grph[][vr] = { { 0, 5, 10, 15 }, // मैट्रिक्स के रूप में ग्राफ के मान
                       { 5, 0, 20, 30 },
                       { 10, 20, 0, 35 },
                       { 15, 30, 35, 0 }
                     };
    int p = 0;
    cout << "\nThe result is: " << TSP(grph, p) << endl;
    return 0;
}

आउटपुट

The result is: 75