Heuristic อัลกอริทึมการค้นหาใน C++- คำอธิบาย ตัวอย่าง และโค้ด

Heuristic การค้นหาเป็นวิธีอัลกอริทึมที่มีประสิทธิภาพที่ใช้ในการค้นหาวิธีแก้ไขปัญหาในพื้นที่ปัญหาที่ซับซ้อนโดยการตัดสินใจโดยใช้ข้อมูลตามการวิเคราะห์พฤติกรรมหรือกฎง่ายๆ มีประโยชน์อย่างยิ่งเมื่อการค้นหาแบบละเอียดไม่สามารถทำได้เนื่องจากพื้นที่การค้นหาขนาดใหญ่

มันทำงานอย่างไร

1. Heuristic การประเมิน: อัลกอริทึมประเมินแต่ละสถานะในพื้นที่ปัญหาโดยใช้ heuristic ฟังก์ชัน ฟังก์ชันนี้จะประเมิน "แนวโน้ม" ของแต่ละสถานะในแง่ของความใกล้เคียงกับสถานะเป้าหมาย
2. กลยุทธ์การค้นหา: อัลกอริทึมจะเลือกสถานะที่มีแนวโน้มมากที่สุดตาม heuristic การประเมิน ใช้กลยุทธ์การค้นหา เช่น Best-First ค้นหา 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 แนวทางที่เลือกเมืองที่ยังไม่ได้เยี่ยมชมที่ใกล้ที่สุดในแต่ละขั้นตอน ทำให้ได้โซลูชันที่มักจะใกล้เคียงกับค่าที่เหมาะสมที่สุด