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 दृष्टीकोन आहे जो प्रत्येक पायरीवर सर्वात जवळचे न पाहिलेले शहर निवडतो, परिणामी बहुतेकदा इष्टतम जवळ असलेले समाधान मिळते.