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 અભિગમ છે જે દરેક પગલા પર સૌથી નજીકના અવિવેચન શહેરને પસંદ કરે છે, પરિણામે તે ઉકેલમાં પરિણમે છે જે ઘણીવાર શ્રેષ્ઠની નજીક હોય છે.