Heuristic C++ मा एल्गोरिदम खोज्नुहोस्- व्याख्या, उदाहरण र कोड

Heuristic खोज एक शक्तिशाली एल्गोरिथ्मिक दृष्टिकोण हो जुन जटिल समस्या स्थानहरूमा heuristics वा औंठाको नियमहरूमा आधारित सूचित निर्णयहरू गरेर समाधान खोज्न प्रयोग गरिन्छ। यो विशेष गरी उपयोगी छ जब एक विस्तृत खोज ठूलो खोज स्थान को कारण अव्यावहारिक छ।

यो कसरी काम गर्दछ

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 दृष्टिकोण हो जसले प्रत्येक चरणमा सबैभन्दा नजिकको नभेटिएको सहर छान्छ, परिणाम स्वरूप प्रायः इष्टतमको नजिक हुन्छ।