[기술면접/알고리즘] A*

A* 에 대해 설명하세요

Keyword

특정 노드에서 특정 노드, G(n), H(n), F(n), 휴리스틱 함수, 유클리디안 거리 함수, 맨허튼 거리 함수, open list, closed list

---

Script

A* 알고리즘은 가중치 그래프에서 특정 노드와 특정 노드 간의 최단 경로를 파악할 수 있는 그리디 알고리즘입니다.

먼저, 시작 노드부터 현재 노드까지의 비용을 G(n), 현재 노드에서 목표 노드까지의 예상 비용을 H(n)이라고 할 때, 이 두 값을 더한 F(n)을 최소로 만드는 노드를 다음 탐색 노드로 선정합니다.

그리고 탐색 과정에서 각 노드들은 검색 가능성이 있는 노드 집합인 Open List와 이미 검색이 끝난 노드 집합인 closed list에서 관리됩니다.

이때 H(n)을 휴리스틱 함수라고 하는데, 이 함수를 어떻게 설계하느냐에 따라 알고리즘의 성능이 결정됩니다. 가장 단순하고 대표적인 휴리스틱 함수로 맨허튼 거리 함수와 유클리디안 거리 함수가 있습니다.

그런데 H(n)이 0이거나 모두 같은 경우는 결국 F(n) = G(n)이 되므로, 다익스트라와 동일하게 작동하게 됩니다.

---

Additional

코드 (python)

from collections import deque
 
class Graph:
    def __init__(self, adjac_lis):
        self.adjac_lis = adjac_lis
 
    def get_neighbors(self, v):
        return self.adjac_lis[v]
 
    # This is heuristic function which is having equal values for all nodes
    def h(self, n):
        H = {
            'A': 1,
            'B': 1,
            'C': 1,
            'D': 1
        }
 
        return H[n]
 
    def a_star_algorithm(self, start, stop):
        # In this open_lst is a lisy of nodes which have been visited, but who's 
        # neighbours haven't all been always inspected, It starts off with the start 
  #node
        # And closed_lst is a list of nodes which have been visited
        # and who's neighbors have been always inspected
        open_lst = set([start])
        closed_lst = set([])
 
        # poo has present distances from start to all other nodes
        # the default value is +infinity
        poo = {}
        poo[start] = 0
 
        # par contains an adjac mapping of all nodes
        par = {}
        par[start] = start
 
        while len(open_lst) > 0:
            n = None
 
            # it will find a node with the lowest value of f() -
            for v in open_lst:
                if n == None or poo[v] + self.h(v) < poo[n] + self.h(n):
                    n = v;
 
            if n == None:
                print('Path does not exist!')
                return None
 
            # if the current node is the stop
            # then we start again from start
            if n == stop:
                reconst_path = []
 
                while par[n] != n:
                    reconst_path.append(n)
                    n = par[n]
 
                reconst_path.append(start)
 
                reconst_path.reverse()
 
                print('Path found: {}'.format(reconst_path))
                return reconst_path
 
            # for all the neighbors of the current node do
            for (m, weight) in self.get_neighbors(n):
              # if the current node is not presentin both open_lst and closed_lst
                # add it to open_lst and note n as it's par
                if m not in open_lst and m not in closed_lst:
                    open_lst.add(m)
                    par[m] = n
                    poo[m] = poo[n] + weight
 
                # otherwise, check if it's quicker to first visit n, then m
                # and if it is, update par data and poo data
                # and if the node was in the closed_lst, move it to open_lst
                else:
                    if poo[m] > poo[n] + weight:
                        poo[m] = poo[n] + weight
                        par[m] = n
 
                        if m in closed_lst:
                            closed_lst.remove(m)
                            open_lst.add(m)
 
            # remove n from the open_lst, and add it to closed_lst
            # because all of his neighbors were inspected
            open_lst.remove(n)
            closed_lst.add(n)
 
        print('Path does not exist!')
        return None

input

adjac_lis = {
    'A': [('B', 1), ('C', 3), ('D', 7)],
    'B': [('D', 5)],
    'C': [('D', 12)]
}
graph1 = Graph(adjac_lis)
graph1.a_star_algorithm('A', 'D')

output

Path found: ['A', 'B', 'D']
['A', 'B', 'D']

유클리디안 거리 함수

멘허튼 거리 함수

여기서 초록색을 제외한 '노랑', '파랑', '빨강' 경로는 모두 길이가 같다.

그래서 결국 맨허튼 거리는 아래 수식으로 구한다.