안녕하세요!
A* 알고리즘은 경로 탐색 문제에서 사용되는 효율적인 길찾기 알고리즘 중 하나입니다.
A* 알고리즘은 최적의 경로를 찾는 데 사용되며, 주로 게임 개발, 로봇 공학, 지리 정보 시스템 (GIS), 미로 생성 및 다양한 경로 탐색 문제에서 활용됩니다. 아래에서 A* 알고리즘의 핵심 아이디어와 작동 방식을 설명해드리겠습니다.
A* 알고리즘의 핵심 아이디어
A* 알고리즘은 최단 경로를 찾는 데 사용되며, 경로를 찾는 과정에서 현재 위치에서 목표 위치까지의 예상 비용을 고려합니다.
이를 위해 다음 두 가지 값을 추적합니다.
1. g(n) : 시작 노드에서 현재 노드 n 까지의 실제 이동 비용. 즉, 시작점에서 n 까지 얼마나 많은 비용이 들었는지를 나타냅니다.
2. h(n) : 현재 노드 n 에서 목표 노드까지의 예상 비용. 이 값은 휴리스틱 함수로 계산되며, 현재 위치에서 목표 위치까지 얼마나 먼지에 대한 추정입니다.
A* 알고리즘은 이 두 가지 값의 합인 f(n) = g(n) + h(n) 을 사용하여 각 노드의 우선순위를 결정하고,
우선순위 큐 (일반적으로 힙)를 사용하여 탐색을 진행합니다.
A* 알고리즘의 핵심 아이디어를 더 이해하기 쉽게 예시
상상해보세요, 당신이 현재 어떤 도시에 있다고 가정하고 다른 도시로 이동하려고 합니다.
이때 A* 알고리즘을 사용하여 가장 빠른 경로를 찾는 과정을 설명하겠습니다.
1. g(n) 값 (실제 이동 비용)
- g(n)은 현재 위치에서 출발 지점까지 실제로 얼마나 이동하는 데 드는 비용을 나타냅니다.
2. h(n) 값 (예상 비용)
- h(n)은 현재 위치에서 목표 도시까지 얼마나 먼지에 대한 추정을 나타냅니다. 이 값은 휴리스틱 함수를 사용하여 계산됩니다. 예를 들어, 직선거리가 항상 실제 거리보다 작기 때문에, 현재 위치에서 목표 도시까지의 직선거리를 h(n)으로 사용하는 것이 흔한 예입니다. 이 값은 목표까지 얼마나 빨리 도달할 수 있을지에 대한 예상입니다.
3. f(n) 값 (종합 비용)
- f(n) 값은 g(n) 값과 h(n) 값을 합한 것입니다. 즉, 현재 위치에서 출발 지점까지의 실제 비용과 현재 위치에서 목표 지점까지의 예상 비용을 합한 것입니다. A* 알고리즘은 각 노드의 f(n) 값을 사용하여 노드의 우선순위를 결정하고, 우선순위 큐를 사용하여 탐색을 진행합니다. 이때 f(n) 값이 작은 노드를 먼저 탐색하므로, 최적의 경로에 더 빨리 도달할 가능성이 높아집니다.
간단한 예를 들어보겠습니다. 당신은 지금 뉴욕에 있고, 목표는 샌프란시스코로 가는 것입니다.
- g(n) 값은 현재 뉴욕에서 출발 지점까지 운전하는 데 걸리는 실제 시간과 비용입니다.
- h(n) 값은 현재 뉴욕에서 샌프란시스코까지 직선거리로 얼마나 멀리 떨어져 있는지에 대한 예상입니다.
- f(n) 값은 현재 뉴욕에서 출발 지점까지의 시간과 비용, 그리고 현재 뉴욕에서 샌프란시스코까지의 예상 시간과 비용을 합한 것입니다.
A* 알고리즘의 작동 방식
1. 초기에 시작 노드를 오픈 리스트(우선순위 큐)에 넣고 g와 h 값을 초기화합니다.
2. 오픈 리스트가 비어있지 않은 동안 다음 단계를 반복합니다
- 오픈 리스트에서 f 값이 가장 작은 노드를 선택합니다. 이 노드를 현재 노드로 지정합니다.
- 현재 노드가 목표 노드인지 확인하고, 목표 노드에 도달했다면 경로를 찾은 것이므로 종료합니다.
- 현재 노드의 이웃 노드들을 검사하고 각 이웃에 대한 g 값과 h 값을 계산합니다.
- 이웃 노드를 오픈 리스트에 추가하고, g 값과 h 값을 업데이트합니다.
3. 오픈 리스트가 비어서 목표 노드에 도달하지 못하거나 경로가 없을 경우 실패로 처리합니다.
A* 알고리즘은 휴리스틱 함수 h 에 따라서 최적의 경로를 찾을 가능성이 높습니다.
그러나 휴리스틱 함수의 선택과 문제에 따라 성능이 달라질 수 있으므로, 적절한 휴리스틱 함수를 선택하는 것이 중요합니다.
A* 알고리즘은 최악의 경우 지수 시간복잡도를 가질 수 있으므로, 효율적인 자료 구조 및 최적화 기법을 사용하여 성능을 향상시키는 것이 중요합니다.
소스 코드
import heapq
class Node:
def __init__(self, x, y, parent=None):
self.x = x
self.y = y
self.parent = parent
self.g = 0 # 시작 노드부터 현재 노드까지의 실제 이동 비용 (g(n))
self.h = 0 # 현재 노드부터 목표 노드까지의 휴리스틱 추정 비용 (h(n))
def __lt__(self, other):
return (self.g + self.h) < (other.g + other.h)
def astar(grid, start, end):
open_list = [] # 열린 리스트: 아직 검사하지 않은 노드들을 저장하는 우선순위 큐
closed_set = set() # 닫힌 세트: 이미 검사한 노드들을 저장하는 집합
start_node = Node(*start) # 시작 노드 초기화
end_node = Node(*end) # 목표 노드 초기화
heapq.heappush(open_list, start_node) # 시작 노드를 열린 리스트에 추가
while open_list:
current_node = heapq.heappop(open_list) # 열린 리스트에서 f(n) 값이 가장 작은 노드를 선택
if current_node.x == end_node.x and current_node.y == end_node.y:
# 목표 노드에 도달하면 경로 추적
path = []
while current_node:
path.append((current_node.x, current_node.y))
current_node = current_node.parent
return path[::-1] # 역순으로 반환하여 시작부터 목표까지의 경로 반환
closed_set.add((current_node.x, current_node.y)) # 현재 노드를 닫힌 세트에 추가
for x, y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
new_x, new_y = current_node.x + x, current_node.y + y # 이웃 노드 좌표 계산
if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]) and grid[new_x][new_y] != 1 and (new_x, new_y) not in closed_set:
# 유효한 이웃 노드인지 확인하고 이미 검사한 노드가 아니라면 진행
neighbor = Node(new_x, new_y, current_node) # 이웃 노드 초기화
neighbor.g = current_node.g + 1 # 이웃 노드의 g(n) 값 업데이트
neighbor.h = abs(new_x - end_node.x) + abs(new_y - end_node.y) # 이웃 노드의 h(n) 값 계산 (맨해튼 거리 휴리스틱)
if neighbor not in open_list:
heapq.heappush(open_list, neighbor) # 이웃 노드를 열린 리스트에 추가
return None # 경로를 찾을 수 없는 경우 None 반환
# 예제 그리드
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 1],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0) # 시작점 좌표
end = (4, 4) # 목표점 좌표
path = astar(grid, start, end)
if path:
print("최단 경로:", path)
else:
print("경로를 찾을 수 없습니다.")
출력 결과
최단 경로: [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]
세부 코드 설명
import heapq
class Node:
def __init__(self, x, y, parent=None):
self.x = x
self.y = y
self.parent = parent
self.g = 0 # 시작 노드부터 현재 노드까지의 실제 이동 비용 (g(n))
self.h = 0 # 현재 노드부터 목표 노드까지의 휴리스틱 추정 비용 (h(n))
def __lt__(self, other):
return (self.g + self.h) < (other.g + other.h)
Node 클래스 : 노드 객체를 정의합니다.
각 노드는 자표 (x, y)를 가지며, 부모 노드 정보와 이동 비용 g, 휴리스틱 추정 비용 h를 저장합니다.
__lt__ 메서드를 정의하여 노드를 우선순위 큐에서 비교할 때 f(n) = g(n) + h(n) 값을 기준으로 비교합니다.
def astar(grid, start, end):
open_list = [] # 열린 리스트: 아직 검사하지 않은 노드들을 저장하는 우선순위 큐
closed_set = set() # 닫힌 세트: 이미 검사한 노드들을 저장하는 집합
start_node = Node(*start) # 시작 노드 초기화
end_node = Node(*end) # 목표 노드 초기화
heapq.heappush(open_list, start_node) # 시작 노드를 열린 리스트에 추가
aster 함수 : A* 알고리즘을 구현한 함수입니다.
열린 리스트 open_list 와 닫힌 세트 close_set를 초기화하고, 시작노드와 목표 노드를 설정합니다.
열린 리스트: 아직 검사하지 않은 노드들을 저장하는 우선순위 큐
닫힌 세트: 이미 검사한 노드들을 저장하는 집합
while open_list:
current_node = heapq.heappop(open_list) # 열린 리스트에서 f(n) 값이 가장 작은 노드를 선택
if current_node.x == end_node.x and current_node.y == end_node.y:
# 목표 노드에 도달하면 경로 추적
path = []
while current_node:
path.append((current_node.x, current_node.y))
current_node = current_node.parent
return path[::-1] # 역순으로 반환하여 시작부터 목표까지의 경로 반환
while 루프 : 열린 리스트에 노드가 남아있는 동안 반복합니다.
열린 리스트에서 f(n) = g(n) + h(n) 값이 가장 작은 노드를 선택하고, 이 노드가 목표 노드인지 검사합니다.
목표 노드에 도달하면 경로를 추적하고 반환합니다.
closed_set.add((current_node.x, current_node.y)) # 현재 노드를 닫힌 세트에 추가
# 네가지 방향(상하좌우)을 사용하여 이동하는 것을 구현
for x, y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
new_x, new_y = current_node.x + x, current_node.y + y # 이웃 노드 좌표 계산
# 유효한 이웃 노드인지 확인하고 이미 검사한 노드가 아니라면 진행
if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]) and grid[new_x][new_y] != 1 and (new_x, new_y) not in closed_set:
neighbor = Node(new_x, new_y, current_node) # 이웃 노드 초기화
neighbor.g = current_node.g + 1 # 이웃 노드의 g(n) 값 업데이트
neighbor.h = abs(new_x - end_node.x) + abs(new_y - end_node.y) # 이웃 노드의 h(n) 값 계산 (맨해튼 거리 휴리스틱)
if neighbor not in open_list:
heapq.heappush(open_list, neighbor) # 이웃 노드를 열린 리스트에 추가
이웃 노드 검사 : 현재 노드의 이웃 노드를 검사하고, 이웃 노드가 유효하고 이미 검사한 노드가 아니라면
이웃 노드를 열린 리스트에 추가합니다.
이 때, 이웃노드 g(n) 값을 업데이트하고, h(n) 값을 맨해튼 거리 휴리스틱 함수를 사용하여 계산합니다.
'개발 > Python' 카테고리의 다른 글
| [python] Lambda 함수: 간결한 함수 정의와 활용 (1) | 2024.01.21 |
|---|---|
| [Python] 구글 뉴스 크롤링하기 (2) | 2024.01.04 |
| [Python] 윈도우 venv 가상환경 설치하기 (1) | 2023.01.25 |
| [Python] venv 가상환경 설정이 필요한 이유는? (0) | 2023.01.25 |
