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 ప్రతి దశలో సమీపంలోని సందర్శించని నగరాన్ని ఎంచుకునే విధానం, దీని ఫలితంగా తరచుగా సరైనదానికి దగ్గరగా ఉండే పరిష్కారం లభిస్తుంది.