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

اس مثال میں، Nearest Neighbour Algorithm کا استعمال ٹریولنگ سیلز مین کے مسئلے کو حل کرنے کے لیے کیا جاتا ہے۔ یہ ایک ایسا heuristic طریقہ ہے جو ہر قدم پر قریب ترین غیر دیکھے گئے شہر کا انتخاب کرتا ہے، جس کے نتیجے میں ایک ایسا حل نکلتا ہے جو اکثر بہترین کے قریب ہوتا ہے۔