[Study] Graph와 길찾기

길찾기 알고리즘 종류

- DFS / BFS

- 다익스트라 알고리즘

- 플로이드 워셜 알고리즘

- A* 알고리즘

 

 

각 길찾기 알고리즘의 차이점?

 DFS / BFS

CT-Study/PART 2/Chapter 5, DFS&BFS.md at master · JeongEunJi1127/CT-Study

 

 

 

다익스트라 알고리즘

- 특정 노드에서 갈 수 있는 모든 경로에 대한 최단 거리를 찾고 그 중 가장 비용이 적은 노드를 선택

- 위의 정의에서 알 수 있듯이 그리디 알고리즘으로 분류된다

- 시간복잡도 : O(N^2) (개선된 다익스트라 알고리즘은 O(ElogV) (V = 노드의 개수, E = 간선의 개수) )

 

CT-Study/PART 2/Chapter 9, 최단 경로.md at master · JeongEunJi1127/CT-Study

 

 

플로이드 워셜 알고리즘

- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용

- 시간복잡도 : O(N^3) 

 

 

A* 알고리즘

아래 참고

 

 

A* 알고리즘

다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘 

출발 꼭짓점에서 목표 꼭짓점까지 가는 최단 경로를 찾아내는 휴리스틱 기반의 그래프 탐색 알고리즘

즉, 출발지와 도착지가 주어질 때 최단 경로를 찾는 휴리스틱 알고리즘이다.

다음으로 갈 정점을 결정할 때 목표 지점으로 부터 멀어지는 것을 고려하지 않는 다익스트라 알고리즘과 달리 에이스타 알고리즘은 목표 지점까지의 추정 코스트도 함께 고려해서 탐색한다.

1. 그래프 상에서의 모든 정점의 부모 노드를 -1로 초기화하고, 비용은 INF값으로 설정한다.
2. 시작노드의 비용을 0으로 초기화하고, 시작노드의 부모노드는 시작노드를 가리킨다.
3. 현재 노드를 기준으로 모든 방향의 노드에 대한 비용을 계산한다.
4. 비용이 계산된 노드들 중 최소 비용을 가지는 노드가 다음 노드가 된다.
5. 다음 노드의 부모노드는 현재 노드를 가리킨다.
6. 3~5를 반복한다.
7. 만약 다음 노드가 도착노드라면, 탐색을 중지하고 최적의 경로를 계산한다.

 

 

 

 

예시

Graph가 무엇인지 알고 있나요?

노드(node)와 노드를 연결하는 간선(edge)들로 이루어져 있는 자료구조

& 사이클 존재 가능

& 루트 노드 존재 X

& 방향 그래프 뿐 아니라 무방향 그래프도 존재한다

 

Tree는 Graph인가요? Graph는 Tree인가요?

Tree는 Graph이다. Graph가 더 큰 개념

 

NavMesh가 길찾기를 위해 사용하는 알고리즘은 무엇인가요?

: A* 알고리즘