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 ஒவ்வொரு அடியிலும் அருகிலுள்ள பார்வையிடாத நகரத்தைத் தேர்ந்தெடுக்கும் அணுகுமுறையாகும், இதன் விளைவாக பெரும்பாலும் உகந்ததாக இருக்கும் தீர்வு கிடைக்கும்.