Python :: 최단 경로 - A* 알고리즘

A* 알고리즘

https://github.com/ysshah95/Astar-Algorithm-for-ACME-Robotics

• Best-Frist 검색을 이용해 시작점에서 도착점까지의 가장 적은 비용을 사용하는 경로를 찾아내는 알고리즘
• Best-First-Search에 목적점에 이르는 잔여추정거리를 고려하는 알고리즘

Best-First 검색 : 조사하지 않은 node 중에서 가장 효율적이라고 판단되는 node를 찾음

 

찾아진 node가 도착점이면 종료 / 아니면 다른 node들에서 찾음

조사한 노드들은 close list에 저장 / 조사하지 않은 노드들은 open list에 저장

초기화 : close list - 공집합 / open list 시작점

종료 시점 : 목표노드가 closed list에 추가 / open list가 empty 일 때 - 목표 노드를 찾는데 실패 = 경로 없음

 

Best-First-Search

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

	f(n)	g(n)	h(n)
요약	잔여추정거리	목적 함수	Heuristic function
설명	n 까지 가는데 가장 저렴한 거리의 전체 비용	시작지점에서 n 까지의 경로 값 (거리)	n부터 목표 지점까지의 가장 저렴한 거리의 비용
			문제에 따라 합당한 값으로 주어짐 (맨해튼 거리, 유클리드 거리 등)

 

참고 코드

https://choiseokwon.tistory.com/210

https://www.secmem.org/blog/2020/04/19/astar/