A* 알고리즘
A* 알고리즘은 그래프에서 시작 노드에서 목표 노드까지의 최단 경로를 효율적으로 찾기 위해 1968년 Peter Hart, Nils Nilsson, Bertram Raphael에 의해 처음 제안되었다. A-star 알고리즘의 핵심은 적절한 휴리스틱을 통해 최적의 경로를 가장 빠르게 찾아내는 것으로, 이를 위해 실제 비용(g(n))과 휴리스틱 비용(h(n)) 두 가지 주요 요소를 활용한다.
f(n) : 출발 노드에서 목표 노드까지 최적 경로를 탐색하기 위한 평가함수로, g(n) + h(n)
g(n) : 실제 비용으로, 시작 노드로부터 현재 노드까지의 비용
h(n) : 휴리스틱 비용으로, 현재 노드에서 목표 노드까지의 예상 비용
또한 다음의 요소들을 추가적으로 갖는다.
열린 목록 (Open List) :
-
아직 방문하지 않았지만, 앞으로 방문할 가능성이 있는 노드들의 집합 (아직 해당 노드를 통해 이웃 노드로의 이동 가능성을 모두 탐색하지 않은 상태)
-
Open list는 각 노드의 F값(F = G + H)에 따라 정렬되고 F값이 가장 낮은 노드가 가장 유망한 후보로 간주되어 다음에 탐색된다.
닫힌 목록 (Closed List) :
-
이미 방문하여 이웃 노드들을 탐색한 노드들의 집합 (해당 노드와 그 노드의 이웃들에 대한 탐색이 완료된 상태)
-
Closed list에 한 번 추가된 노드는 더 이상 탐색 과정에서 고려되지 않는다. 이를 통해 알고리즘의 효율성을 높이고, 같은 노드를 반복해서 탐색하는 것을 방지할 수 있다.
A* 알고리즘 과정
- 초기화 : 시작 노드를 열린 목록에 추가 (시작 노드의 g(n)=0)
- 노드 선택 : 열린 목록에서 f(n) 값이 가장 낮은 노드를 현재 노드로 선택
- 목표 확인 : 현재 노드가 목표 노드인지 확인 (목표 노드라면 경로를 추적하여 반환)
- 이웃 탐색 : 현재 노드의 이웃들을 검사하며, 각각에 대해 g(n), h(n), f(n)을 계산. 이웃이 열린 목록에 이미 있다면, 더 낮은 g(n)값으로 업데이트할지 결정합니다.
- 반복 or 종료: 열린 목록이 비어있으면 경로를 찾을 수 없는 것으로 판단합니다. 그렇지 않다면, 2번 단계로 돌아가 과정을 반복
위 과정을 통해, 알고리즘은 최적의 경로를 점진적으로 좁혀나가며 최종적으로 목표 노드까지의 최단 경로를 찾아낼 수 있다.
특징
- 주어진 휴리스틱 함수가 일관성 또는 접근성 조건을 만족한다면, 목표에 도달하는 최적의 경로를 보장한다
- 탐색 공간 내 경로가 존재한다면 A* 알고리즘은 반드시 경로를 찾을 수 있다
- A* 알고리즘 성능은 휴리스틱 함수의 선택에 크게 의존한다 (선정한 휴리스틱 함수가 현재 노드에서 목표 노드까지의 실제 비용을 정확하게 예측할수록 최적 경로를 위해 필요한 최소한의 노드만을 검사할 수 있어 적절한 휴리스틱 함수 선택이 중요)
- A* 알고리즘은 탐색 과정에서 더 낮은 F값을 가진 노드를 발견하면 해당 노드로 탐색경로를 변경하여 동적 탐색이 가능하다
구현 코드
import heapq
class Node:
def __init__(self, state, parent=None, g=0, h=0):
self.state = state
self.parent = parent
self.g = g # G value
self.h = h # H value
def f(self):
return self.g + self.h
def __lt__(self, other):
return self.f() < other.f()
def astar(start_state, goal_state, heuristic, neighbors):
start_node = Node(start_state, g=0, h=heuristic(start_state, goal_state))
open_list = []
closed_set = set()
heapq.heappush(open_list, start_node)
while open_list:
current_node = heapq.heappop(open_list)
if current_node.state == goal_state:
path = []
while current_node:
path.append(current_node.state)
current_node = current_node.parent
return path[::-1]
closed_set.add(current_node.state)
for neighbor_state in neighbors(current_node.state):
if neighbor_state in closed_set:
continue
g = current_node.g + 1
h = heuristic(neighbor_state, goal_state)
neighbor_node = Node(neighbor_state, parent=current_node, g=g, h=h)
if neighbor_node not in open_list:
heapq.heappush(open_list, neighbor_node)
elif g < neighbor_node.g:
neighbor_node.g = g
neighbor_node.parent = current_node
return None
def manhattan_distance(state, goal_state):
x1, y1 = state
x2, y2 = goal_state
return abs(x1 - x2) + abs(y1 - y2)
def get_neighbors(state):
x, y = state
neighbors = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
return [(nx, ny) for nx, ny in neighbors if 0 <= nx < 5 and 0 <= ny < 5]
if __name__=="__main__":
start = (0, 0)
goal = (4, 4)
path = astar(start, goal, manhattan_distance, get_neighbors)
print(path)A* 알고리즘 과정에 대해 구현한 코드로, (5,5) 격자 내에서 (0,0)에서 출발해 (4,4)으로 도달하는 것을 목적으로 하며 각 점에서는 상하좌우로만 이동가능하다. 각 이동의 비용은 1로 고정하였고 휴리스틱 함수로는 맨해튼 거리를 이용하였다.
A* vs 다익스트라 알고리즘
A* 알고리즘과 다익스트라 알고리즘은 모두 그래프 탐색 알고리즘이지만 목적과 동작 방식에 있어서 차이가 있다.
| 다익스트라 알고리즘 | A* 알고리즘 | |
|---|---|---|
| 목적 | 단일 출발점에서 여러 노드 간 최단 경로를 찾기 위해 각 노드까지의 경로 비용을 계산 | 특정 목표 노드에 도달하는 최단 경로를 찾기 위해 목표 노드까지의 예상 비용을 계산 |
| 경로 비용 | 출발 노드로부터의 가중치 | 출발 노드로부터 실제 비용과 목표 노드까지의 휴리스틱 비용의 합 |
| 메모리 요구량 | 모든 노드의 비용을 기록하고 갱신하여 연산량 많음 | 휴리스틱 함수와 open/closed list를 통해 더 효율적인 탐색 수행 |
| 탐색 속도 | 별도 휴리스틱 함수 없이 가능한 모든 경로를 탐색해 탐색 속도 느림 | 휴리스틱 함수를 통해 목표에 더 가까운 노드를 우선적으로 탐색해 더 빠른 속도로 최적 경로 탐색 가능 |
