[Python] A*알고리즘 - 최단 경로 탐색

 

---

어린이를 위한 안전 길 찾기 어플을 만들었는 데, 해당 어플에서 사용한 길 찾기 알고리즘에 대해 적어보려고 한다.

사용한 알고리즘은 A* 알고리즘이며, 본 글에서는 A* 알고리즘의 기본 개념과 간단한 예시를 설명하고자 한다.

 

✏️ A* 알고리즘(A star algorithm)

A*알고리즘은 다익스트라 알고리즘의 확장으로, 휴리스틱을 결합한 최단거리 탐색 알고리즘이다.

 

✏️ 휴리스틱(heuristic)

휴리스틱이란 예상값으로, 복잡하고 계산 비용이 높은 문제에서 사용할 수 있다. A* 알고리즘에서는 휴리스틱을 사용하여 각 노드까지의 예상 비용을 계산한다.

예를 들면, 노드 간 직선거리를 휴리스틱으로 사용할 수 있다. 출발 노드에서 다음 노드를 어떤 노드로 선택할 지 비교할 때, 출발 노드와 다음 노드의 실제 거리 뿐만 아니라 목적지까지 직선거리도 함께 고려해서 비교한다.

 f(n) = g(n) + h(n) 

f(n) : 총 비용

g(n) : 출발  노드에서 현재노드까지의 실제 비용

h(n) : 휴리스틱, 목적지까지의 예상비용

 

✏️ open list & closed list

open list : 아직 방문하지 않은 노드들의 집합이다. 초기에는 시작 노드만 있다.

closed list : 이미 방문한 노드들의 집합이다. closed list에 추가된 노드는 더 이상 고려하지 않는다. 중복 방문을 방지할 수 있다.

 

✏️ 구현

(전체 코드는 아래에)

def a_star_algorithm(self, start_node, stop_node):

 

1. 초기화

# 시작 노드를 초기값으로 가지며, 아직 방문하지 않은 노드의 집합
open_list = set([start_node])

# 초기에는 비어 있으며, 이미 방문한 노드들의 집합
closed_list = set([])

# 각 노드까지의 현재까지의 최소 비용을 저장하는 딕셔너리
g = {}
g[start_node] = 0

# 각 노드의 부모 노드를 저장하는 딕셔너리
parents = {}
parents[start_node] = start_node

 

 

2. 탐색 루프

# Open List가 비어있을 때까지 반복
while len(open_list) > 0:

 

 

3. 현재 노드 선택

# 현재 노드를 나타내는 변수를 초기화
n = None

# Open List에서 가장 낮은 비용의 노드를 선택
for v in open_list:
    if n == None or g[v] + self.h(v) < g[n] + self.h(n):
    n = v

 

4. 경로의 존재 여부 확인

 

# 현재 노드가 없으면 경로가 존재하지 않는다고 출력하고 None을 반환
if n == None:
    print('Path does not exist!')
    return None

 

5. 목적지 도달 여부 확인

# 현재 노드가 목적지 노드와 일치하면, 최적 경로를 재구성하고 결과를 출력하고 반환
if n == stop_node:
    reconst_path = []

    while parents[n] != n:
        reconst_path.append(n)
        n = parents[n]

    reconst_path.append(start_node)
    reconst_path.reverse()

    print('Path found: {}'.format(reconst_path))
    return reconst_path

 

6. 이웃 노드 탐색 및 업데이트

# 현재 노드의 이웃 노드들을 탐색
for (m, weight) in self.get_neighbors(n):
	
    # 이웃 노드가 Open List와 Closed List에 없으면 추가하고 정보를 업데이트
    if m not in open_list and m not in closed_list:
        open_list.add(m)
        parents[m] = n
        g[m] = g[n] + weight

	# 이미 방문한 노드이거나 Open List에 포함된 경우, 비용을 비교하여 업데이트
    else:
        if g[m] > g[n] + weight:
            g[m] = g[n] + weight
            parents[m] = n
            if m in closed_list:
                closed_list.remove(m)
                open_list.add(m)

 

7. 현재 노드를 Closed List로 이동

# 현재 노드를 Open List에서 제거
open_list.remove(n)
# 현재 노드를 Closed List에 추가
closed_list.add(n)

 

8. 최적 경로가 없는 경우 처리

# 최적 경로를 찾지 못한 경우, 'Path does not exist!'를 출력하고 None을 반환
print('Path does not exist!')
return None

 

✏️ 전체 코드

class Graph:
    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list

    def get_neighbors(self, v):
        return self.adjacency_list[v]

    def h(self, n):
        H = {
            'A': 1,
            'B': 1,
            'C': 1,
            'D': 1
        }
        return H[n]

    def a_star_algorithm(self, start_node, stop_node):
        open_list = set([start_node])
        closed_list = set([])
        g = {}
        g[start_node] = 0
        parents = {}
        parents[start_node] = start_node

        while len(open_list) > 0:
            n = None

            for v in open_list:
                if n == None or g[v] + self.h(v) < g[n] + self.h(n):
                    n = v;

            if n == None:
                print('Path does not exist!')
                return None

            if n == stop_node:
                reconst_path = []

                while parents[n] != n:
                    reconst_path.append(n)
                    n = parents[n]

                reconst_path.append(start_node)

                reconst_path.reverse()

                print('Path found: {}'.format(reconst_path))
                return reconst_path

            for (m, weight) in self.get_neighbors(n):
                if m not in open_list and m not in closed_list:
                    open_list.add(m)
                    parents[m] = n
                    g[m] = g[n] + weight

                else:
                    if g[m] > g[n] + weight:
                        g[m] = g[n] + weight
                        parents[m] = n

                        if m in closed_list:
                            closed_list.remove(m)
                            open_list.add(m)

            open_list.remove(n)
            closed_list.add(n)

        print('Path does not exist!')
        return None


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

위의 코드는 각 노드의 휴리스틱 값을 1로 적용한 간단한 예시이다.