[C++][알고리즘] A*알고리즘

1.  개요

미로 탐색 등 최단거리 탐색을 할때 bfs, dfs만 사용해보았다. 하지만 이 둘은 완전 탐색으로 시간적 비효율이 발생했다. 

그래서 다른 알고리즘을 찾아보던중 실제 게임에 많이 쓰이는 에이스타(A*)알고리즘에 대해 알게되었다.

 

2.  A*알고리즘 vs BFS

A*알고리즘은 bfs와 형태가 유사하다. 큐에 구조체를 넣고 큐의 모든요소를 탐색할때까지 반복한다.

하지만, 일반 큐가 아닌 우선순위 큐(priority queue)를 사용한다는점이 다르다.

이게 키포인트이고, 이로인해 시간이 대폭 감소하게 된다.

아래 예시는 탈출 조건만 간단하게 작성해보았다.

//BFS
#include <queue>

void bfs(...)
{
	queue<Node> q;
    q.push(start);
    
    while(!q.empty())
    {
    	Node cur = q.front();
        q.pop();
    	if (//조건 만족하면)
        {
        	answer = min(answer, cur.value);
        	continue;
        }
        
        for(....)
    }
}

//A*
#include <queue>

bool comp(Node a, Node b)
{	return a.getScore() > b.getScore(); }

void bfs(...)
{
	//우선순위 큐, 비교 함수 설정시 해당 비교함수를 삽입 sort와 비슷
	priority_queue<Node, vector<Node>, (bool)(*)(Node, Node)> pq(comp);
	q.push(start);
    
    while(!q.empty())
    {
    	Node cur = q.front();
        q.pop();
    	if (//조건 만족하면 바로 리턴, 우선순위가 적용되었으니까)
        {
        	answer = cur.value;
        	return;
        }
        
        for(....)
    }
}

3. 우선순위 큐

우선순위 큐는 말그대로 우선순위대로 큐에 넣는다고 생각하면 된다. 

쉽게 말하면 큐에 push를 할때마다 오름차순 또는 내림차순으로 정렬된다고 생각하면 된다.

(실제 작동 원리는 다음에 알아보자..)

https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90

우선순위 큐 - 위키백과, 우리 모두의 백과사전

 

4. A*알고리즘 구조

A*알고리즘은 우선순위가 적용되었으니 바로 탈출한다고 하였다. 그럼 여기서 우선순위를 어떻게 설정할까?

일단 우선순위를 설정하는 방법은 위에서 보았듯이 priority_queue를 선언할때 세번째 인자로 넣어주는 함수로 결정하게 된다.

// 우선순위 설정
bool comp(Node a, Node b)
{	return a.getScore() > b.getScore(); }

priority_queue<Node, vector<Node>, (bool)(*)(Node, Node)> pq(comp);

근데 이때 중요한 개념이 들어가게 된다.

 

출처 : 위키백과

여기서 간단히 f = g + h라고 하겠다.

g는 출발지점부터 현위치까지 거리

h는 현위치부터 목표지점까지의 거리

이렇게 생각하면 된다.

 

그리고 Node에는 g와 h값이 들어가게되고

우선순위는 f값 즉 g + h값이 작은 값이 우선순위로 설정하게 되는것이다.

 

5. 적용

이렇게 해서 bfs같은 큐 구조이지만 f값이 작은 값들 부터 우선순위로 탐색했기 때문에 목표지점에

도달하기만 한다면 끝나게 되는것이다.

아래 코드는 프로그래머스 미로탈출을 C++로 풀어본 코드이다.

#include <iostream> //test print
#include <string> //string
#include <vector> //vector
#include <queue> //priority queue
#include <unordered_set> //unordered_set

using namespace std;

struct Node
{
    int x, y; //pos
    int g, h; //g(출발지로부터 거리), h(도착지까지 추정거리)
    Node *parent, *child;
    
    Node(int x, int y) : x(x), y(y), g(0), h(0), parent(nullptr), child(nullptr) {}
    
    bool operator==(const Node& other) const
    {
        return (x == other.x && y == other.y);
    }
    
    string getPos()
    {
        return string("(" + to_string(x) + "," + to_string(y) + ")");
    }
    
    int getScore()
    {
        return g + h;
    }
};

//맨해튼 거리 계산 (대각선 X)
int heuristic(const Node *a, const Node *b)
{
    return abs(a->x - b->x) + abs(a->y - b->y);
}

size_t width, height;

bool comp(Node *a, Node *b)
{
    return a->getScore() > b->getScore();
}

void free_mem(vector<Node *> &vmem)
{
    for (size_t i = 0; i < vmem.size(); i++)
        delete vmem[i];
}

bool is_visited(unordered_set<string> &visited, const int x, const int y)
{
    string id = to_string(x) + "," + to_string(y);
    if (visited.count(id))
        return true;
    visited.insert(id);
    return false;
}

int astar(const Node *o_start, const Node *goal, const vector<string> maps)
{
    unordered_set<string> visited;
    priority_queue<Node*, vector<Node*>, bool(*)(Node *, Node *)> pq(comp);
    
    Node *start = new Node(o_start->x, o_start->y);
    vector<Node *> vmem;
    
    start->h = heuristic(start, goal);
    pq.push(start);
    
    vmem.push_back(start);
    
    while (!pq.empty())
    {
        Node *cur = pq.top();
        pq.pop();
        
        if (*cur == *goal)
        {
            int answer = cur->getScore();            
            free_mem(vmem);
            return answer;
        }
        
        if (is_visited(visited, cur->x, cur->y)) // check double
            continue;
        
        //move up, down, left, right
        static int dx[4] = {1, -1, 0, 0};
        static int dy[4] = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++)
        {
            int nx = cur->x + dx[i];
            int ny = cur->y + dy[i];
            
            //out of maps
            if (nx < 0 || ny < 0 || nx >= width || ny >= height || maps[ny][nx] == 'X')
                continue;
            
            Node *neighbor = new Node(nx, ny);
            neighbor->g = cur->g + 1; //distance start to cur location
            neighbor->h = heuristic(neighbor, goal); //distance cur location to goal
            neighbor->parent = cur;
            pq.push(neighbor);
            vmem.push_back(neighbor);
        }
    }
    free_mem(vmem);
    return -1;
}

int solution(vector<string> maps) {
    
    width = maps[0].size(), height = maps.size();
    Node *start, *lever, *exit;
    
    /*시작지점, 레버, 출구 위치 추출*/
    for (size_t y = 0; y < height; y++){
        for (size_t x = 0; x < width; x++){
            if (maps[y][x] == 'S')
            {
                start = new Node(x, y);
            }
            else if (maps[y][x] == 'L')
            {
                lever = new Node(x, y);
            }
            else if (maps[y][x] == 'E')
            {
                exit = new Node(x, y);
            }
            else
                continue;
        }
    }
    
    int time_start_to_lever = astar(start, lever, maps);
    int time_lever_to_exit = astar(lever, exit, maps);
    
    /*memory free*/
    delete start;
    delete lever;
    delete exit;
    
    if (time_start_to_lever == -1 || time_lever_to_exit == -1)
        return -1;
    return time_start_to_lever + time_lever_to_exit;
}

 

 

 

#참고

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

https://ko.wikipedia.org/wiki/A*_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

A* 알고리즘 - 위키백과, 우리 모두의 백과사전