a-star 알고리즘
- 휴리스틱을 사용하는 최단 경로 탐색 알고리즘이다.
- 주로 global path planning에서 사용
- 이는 시작노드에서 목표 노드까지 비용이 가장 적게 드는 경로를 찾는다.
- 휴리스틱 함수
- 현재 위치에서 목표 노드까지의 추정 비용을 계산하는 함수
- g(n) : 출발 노드에서 특정 노드 n까지의 실제 비용
- h(n) : 특정 노드에서 목표 노드까지의 추정 비용 ( 이것이 휴리스틱 함수이다.)
- f(n) = g(n) + h(n) : f(n)은 특정 노드n에서 목표노드까지의 예상 총 비용이다.
- a star알고리즘은 각 노드에 대해서 f(n)을 계산하고, 이 값을 기준으로 경로를 탐색함.
- 장점
- 최단 경로 보장
- 구현이 간단 및 격자 기반 환경에 적합
- 단점
- 격자의 해상도가 높아질수록 계산량이 급격히 증가함
- 동적인 장애물에 대해서 실시간 대응이 어려움
- 응용 사례
- 로봇의 장애물 회피 및 단순한 실내 환경 경로 탐색
- 게임에서 커릭터의 이동 경로 설정
import heapq
# 휴리스틱 함수: 현재 노드와 목표 노드간의 추정 비용을 걔산함. 여기서는 맨해큰 거리를 이용함.
def heuristic(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
# 경로 재구성 함수. 목표 노드에서 출발 노드까지의 최적 경로를 추적함.
def reconstruct_path(rst_shortest_node, current_node):
total_path = [current_node]
print(f'\역순으로 찾아가며 경로를 재구성합니다. total_path 초기값은 {total_path}입니다.')
while current_node in rst_shortest_node:
print(f'current node is {current_node} and rst_shortst node[current node] is {rst_shortest_node[current_node]}')
current_node = rst_shortest_node[current_node]
total_path.append(current_node)
print(f'\n경로를 재구성합니다. total_path은 {total_path}입니다.')
return total_path[::-1]
# 이웃 노드 반환 함수
def get_neighbors(graph, node): # 그래프와 current_node를 입력받음.
neighbors = [] # 이웃노드를 저장할 리스트
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 상하좌우로 움직이기 위한 방향들
for d in directions: # 각 4방향에 대해서...
neighbor = (node[0] + d[0], node[1] + d[1]) # 이웃노드의 좌표를 계산함.
if 0 <= neighbor[0] < len(graph) and 0 <= neighbor[1] < len(graph[0]): # 좌표가 유효한지 체크함.
neighbors.append(neighbor) # 유효한 좌표면, 이웃 리스티에 추가
return neighbors # 리턴
# A* 알고리즘.
def a_star_search(graph, start, goal):
priority_queue = [] # 우선순위 큐를 초기화 시킨다.
heapq.heappush(priority_queue, (0, start)) # 시작 노드를 큐에 추가 시킴. (f_score값 , 노드)
print(f'시작하는 노드는 {start}입니다... priority_queue : {priority_queue}')
# g(n)을 저장하는 딕셔너리 선언합니다. ( 출발 노드에서 특정 노드 n까지의 실제 비용)
g_score = { (i, j): float('inf') for i in range(len(graph)) for j in range(len(graph[0])) }
g_score[start] = 0 # 출발 노드의 g_score는 0입니다.
# f(n)을 저장하는 딕셔너리. ( f(n) = g(n) + h(n) )
f_score = { (i, j): float('inf') for i in range(len(graph)) for j in range(len(graph[0])) }
f_score[start] = heuristic(start, goal) # 출발 노드의 f_Score는 h(n)으로 초기화
print(f'초기화 한 g_score는 {g_score}입니다.\n초기화 한 f_score는 {f_score}입니다.\n\n ')
came_from = {} # 경로를 추적하기 위한 딕셔너리. 각 노드의 이전 노드들을 저장. 즉 , 현재 노드에서 가장 가까운 거리의 노드를 저장하는거
while priority_queue:
print(f'\n현재의 priority_queue에는 {priority_queue}가 존재...\n각 노드의 이전 노드들은 {came_from}입니다.')
current_node = heapq.heappop(priority_queue)[1]
print(f'while문 입니다. current_node는 {current_node}입니다.')
if current_node == goal:
print(f'\n=====cuurent_node가 goal에 도달하였습니다... current_node==goal는 {current_node} == {goal}')
return reconstruct_path(came_from, current_node)
for neighbor in get_neighbors(graph, current_node):# 현재 노드의 주변의 이웃노드를 확인해서, 해당 노드에 대해서 처리..
tmp_g_score = g_score[current_node] + graph[ neighbor[0] ][ neighbor[1] ] # 현재 노드를 거쳐서, 이웃노드로 가는 경로 비용을 계산
print(f'현재 노드는 {current_node}이며, 현재 방문하려는 이웃노드는 {neighbor}입니다. 현재노드의 g_score는 {g_score[current_node]}이며 이웃노드로 가려면 {graph[ neighbor[0] ][ neighbor[1] ]}필요')
print(f'=========> 현재 노드에서 이웃노드로 가는 비용은 {tmp_g_score}이며, 기존의 g_score는 {g_score[ neighbor ]}', end='')
if tmp_g_score < g_score[ neighbor ]:# 새로운 경로가 더 짧은 경우에 갱신
came_from[neighbor] = current_node # 이웃 노드의 이전 노드를 현재 노드로 설정
print(f'\n===============> 갱신... {neighbor}의 새로운 shortest한 노드는 {came_from[neighbor]}입니다. ' , end='')
g_score[neighbor] = tmp_g_score
f_score[neighbor] = tmp_g_score + heuristic(neighbor, goal)
print(f'---------======>f(x)는 {f_score[neighbor]}이며 g(x)는 {g_score[neighbor]}이고 h(x)는 { heuristic(neighbor, goal)}입니다. ' , end='')
if neighbor not in [i[1] for i in priority_queue]:
heapq.heappush(priority_queue, (f_score[neighbor], neighbor))
else:
print('\n**갱신안함',end='')
print()
return None
ex_graph = [
[1, 3, 1, 1 , 3],
[1, 5, 10, 1 , 5],
[4, 12, 9, 1 , 1],
[1, 1, 1, 7 , 2]
]
# 시작 노드와 목표 노드 설정
start = (0, 0) # 좌상단 (0,0)
goal = (3, 4) # 우하단 (3,3)
# 알고리즘 실행
path = a_star_search(ex_graph, start, goal)
# 결과 출력
if path:
print("최단 경로:", path)
else:
print("목표 노드에 도달할 수 없습니다.")
시작하는 노드는 (0, 0)입니다... priority_queue : [(0, (0, 0))]
초기화 한 g_score는 {(0, 0): 0, (0, 1): inf, (0, 2): inf, (0, 3): inf, (0, 4): inf, (1, 0): inf, (1, 1): inf, (1, 2): inf, (1, 3): inf, (1, 4): inf, (2, 0): inf, (2, 1): inf, (2, 2): inf, (2, 3): inf, (2, 4): inf, (3, 0): inf, (3, 1): inf, (3, 2): inf, (3, 3): inf, (3, 4): inf}입니다.
초기화 한 f_score는 {(0, 0): 7, (0, 1): inf, (0, 2): inf, (0, 3): inf, (0, 4): inf, (1, 0): inf, (1, 1): inf, (1, 2): inf, (1, 3): inf, (1, 4): inf, (2, 0): inf, (2, 1): inf, (2, 2): inf, (2, 3): inf, (2, 4): inf, (3, 0): inf, (3, 1): inf, (3, 2): inf, (3, 3): inf, (3, 4): inf}입니다.
현재의 priority_queue에는 [(0, (0, 0))]가 존재...
각 노드의 이전 노드들은 {}입니다.
while문 입니다. current_node는 (0, 0)입니다.
현재 노드는 (0, 0)이며, 현재 방문하려는 이웃노드는 (0, 1)입니다. 현재노드의 g_score는 0이며 이웃노드로 가려면 3필요
=========> 현재 노드에서 이웃노드로 가는 비용은 3이며, 기존의 g_score는 inf
===============> 갱신... (0, 1)의 새로운 shortest한 노드는 (0, 0)입니다. ---------======>f(x)는 9이며 g(x)는 3이고 h(x)는 6입니다.
현재 노드는 (0, 0)이며, 현재 방문하려는 이웃노드는 (1, 0)입니다. 현재노드의 g_score는 0이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 1이며, 기존의 g_score는 inf
===============> 갱신... (1, 0)의 새로운 shortest한 노드는 (0, 0)입니다. ---------======>f(x)는 7이며 g(x)는 1이고 h(x)는 6입니다.
현재의 priority_queue에는 [(7, (1, 0)), (9, (0, 1))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0)}입니다.
while문 입니다. current_node는 (1, 0)입니다.
현재 노드는 (1, 0)이며, 현재 방문하려는 이웃노드는 (1, 1)입니다. 현재노드의 g_score는 1이며 이웃노드로 가려면 5필요
=========> 현재 노드에서 이웃노드로 가는 비용은 6이며, 기존의 g_score는 inf
===============> 갱신... (1, 1)의 새로운 shortest한 노드는 (1, 0)입니다. ---------======>f(x)는 11이며 g(x)는 6이고 h(x)는 5입니다.
현재 노드는 (1, 0)이며, 현재 방문하려는 이웃노드는 (2, 0)입니다. 현재노드의 g_score는 1이며 이웃노드로 가려면 4필요
=========> 현재 노드에서 이웃노드로 가는 비용은 5이며, 기존의 g_score는 inf
===============> 갱신... (2, 0)의 새로운 shortest한 노드는 (1, 0)입니다. ---------======>f(x)는 10이며 g(x)는 5이고 h(x)는 5입니다.
현재 노드는 (1, 0)이며, 현재 방문하려는 이웃노드는 (0, 0)입니다. 현재노드의 g_score는 1이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 2이며, 기존의 g_score는 0
**갱신안함
현재의 priority_queue에는 [(9, (0, 1)), (11, (1, 1)), (10, (2, 0))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0)}입니다.
while문 입니다. current_node는 (0, 1)입니다.
현재 노드는 (0, 1)이며, 현재 방문하려는 이웃노드는 (0, 2)입니다. 현재노드의 g_score는 3이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 4이며, 기존의 g_score는 inf
===============> 갱신... (0, 2)의 새로운 shortest한 노드는 (0, 1)입니다. ---------======>f(x)는 9이며 g(x)는 4이고 h(x)는 5입니다.
현재 노드는 (0, 1)이며, 현재 방문하려는 이웃노드는 (1, 1)입니다. 현재노드의 g_score는 3이며 이웃노드로 가려면 5필요
=========> 현재 노드에서 이웃노드로 가는 비용은 8이며, 기존의 g_score는 6
**갱신안함
현재 노드는 (0, 1)이며, 현재 방문하려는 이웃노드는 (0, 0)입니다. 현재노드의 g_score는 3이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 4이며, 기존의 g_score는 0
**갱신안함
현재의 priority_queue에는 [(9, (0, 2)), (11, (1, 1)), (10, (2, 0))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1)}입니다.
while문 입니다. current_node는 (0, 2)입니다.
현재 노드는 (0, 2)이며, 현재 방문하려는 이웃노드는 (0, 3)입니다. 현재노드의 g_score는 4이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 5이며, 기존의 g_score는 inf
===============> 갱신... (0, 3)의 새로운 shortest한 노드는 (0, 2)입니다. ---------======>f(x)는 9이며 g(x)는 5이고 h(x)는 4입니다.
현재 노드는 (0, 2)이며, 현재 방문하려는 이웃노드는 (1, 2)입니다. 현재노드의 g_score는 4이며 이웃노드로 가려면 10필요
=========> 현재 노드에서 이웃노드로 가는 비용은 14이며, 기존의 g_score는 inf
===============> 갱신... (1, 2)의 새로운 shortest한 노드는 (0, 2)입니다. ---------======>f(x)는 18이며 g(x)는 14이고 h(x)는 4입니다.
현재 노드는 (0, 2)이며, 현재 방문하려는 이웃노드는 (0, 1)입니다. 현재노드의 g_score는 4이며 이웃노드로 가려면 3필요
=========> 현재 노드에서 이웃노드로 가는 비용은 7이며, 기존의 g_score는 3
**갱신안함
현재의 priority_queue에는 [(9, (0, 3)), (11, (1, 1)), (10, (2, 0)), (18, (1, 2))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1), (0, 3): (0, 2), (1, 2): (0, 2)}입니다.
while문 입니다. current_node는 (0, 3)입니다.
현재 노드는 (0, 3)이며, 현재 방문하려는 이웃노드는 (0, 4)입니다. 현재노드의 g_score는 5이며 이웃노드로 가려면 3필요
=========> 현재 노드에서 이웃노드로 가는 비용은 8이며, 기존의 g_score는 inf
===============> 갱신... (0, 4)의 새로운 shortest한 노드는 (0, 3)입니다. ---------======>f(x)는 11이며 g(x)는 8이고 h(x)는 3입니다.
현재 노드는 (0, 3)이며, 현재 방문하려는 이웃노드는 (1, 3)입니다. 현재노드의 g_score는 5이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 6이며, 기존의 g_score는 inf
===============> 갱신... (1, 3)의 새로운 shortest한 노드는 (0, 3)입니다. ---------======>f(x)는 9이며 g(x)는 6이고 h(x)는 3입니다.
현재 노드는 (0, 3)이며, 현재 방문하려는 이웃노드는 (0, 2)입니다. 현재노드의 g_score는 5이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 6이며, 기존의 g_score는 4
**갱신안함
현재의 priority_queue에는 [(9, (1, 3)), (10, (2, 0)), (18, (1, 2)), (11, (1, 1)), (11, (0, 4))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1), (0, 3): (0, 2), (1, 2): (0, 2), (0, 4): (0, 3), (1, 3): (0, 3)}입니다.
while문 입니다. current_node는 (1, 3)입니다.
현재 노드는 (1, 3)이며, 현재 방문하려는 이웃노드는 (1, 4)입니다. 현재노드의 g_score는 6이며 이웃노드로 가려면 5필요
=========> 현재 노드에서 이웃노드로 가는 비용은 11이며, 기존의 g_score는 inf
===============> 갱신... (1, 4)의 새로운 shortest한 노드는 (1, 3)입니다. ---------======>f(x)는 13이며 g(x)는 11이고 h(x)는 2입니다.
현재 노드는 (1, 3)이며, 현재 방문하려는 이웃노드는 (2, 3)입니다. 현재노드의 g_score는 6이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 7이며, 기존의 g_score는 inf
===============> 갱신... (2, 3)의 새로운 shortest한 노드는 (1, 3)입니다. ---------======>f(x)는 9이며 g(x)는 7이고 h(x)는 2입니다.
현재 노드는 (1, 3)이며, 현재 방문하려는 이웃노드는 (1, 2)입니다. 현재노드의 g_score는 6이며 이웃노드로 가려면 10필요
=========> 현재 노드에서 이웃노드로 가는 비용은 16이며, 기존의 g_score는 14
**갱신안함
현재 노드는 (1, 3)이며, 현재 방문하려는 이웃노드는 (0, 3)입니다. 현재노드의 g_score는 6이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 7이며, 기존의 g_score는 5
**갱신안함
현재의 priority_queue에는 [(9, (2, 3)), (11, (0, 4)), (10, (2, 0)), (11, (1, 1)), (13, (1, 4)), (18, (1, 2))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1), (0, 3): (0, 2), (1, 2): (0, 2), (0, 4): (0, 3), (1, 3): (0, 3), (1, 4): (1, 3), (2, 3): (1, 3)}입니다.
while문 입니다. current_node는 (2, 3)입니다.
현재 노드는 (2, 3)이며, 현재 방문하려는 이웃노드는 (2, 4)입니다. 현재노드의 g_score는 7이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 8이며, 기존의 g_score는 inf
===============> 갱신... (2, 4)의 새로운 shortest한 노드는 (2, 3)입니다. ---------======>f(x)는 9이며 g(x)는 8이고 h(x)는 1입니다.
현재 노드는 (2, 3)이며, 현재 방문하려는 이웃노드는 (3, 3)입니다. 현재노드의 g_score는 7이며 이웃노드로 가려면 7필요
=========> 현재 노드에서 이웃노드로 가는 비용은 14이며, 기존의 g_score는 inf
===============> 갱신... (3, 3)의 새로운 shortest한 노드는 (2, 3)입니다. ---------======>f(x)는 15이며 g(x)는 14이고 h(x)는 1입니다.
현재 노드는 (2, 3)이며, 현재 방문하려는 이웃노드는 (2, 2)입니다. 현재노드의 g_score는 7이며 이웃노드로 가려면 9필요
=========> 현재 노드에서 이웃노드로 가는 비용은 16이며, 기존의 g_score는 inf
===============> 갱신... (2, 2)의 새로운 shortest한 노드는 (2, 3)입니다. ---------======>f(x)는 19이며 g(x)는 16이고 h(x)는 3입니다.
현재 노드는 (2, 3)이며, 현재 방문하려는 이웃노드는 (1, 3)입니다. 현재노드의 g_score는 7이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 8이며, 기존의 g_score는 6
**갱신안함
현재의 priority_queue에는 [(9, (2, 4)), (11, (0, 4)), (10, (2, 0)), (11, (1, 1)), (13, (1, 4)), (18, (1, 2)), (15, (3, 3)), (19, (2, 2))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1), (0, 3): (0, 2), (1, 2): (0, 2), (0, 4): (0, 3), (1, 3): (0, 3), (1, 4): (1, 3), (2, 3): (1, 3), (2, 4): (2, 3), (3, 3): (2, 3), (2, 2): (2, 3)}입니다.
while문 입니다. current_node는 (2, 4)입니다.
현재 노드는 (2, 4)이며, 현재 방문하려는 이웃노드는 (3, 4)입니다. 현재노드의 g_score는 8이며 이웃노드로 가려면 2필요
=========> 현재 노드에서 이웃노드로 가는 비용은 10이며, 기존의 g_score는 inf
===============> 갱신... (3, 4)의 새로운 shortest한 노드는 (2, 4)입니다. ---------======>f(x)는 10이며 g(x)는 10이고 h(x)는 0입니다.
현재 노드는 (2, 4)이며, 현재 방문하려는 이웃노드는 (2, 3)입니다. 현재노드의 g_score는 8이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 9이며, 기존의 g_score는 7
**갱신안함
현재 노드는 (2, 4)이며, 현재 방문하려는 이웃노드는 (1, 4)입니다. 현재노드의 g_score는 8이며 이웃노드로 가려면 5필요
=========> 현재 노드에서 이웃노드로 가는 비용은 13이며, 기존의 g_score는 11
**갱신안함
현재의 priority_queue에는 [(10, (2, 0)), (10, (3, 4)), (15, (3, 3)), (11, (0, 4)), (13, (1, 4)), (18, (1, 2)), (19, (2, 2)), (11, (1, 1))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1), (0, 3): (0, 2), (1, 2): (0, 2), (0, 4): (0, 3), (1, 3): (0, 3), (1, 4): (1, 3), (2, 3): (1, 3), (2, 4): (2, 3), (3, 3): (2, 3), (2, 2): (2, 3), (3, 4): (2, 4)}입니다.
while문 입니다. current_node는 (2, 0)입니다.
현재 노드는 (2, 0)이며, 현재 방문하려는 이웃노드는 (2, 1)입니다. 현재노드의 g_score는 5이며 이웃노드로 가려면 12필요
=========> 현재 노드에서 이웃노드로 가는 비용은 17이며, 기존의 g_score는 inf
===============> 갱신... (2, 1)의 새로운 shortest한 노드는 (2, 0)입니다. ---------======>f(x)는 21이며 g(x)는 17이고 h(x)는 4입니다.
현재 노드는 (2, 0)이며, 현재 방문하려는 이웃노드는 (3, 0)입니다. 현재노드의 g_score는 5이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 6이며, 기존의 g_score는 inf
===============> 갱신... (3, 0)의 새로운 shortest한 노드는 (2, 0)입니다. ---------======>f(x)는 10이며 g(x)는 6이고 h(x)는 4입니다.
현재 노드는 (2, 0)이며, 현재 방문하려는 이웃노드는 (1, 0)입니다. 현재노드의 g_score는 5이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 6이며, 기존의 g_score는 1
**갱신안함
현재의 priority_queue에는 [(10, (3, 0)), (10, (3, 4)), (15, (3, 3)), (11, (0, 4)), (13, (1, 4)), (18, (1, 2)), (19, (2, 2)), (21, (2, 1)), (11, (1, 1))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1), (0, 3): (0, 2), (1, 2): (0, 2), (0, 4): (0, 3), (1, 3): (0, 3), (1, 4): (1, 3), (2, 3): (1, 3), (2, 4): (2, 3), (3, 3): (2, 3), (2, 2): (2, 3), (3, 4): (2, 4), (2, 1): (2, 0), (3, 0): (2, 0)}입니다.
while문 입니다. current_node는 (3, 0)입니다.
현재 노드는 (3, 0)이며, 현재 방문하려는 이웃노드는 (3, 1)입니다. 현재노드의 g_score는 6이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 7이며, 기존의 g_score는 inf
===============> 갱신... (3, 1)의 새로운 shortest한 노드는 (3, 0)입니다. ---------======>f(x)는 10이며 g(x)는 7이고 h(x)는 3입니다.
현재 노드는 (3, 0)이며, 현재 방문하려는 이웃노드는 (2, 0)입니다. 현재노드의 g_score는 6이며 이웃노드로 가려면 4필요
=========> 현재 노드에서 이웃노드로 가는 비용은 10이며, 기존의 g_score는 5
**갱신안함
현재의 priority_queue에는 [(10, (3, 1)), (10, (3, 4)), (15, (3, 3)), (11, (0, 4)), (13, (1, 4)), (18, (1, 2)), (19, (2, 2)), (21, (2, 1)), (11, (1, 1))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1), (0, 3): (0, 2), (1, 2): (0, 2), (0, 4): (0, 3), (1, 3): (0, 3), (1, 4): (1, 3), (2, 3): (1, 3), (2, 4): (2, 3), (3, 3): (2, 3), (2, 2): (2, 3), (3, 4): (2, 4), (2, 1): (2, 0), (3, 0): (2, 0), (3, 1): (3, 0)}입니다.
while문 입니다. current_node는 (3, 1)입니다.
현재 노드는 (3, 1)이며, 현재 방문하려는 이웃노드는 (3, 2)입니다. 현재노드의 g_score는 7이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 8이며, 기존의 g_score는 inf
===============> 갱신... (3, 2)의 새로운 shortest한 노드는 (3, 1)입니다. ---------======>f(x)는 10이며 g(x)는 8이고 h(x)는 2입니다.
현재 노드는 (3, 1)이며, 현재 방문하려는 이웃노드는 (3, 0)입니다. 현재노드의 g_score는 7이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 8이며, 기존의 g_score는 6
**갱신안함
현재 노드는 (3, 1)이며, 현재 방문하려는 이웃노드는 (2, 1)입니다. 현재노드의 g_score는 7이며 이웃노드로 가려면 12필요
=========> 현재 노드에서 이웃노드로 가는 비용은 19이며, 기존의 g_score는 17
**갱신안함
현재의 priority_queue에는 [(10, (3, 2)), (10, (3, 4)), (15, (3, 3)), (11, (0, 4)), (13, (1, 4)), (18, (1, 2)), (19, (2, 2)), (21, (2, 1)), (11, (1, 1))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1), (0, 3): (0, 2), (1, 2): (0, 2), (0, 4): (0, 3), (1, 3): (0, 3), (1, 4): (1, 3), (2, 3): (1, 3), (2, 4): (2, 3), (3, 3): (2, 3), (2, 2): (2, 3), (3, 4): (2, 4), (2, 1): (2, 0), (3, 0): (2, 0), (3, 1): (3, 0), (3, 2): (3, 1)}입니다.
while문 입니다. current_node는 (3, 2)입니다.
현재 노드는 (3, 2)이며, 현재 방문하려는 이웃노드는 (3, 3)입니다. 현재노드의 g_score는 8이며 이웃노드로 가려면 7필요
=========> 현재 노드에서 이웃노드로 가는 비용은 15이며, 기존의 g_score는 14
**갱신안함
현재 노드는 (3, 2)이며, 현재 방문하려는 이웃노드는 (3, 1)입니다. 현재노드의 g_score는 8이며 이웃노드로 가려면 1필요
=========> 현재 노드에서 이웃노드로 가는 비용은 9이며, 기존의 g_score는 7
**갱신안함
현재 노드는 (3, 2)이며, 현재 방문하려는 이웃노드는 (2, 2)입니다. 현재노드의 g_score는 8이며 이웃노드로 가려면 9필요
=========> 현재 노드에서 이웃노드로 가는 비용은 17이며, 기존의 g_score는 16
**갱신안함
현재의 priority_queue에는 [(10, (3, 4)), (11, (0, 4)), (15, (3, 3)), (11, (1, 1)), (13, (1, 4)), (18, (1, 2)), (19, (2, 2)), (21, (2, 1))]가 존재...
각 노드의 이전 노드들은 {(0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 0), (2, 0): (1, 0), (0, 2): (0, 1), (0, 3): (0, 2), (1, 2): (0, 2), (0, 4): (0, 3), (1, 3): (0, 3), (1, 4): (1, 3), (2, 3): (1, 3), (2, 4): (2, 3), (3, 3): (2, 3), (2, 2): (2, 3), (3, 4): (2, 4), (2, 1): (2, 0), (3, 0): (2, 0), (3, 1): (3, 0), (3, 2): (3, 1)}입니다.
while문 입니다. current_node는 (3, 4)입니다.
=====cuurent_node가 goal에 도달하였습니다... current_node==goal는 (3, 4) == (3, 4)
\역순으로 찾아가며 경로를 재구성합니다. total_path 초기값은 [(3, 4)]입니다.
current node is (3, 4) and rst_shortst node[current node] is (2, 4)
current node is (2, 4) and rst_shortst node[current node] is (2, 3)
current node is (2, 3) and rst_shortst node[current node] is (1, 3)
current node is (1, 3) and rst_shortst node[current node] is (0, 3)
current node is (0, 3) and rst_shortst node[current node] is (0, 2)
current node is (0, 2) and rst_shortst node[current node] is (0, 1)
current node is (0, 1) and rst_shortst node[current node] is (0, 0)
경로를 재구성합니다. total_path은 [(3, 4), (2, 4), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0)]입니다.
최단 경로: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 4), (3, 4)]