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 、各ステップで最も近い未訪問の都市を選択するアプローチであり、多くの場合、最適に近いソリューションが得られます。