Heuristic C++-এ অ্যালগরিদম অনুসন্ধান করুন- ব্যাখ্যা, উদাহরণ এবং কোড

Heuristic অনুসন্ধান হল একটি শক্তিশালী অ্যালগরিদমিক পদ্ধতি যা হিউরিস্টিকস বা অঙ্গুষ্ঠের নিয়মের উপর ভিত্তি করে জ্ঞাত সিদ্ধান্ত নেওয়ার মাধ্যমে জটিল সমস্যার স্থানগুলিতে সমাধান খুঁজতে ব্যবহৃত হয়। এটি বিশেষভাবে উপযোগী যখন একটি সম্পূর্ণ অনুসন্ধান বৃহৎ অনুসন্ধান স্থানের কারণে অবাস্তব হয়।

কিভাবে এটা কাজ করে

1. Heuristic মূল্যায়ন: heuristic অ্যালগরিদম একটি ফাংশন ব্যবহার করে সমস্যার স্থানের প্রতিটি অবস্থাকে মূল্যায়ন করে । এই ফাংশনটি লক্ষ্য রাষ্ট্রের সাথে ঘনিষ্ঠতার পরিপ্রেক্ষিতে প্রতিটি রাজ্যের "প্রতিশ্রুতিশীলতা" অনুমান করে।
2. অনুসন্ধান কৌশল: অ্যালগরিদম heuristic মূল্যায়নের উপর ভিত্তি করে সবচেয়ে প্রতিশ্রুতিশীল অবস্থা নির্বাচন করে। Best-First এটি অনুসন্ধান, A* অনুসন্ধান বা Greedy অনুসন্ধানের মতো একটি অনুসন্ধান কৌশল ব্যবহার করে ।
3. রাজ্য সম্প্রসারণ: নির্বাচিত রাজ্যটি প্রতিবেশী রাজ্যগুলি তৈরি করে সম্প্রসারিত হয়। এরাই পরবর্তী ধাপের সম্ভাব্য প্রার্থী।
4. পুনরাবৃত্তি: প্রক্রিয়াটি পুনরাবৃত্তভাবে পুনরাবৃত্তি করা হয়, লক্ষ্যের অবস্থা পাওয়া না যাওয়া পর্যন্ত বা একটি সমাপ্তির শর্ত পূরণ না হওয়া পর্যন্ত রাজ্যগুলি নির্বাচন এবং সম্প্রসারণ করা হয়।

উদাহরণ: ট্রাভেলিং সেলসম্যান প্রবলেম(TSP)

ট্রাভেলিং সেলসম্যান সমস্যা বিবেচনা করুন, যেখানে একজন সেলসম্যানকে কয়েকটি শহর পরিদর্শন করতে হবে এবং ভ্রমণের মোট দূরত্ব কমিয়ে শুরুর শহরে ফিরে যেতে হবে। একটি heuristic পন্থা হতে পারে নিকটতম প্রতিবেশী অ্যালগরিদম:

1. এলোমেলো শহর থেকে শুরু করুন।
2. প্রতিটি ধাপে, পরবর্তী গন্তব্য হিসাবে নিকটতম অনাবিষ্কৃত শহর বেছে নিন।
3. সমস্ত শহর পরিদর্শন না হওয়া পর্যন্ত পুনরাবৃত্তি করুন, তারপর শুরু শহরে ফিরে যান।

C++ এ কোডের উদাহরণ

#include <iostream>  
#include <vector>  
#include <cmath>  
#include <algorithm>  
  
struct City {  
    int x, y;  
};  
  
double distance(const City& city1, const City& city2) {  
    return std::sqrt(std::pow(city1.x- city2.x, 2) + std::pow(city1.y- city2.y, 2));  
}  
  
std::vector<int> nearestNeighbor(const std::vector<City>& cities) {  
    int numCities = cities.size();  
    std::vector<int> path(numCities);  
    std::vector<bool> visited(numCities, false);  
  
    path[0] = 0;  
    visited[0] = true;  
  
    for(int i = 1; i < numCities; ++i) {  
        int currentCity = path[i- 1];  
        double minDist = std::numeric_limits<double>::max();  
        int nextCity = -1;  
  
        for(int j = 0; j < numCities; ++j) {  
            if(!visited[j]) {  
                double dist = distance(cities[currentCity], cities[j]);  
                if(dist < minDist) {  
                    minDist = dist;  
                    nextCity = j;  
                }  
            }  
        }  
  
        path[i] = nextCity;  
        visited[nextCity] = true;  
    }  
  
    path.push_back(0); // Return to the starting city  
    return path;  
}  
  
int main() {  
    std::vector<City> cities = {{0, 0}, {1, 3}, {4, 2}, {3, 6}, {7, 1}};  
    std::vector<int> path = nearestNeighbor(cities);  
  
    std::cout << "Traveling Salesman Path: ";  
    for(int city: path) {  
        std::cout << city << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

এই উদাহরণে, ট্রাভেলিং সেলসম্যান সমস্যা সমাধানের জন্য নিকটতম প্রতিবেশী অ্যালগরিদম ব্যবহার করা হয়। এটি এমন একটি heuristic পদ্ধতি যা প্রতিটি ধাপে সবচেয়ে কাছের অনাবিষ্কৃত শহর বেছে নেয়, যার ফলে একটি সমাধান হয় যা প্রায়শই অনুকূলের কাছাকাছি থাকে।