Heuristic خوارزمية البحث في C ++- شرح ومثال ورمز

Heuristic يعد البحث نهجًا خوارزميًا قويًا يستخدم لإيجاد حلول في مساحات المشكلات المعقدة من خلال اتخاذ قرارات مستنيرة بناءً على الاستدلال أو القواعد العامة. إنه مفيد بشكل خاص عندما يكون البحث الشامل غير عملي بسبب مساحة البحث الكبيرة.

كيف تعمل

1. Heuristic التقييم: تقوم الخوارزمية بتقييم كل حالة في مساحة المشكلة باستخدام heuristic دالة. تقدر هذه الوظيفة "الوعد" لكل دولة من حيث قربها من حالة الهدف.
2. استراتيجية البحث: تختار الخوارزمية الحالة الواعدة بناءً على heuristic التقييم. يستخدم استراتيجية بحث مثل Best-First البحث أو البحث * أو 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 نهج يختار أقرب مدينة لم تتم زيارتها في كل خطوة ، مما يؤدي إلى حل قريب من الأمثل في كثير من الأحيان.