A* 알고리즘 설명

A* 는 BFS 방식을 이용해 최단 경로를 구하는 알고리즘이다.

 

공식

F = G + H

G는 시작점으로부터 해당 노드까지의 이동 비용,

H는 해당 노드로부터 도착지까지의 예상 이동 비용이다. (휴리스틱에 대한 설명)

 

단점

맵의 크기가 커지면 Open Queue와 Closed Queue에 수 많은 노드들이 들어갈 수 있어서 메모리를 많이 차지하게 된다.

또한 시작점부터 도착지까지의 경로가 존재하지 않는 경우 모든 노드를 검색하므로 비효율적이다.

 

 

+ 맵을 어떤 자료구조로 구현하는게 좋을까 생각해봤는데 굳이 노드를 더 추가할 계획이 아니라면 배열을 사용해 인덱스 접근으로 탐색하는게 좋을 것 같다.

    - vector : 나중에 노드를 추가하는 경우가 아니라면 굳이?

    - list : 인덱스가 없어서.. 인접한 노드에 어떻게 접근할 것인지?

    - map : key에 노드, value에 인접 노드 벡터를 넣어도 되지만 배열 인덱스 접근이 더 편할텐데 굳이..?