Traveling Salesman Problem Step By Step in Bangla

Traveling Salesman Problem 

ট্রাভেলিং সেলসম্যান

TSP তে সাধারনত একজন salesman এর এক শহর থেকে অন্যান্য শহরে গিয়ে আবার প্রথম শহরে ফিরে আসতে যে রুটে সব থেকে কম সময় লাগে সেই রুটের দূরত্ত্ব বের করতে হয়। Salesman অবশ্যই সব শহরে গিয়ে নিজ শহরে ফিরে আসতে হবে এবং এই কারনে এখানে হ্যামিল্টন Cycle থাকে। 

চিত্রের উল্লেখিত ভার্টেক্সগুলোকে যদি এক একটা শহর ধরি এবং এজ গুলোকে দূরত্ব তাহলে Salesman যদি 0 নম্বর ভার্টেক্স থেকে শুরু করে আবার 0 নম্বরেই ফিরে আসতে চায় তাহলে আমাদের 0 থেকে 1,2,3 হয়ে আবার 0 তে যেতে যত সম্ভাব্য সব পারমুটেশন বের করে সব থেকে মিনিমাম দূরত্ব বের করতে হবে। তাহলে ধাপে ধাপে আমরা সলুশন বের করার চেষ্টা করি।

১। প্রথমে কয়টি শহর থাকবে সেটা ইনপুট নিয়ে নিব যেটা n । এখানে n=4। তারপর গ্রাফ ইনপুট নেয়ার জন্য আমারা 2d array  নিব। কারন এক শহর থেকে অন্য শহর এর দূরত্ব নেয়ার জন্য অবশ্যই দুটি ইন্ডেক্স লাগবে। এর সাথে আমার স্টার্টিং ভার্টেক্স Initialize করে নিব যেটা s=0 । যেহেতু আমারা কোড এ 0 ইন্ডেক্সিং ইউজ করব তাই শহরগুলোর ভার্টেক্স হবে 0,1,2,3।

    long long int i,j,k,l,m,n,g[100][100],s=0;

    cin>>n;

    for(i=0;i<n;i++)

    {

        for(j=0;j<n;j++)

        {

            cin>>g[i][j];

        }

      cout << tsp(g,s,n) << endl;

      return 0;

   }

ইনপুটঃ

  0 10 15 20

  10 0 35 25

  15 35 0 30

  20 25 30 0

২। ইনপুট নেয়ার পর 0 ছাড়া বাকি ভার্টেক্সগুলো একটা ভেক্টরে পুশ করে রাখব। এরপর প্রত্যেক পারমুটেশনে ভার্টেক্স এর সাইজ পর্যন্ত লুপ চালাব। এখানে যেহেতু মোট শহর 4 তাই ভার্টেক্স এর সাইজ (n-1)=3 এবং প্রথম বার পারমুটেশন এর সময় 4 বার এভাবে দূরত্ব যোগ করবে (0->1 + 1->2 + 2->3 + 3->0) অর্থাৎ (0->1->2->3->0) এই রুট এর দূরত্ব বের করবে। এভাবে প্রত্যেক বার আমরা দূরত্ব বের করব এবং আগের সাথে তুলনা করে মিনিমাম টা নিব। C++ এর next_permuattion() ফাংশন দিয়ে আমরা সব পারমুটেশন জেনারেট করতে পারব। 

এখানে অবশ্যই do-while loop ইউজ করতে হবে কারন next_permutation() vertex ভেক্টর এর প্রথম সিকুয়েন্স স্কিপ করে নেক্সটে যাবে তাই do-while loop দিয়ে আমরা প্রথম সিকুয়েন্স এর রেজাল্ট বের করে নিব।

int tsp(long long int graph[100][100], int s,int N)
{
    // store all vertex apart from source vertex
    vector<int> vertex;
    for (int i=0; i<N; i++)
    {
        if (i!= s)
        {
             vertex.push_back(i);
        }

    }

    // store minimum weight Hamiltonian Cycle.
    int min_path = INT_MAX;
    do
    {

        // store current Path weight(cost)
        int current_pathweight = 0;

        // compute current path weight
        int k = s;
        for (int i = 0; i <vertex.size(); i++)
        {
            current_pathweight += graph[k][vertex[i]];
            k = vertex[i];
        }
        current_pathweight += graph[k][s]; //for looping back to source 4 1

        // update minimum
        min_path = min(min_path, current_pathweight);

    }while (next_permutation(vertex.begin(), vertex.end()));

    return min_path;
}

প্রথম বার পারমুটেশন টা বোঝার জন্য দেখানো হল। তাহলে বাকিগুলো নিজে বের করা যাবে। প্রথম বারে s=0, k=0, current_pathweight=0। তাহলে লুপ এর প্রথম ধাপে,

When i=0,

current_pathweight=0+graph[k][vertex[i]]=0+graph[0][vertex[0]]=0+graph[0][1]=0+10

=10 and k=vertex[0]=1

When i=1

current_pathweight=10+graph[1][2]=10+35=45 and k=vertex[1]=2

When i=2

current_pathweight=45+graph[2][3]=45+30=75 and k=vertex[2]=3

লুপ শেষে আবার প্রথম শহরে যাবে তাই

current_pathweight=75=graph[k][s]=75+graph[3][0]=75+20=95

এটা হল 0-1-2-3-0 এর দূরত্ব।

এভাবে নেক্সট পারমুটেশন এর কোন এক ধাপে আমরা 0-1-3-2-0 রুটে আমরা সব থেকে কম দূরত্ব পাব যা হবে 80 । নিচে ফুল কোড দেয়া হলঃ

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

int tsp(long long int graph[100][100], int s,int N)
{
    // store all vertex apart from source vertex
    vector<int> vertex;
    for (int i=0; i<N; i++)
    {
        if (i!= s)
        {
             vertex.push_back(i);
        }

    }

    // store minimum weight Hamiltonian Cycle.
    int min_path = INT_MAX;
    do
    {

        // store current Path weight(cost)
        int current_pathweight = 0;

        // compute current path weight
        int k = s;
        for (int i = 0; i <vertex.size(); i++)
        {
            current_pathweight += graph[k][vertex[i]];
            k = vertex[i];
        }
        current_pathweight += graph[k][s]; //for looping back to source 4 1

        // update minimum
        min_path = min(min_path, current_pathweight);

    }while (next_permutation(vertex.begin(), vertex.end()));

    return min_path;
}


int main()
{
    long long int i,j,k,l,m,n,g[100][100],s=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>g[i][j];
        }
    }
    cout << tsp(g,s,n) << endl;
    return 0;

}


Related Problems:

Travelling Salesman Problem GeeksForGeeks  

Travelling Salesman Problem Spoj  
 
 

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here