Path Search Algorithms Simple Overview

 

 

Algorithm	Always Shortest Path	Movement Costs	Multiple Start or End Points	Speed
Breadth First Search	✔	✖	✔	Medium
Dijkstra	✔	✔	✔	Slow
A*	❔	✔	✖	Fast

 

 

A* 알고리즘은 최단경로를 찾을 때 속도와 정확도 사이에서 트레이드 오프 할 수 있다.

 

BFS 알고리즘은 이동 비용을 다루지 못함. (포인트간 간선 또는 가중치의 계산을 할 수 없음) (List, Queue 써서 쉽게 만들 수 있다)

 

A* 알고리즘은 한 포인트에서 한 포인트로 연결되는 알고리즘이라 여러 시작점과 종료점의 선택이 불가능.

 

A* 알고리즘은 정확도를 높이게 되면 느려짐.

그리고 휴리스틱 탐색 방법에 의존하기에 나쁜 방법을 고르게 되면 Dijkstra 알고리즘으로 전환되면서 아주 느려짐.