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