ওজনহীন গ্রাফের জন্য ভ্রমণ বিক্রয়কর্মী সমস্যা সমাধানের জন্য C++ প্রোগ্রাম

ভ্রমণ সেলসম্যান সমস্যা সমস্ত শহরকে কভার করার জন্য এবং মূল শহরে ফিরে আসার জন্য সংক্ষিপ্ততম রুট গণনা করতে ব্যবহার করুন। এই পদ্ধতিটি একটি গ্রাফের সমস্ত নোড কভার করার জন্য সবচেয়ে ছোট পথ খুঁজে বের করতে ব্যবহার করা হয়।

এটি একটি ওজনহীন গ্রাফের সংক্ষিপ্ততম রুট খুঁজে বের করার প্রোগ্রাম৷

অ্যালগরিদম

Begin
   Define a variable vr = 4 universally.
   Declare an integer function TSP to implement Travelling salesman Problem.
   Declare a graph grph[][] as a 2D matrix and variable p to the integer datatype.
   Pass them as a parameter.
   Declare variable ver to the vector datatype.
   for (int i = 0; i < vr; i++)
      if (i != p) then
         Call push_back(i) function to store the value of all vertex except source vertex.
         Initialize m_p = INT_MAX to store minimum weight of a graph.
      do
         Declare cur_pth, k to the integer datatype.
            initialize cur_pth = 0.
            initialize 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) to update the value of minimum weight.
         while (next_permutation(ver.begin(), ver.end())).
         Return m_p.
   Declare a graph grph[][] as a 2D matrix to the integer datatype.
      Initialize values of grph[][] graph.
   Declare variable p to the integer datatype.
      Initialize p = 0.
   Print “The result is: ”.
   Print the return value of TSP() function.
End.

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
#define vr 4
int TSP(int grph[][vr], int p) // implement traveling Salesman Problem. {
   vector<int> ver; //
   for (int i = 0; i < vr; i++)
      if (i != p)
         ver.push_back(i);
         int m_p = INT_MAX; // store minimum weight of a graph
   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); // to update the value of minimum weight
   }
   while (next_permutation(ver.begin(), ver.end()));
   return m_p;
}
int main() {
   int grph[][vr] = { { 0, 5, 10, 15 }, //values of a graph in a form of matrix
      { 5, 0, 20, 30 },
      { 10, 20, 0, 35 },
      { 15, 30, 35, 0 }
   };
   int p = 0;
   cout<< "\n The result is: "<< TSP(grph, p) << endl;
   return 0;
}

আউটপুট

The result is: 75