Heuristic ძიების ალგორითმი C++-ში- ახსნა, მაგალითი და კოდი

Heuristic ძიება არის მძლავრი ალგორითმული მიდგომა, რომელიც გამოიყენება კომპლექსურ პრობლემურ სივრცეებში გადაწყვეტილებების მოსაძებნად, ინფორმირებული გადაწყვეტილებების მიღების გზით, ევრისტიკის ან ცერის წესების საფუძველზე. ეს განსაკუთრებით სასარგებლოა, როდესაც ამომწურავი ძებნა არაპრაქტიკულია დიდი საძიებო სივრცის გამო.

Როგორ მუშაობს

1. Heuristic შეფასება: ალგორითმი აფასებს თითოეულ მდგომარეობას პრობლემის სივრცეში ფუნქციის გამოყენებით heuristic. ეს ფუნქცია აფასებს თითოეული სახელმწიფოს „პერსპექტიულობას“ მიზნის მდგომარეობასთან სიახლოვის თვალსაზრისით.
2. ძიების სტრატეგია: ალგორითმი შეფასების საფუძველზე ირჩევს ყველაზე პერსპექტიულ მდგომარეობას heuristic. ის იყენებს ძიების სტრატეგიას, როგორიცაა Best-First Search, A* Search ან Greedy Search.
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 მიდგომა, რომელიც ირჩევს უახლოეს დაუთვალიერებელ ქალაქს ყოველ ნაბიჯზე, რის შედეგადაც გამოსავალი ხშირად ოპტიმალურთან ახლოსაა.