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 각 단계에서 방문하지 않은 가장 가까운 도시를 선택하여 종종 최적에 가까운 솔루션을 제공하는 접근 방식 입니다 .