A* 알고리즘은 출발 노드부터 목표 노드까지 가는 최단 경로 찾는 그래프 탐색 알고리즘 중 하나이다.
Dijkstra algorithm과 유사하지만, 목표 노드까지의 휴리스틱 거리 측정값인 h(n)도 사용한다는 점에서 다르다.
가장 작은 비용 갖는 사각형끼리 서로 이으면 시작 지점과 목표 지점 잇는 경로 생성됨 -> 각 비용 적게 드는 경로끼리 연결했으니까 찾은 경로가 최단 경로
g(n): 출발~현재 노드 n까지 도달하기 위한 최단 비용, = 유클라디안 거리
h(n): 현재 노드 n에서 목표 노드까지 예상 이동 비용, = 휴리스틱 거리 측정값, 맨하튼 거리
f(n): g + h, 총 비용
출발 노드 부터 인접한 사각형 확인하면서 경로 만듦
잉공지능