close

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

在此示例中，最近邻算法用于解决旅行商问题。 这种 heuristic 方法在每一步中都会选择最近的未访问过的城市，从而产生通常接近最佳的解决方案。