ট্রাভেলিং সেলসম্যান প্রব্লেম (TSP) সব শহর ঘুরে এবং মূল শহরে ফিরে আসার জন্য সবচেয়ে ছোট রুট ক্যালকুলেট করতে ব্যবহৃত হয়। এই পদ্ধতিটি একটি গ্রাফের সব নোড কভার করার জন্য সবচেয়ে ছোট পাথ খুঁজে বের করতে ব্যবহৃত হয়।
এটি একটি অনওয়েটেড (unweighted) গ্রাফের সবচেয়ে ছোট রুট বের করার প্রোগ্রাম।
অ্যালগরিদম
শুরু
vr = 4 Универসালি ডিক্লেয়ার করুন
TSP() ইন্টিজার ফাংশন ডিক্লেয়ার করুন (ট্রাভেলিং সেলসম্যান প্রব্লেম ইমপ্লিমেন্ট করতে)
grph[][] 2D ম্যাট্রিক্স এবং p ভেরিয়েবল ইন্টিজার টাইপে ডিক্লেয়ার করুন
প্যারামিটার হিসেবে পাস করুন
ver ভেক্টর টাইপে ডিক্লেয়ার করুন
for (int i = 0; i < vr; i++)
যদি (i != p) হয়, তবে
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() ফাংশনের রিটার্ন মান প্রিন্ট করুন
শেষ
উদাহরণ কোড
#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 << "\n The result is: " << TSP(grph, p) << endl;
return 0;
}
আউটপুট
The result is: 75
