C++ প্রোগ্রাম: নিয়ারেস্ট নেইবার অ্যালগরিদম ব্যবহার করে ট্রেভেলিং সেলসম্যান প্রობলেম সমাধান

এখানে নিয়ারেস্ট নেইবার অ্যালগরিদম ব্যবহার করে ট্রেভেলিং সেলসম্যান প্রোবলেম সমাধানের একটি C++ প্রোগ্রাম দেওয়া হলো।

প্রয়োজনীয় ফাংশন এবং সিউডোকোড

অ্যালগরিদম

শুরু
    c = 0, cost = 1000 ইনিশিয়ালাইজ করো।
    g[][] ইনিশিয়ালাইজ করো।
    swap() ফাংশন - দুটি ভ্যালু x এবং y স왪 করতে।
    cal_sum() ফাংশন - কস্ট ক্যালকুলেট করতে যা array a[] এবং আকার নেয় ইনপুট হিসেবে।
    sum = 0 ইনিশিয়ালাইজ করো।
    for i = 0 to n
        s += g[a[i % 3]][a[(i + 1) % 3]] ক্যালকুলেট করো।
    if (cost > s)
        cost = s
    permute() ফাংশন - পারমুটেশন করতে:
        যদি অ্যারেতে এক এলিমেন্ট থাকে
            cal_sum() কল করো।
        অন্যথায়
            for j = i to n
                swap(a+i) with (a+j)
                cal_sum(a+1, n)
                swap(a+i) with (a+j)
শেষ

উদাহরণ কোড

#include <iostream> 
using namespace std; 
int c = 0, cost = 1000; 
int g[3][3] = {{1, 2, 3}, {4, 5, 8}, {6, 7, 10}}; 
void swap(int *x, int *y) { 
    int t; 
    t = *x; 
    *x = *y; 
    *y = t; 
} 
void cal_sum(int *a, int n) { 
    int i, s = 0; 
    for (i = 0; i <= n; i++) { 
        s += g[a[i % 3]][a[(i + 1) % 3]]; 
    } 
    if (cost > s) { 
        cost = s; 
    } 
} 
void permute(int *a, int i, int n) { 
    int j, k; 
    if (i == n) { 
        cal_sum(a, n); 
    } else { 
        for (j = i; j <= n; j++) { 
            swap((a + i), (a + j)); 
            cal_sum(a + 1, n); 
            swap((a + i), (a + j)); 
        } 
    } 
} 
int main() { 
    int i, j; 
    int a[] = {1, 2, 3}; 
    permute(a, 0, 2); 
    cout << "minimum cost: " << cost << endl; 
}

আউটপুট

minimum cost: 3