Heuristic C++ में एल्गोरिदम खोजें- स्पष्टीकरण, उदाहरण और कोड

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

यह काम किस प्रकार करता है

1. Heuristic मूल्यांकन: heuristic एल्गोरिदम एक फ़ंक्शन का उपयोग करके समस्या स्थान में प्रत्येक स्थिति का मूल्यांकन करता है । यह फ़ंक्शन लक्ष्य राज्य से निकटता के संदर्भ में प्रत्येक राज्य की "आशाजनकता" का अनुमान लगाता है।
2. खोज रणनीति: heuristic एल्गोरिदम मूल्यांकन के आधार पर सबसे आशाजनक स्थिति का चयन करता है । Best-First यह खोज, ए* खोज, या Greedy खोज जैसी खोज रणनीति का उपयोग करता है ।
3. राज्य विस्तार: चयनित राज्य का विस्तार उसके पड़ोसी राज्यों को उत्पन्न करके किया जाता है। ये अगले चरण के लिए संभावित उम्मीदवार हैं।
4. दोहराएँ: प्रक्रिया को लगातार दोहराया जाता है, राज्यों का चयन और विस्तार किया जाता है जब तक कि लक्ष्य राज्य नहीं मिल जाता है या समाप्ति की स्थिति पूरी नहीं हो जाती है।

उदाहरण: ट्रैवलिंग सेल्समैन समस्या(टीएसपी)

ट्रैवलिंग सेल्समैन समस्या पर विचार करें, जहां एक सेल्समैन को शहरों के एक समूह का दौरा करने और यात्रा की गई कुल दूरी को कम करते हुए शुरुआती शहर में लौटने की आवश्यकता होती है। एक 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 दृष्टिकोण है जो प्रत्येक चरण में निकटतम अनदेखे शहर को चुनता है, जिसके परिणामस्वरूप एक ऐसा समाधान मिलता है जो अक्सर इष्टतम के करीब होता है।