Heuristic C++'da Arama Algoritması- Açıklama, Örnek ve Kod

Heuristic Arama, buluşsal yöntemlere veya pratik kurallara dayalı bilinçli kararlar vererek karmaşık problem alanlarında çözümler bulmak için kullanılan güçlü bir algoritmik yaklaşımdır. Kapsamlı bir arama, geniş arama alanı nedeniyle pratik olmadığında özellikle yararlıdır.

Nasıl çalışır

1. Heuristic Değerlendirme: Algoritma problem uzayındaki her durumu bir heuristic fonksiyon kullanarak değerlendirir. Bu işlev, hedef duruma yakınlığı açısından her bir durumun "umut vericiliğini" tahmin eder.
2. Arama Stratejisi: Algoritma, değerlendirmeye dayalı olarak en umut verici durumu seçer heuristic. Best-First Arama, A* Arama veya Greedy Arama gibi bir arama stratejisi kullanır .
3. Durum Genişletme: Seçilen durum, komşu durumları oluşturularak genişletilir. Bunlar bir sonraki adım için potansiyel adaylardır.
4. Tekrarla: Süreç, hedef durumu bulunana veya bir sonlandırma koşulu sağlanana kadar durumları seçerek ve genişleterek yinelemeli olarak tekrarlanır.

Örnek: Gezgin Satıcı Problemi(TSP)

Bir satıcının bir dizi şehri ziyaret etmesi ve kat edilen toplam mesafeyi en aza indirirken başlangıç ​​​​şehrine dönmesi gerektiği Gezgin Satıcı Problemini düşünün. Bir heuristic yaklaşım, En Yakın Komşu Algoritması olabilir:

1. Rastgele bir şehirde başlayın.
2. Her adımda, bir sonraki varış noktası olarak en yakın ziyaret edilmemiş şehri seçin.
3. Tüm şehirler ziyaret edilene kadar tekrarlayın, ardından başlangıç ​​şehrine dönün.

C++'da Kod Örneği

#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;  
}  

Bu örnekte, Gezgin Satıcı Problemini çözmek için En Yakın Komşu Algoritması kullanılmıştır. Bu, heuristic her adımda ziyaret edilmeyen en yakın şehri seçen ve genellikle optimale yakın bir çözümle sonuçlanan bir yaklaşımdır.