[점검퀴즈]길찾기,우수법,다익스트라,에이스타,FathFinding,RightHand,Dijkstra,AStar,A*

1.우수법

1.1 특징

-

-

-

 

1.2 Flow를 설명하세요(그림 또는 의사코드)

 

 

 

 

2.다익스트라

2.1 특징

-

-

-

 

2.2 Flow를 설명하세요(그림 또는 의사코드)

 

 

 

 

3.에이스타

3.1 특징

-

-

-

 

3.2 Flow를 설명하세요(그림 또는 의사코드)

 

 

 

 

4. BFS, 다익스트라, Astar의 차이점에 대해서 각 알고리즘을 비교하여 설명하시오.

-

-

-

-

 

5.다익스트라 구현하기

c++

c#

 

 

4번풀이

- 다익스트라는 BFS와 다르게 가중치 계산이 가능하고 때문에 가중치를 통해서 더 유리한 탐색 후보군을 추려야 한다.

- BFS와 다익스트라는 목적지가 없는 탐색방법이다. 그렇기 떄문에 목적지를 찾아가는 개념이 아니라, 탐색하다 보니 목적지에 닿아서 탐색을 종료하는 개념이다.

- 따라서 bfs, 다익스트트라 길찾기로는 항상 최단 거리를 구하는 것이 아니다.

- 에이스타는 다익스트라와 다르게 목적지를 향해 탐색한다. 다익스트라에서 탐색 후보군을 계산하는 과정에서 [현재-목적지] 코스트를 계산하는 연산이 추가된다고 생각하면 된다.