차이가 있는 것을 어렴풋이 알겠는데 어떻게 딱 설명을 할 수가 없네요..
누군가 물어본다면 어떻게 설명을 해야될까요.
두 알고리즘다 최소비용을 갖는 노드를 탐색하는데 정확히 어떻게 말해야되는지...
둘 다 결과는 똑같은데 과정이 다릅니다.
다음 탐색할 노드를 선택할 때, 다익스트라는 d(n)이 최소인 노드 n을 선택하고 A*는 d(n) + h(n)이 최소인 노드 n을 선택한다는 차이가 있습니다. 여기서 d(n)은 출발점에서 노드 n까지 거리, h(n)은 노드 n에서 도착점까지의 거리 추정치.
다르게 설명하자면 다익스트라는 출발점에서 가장 가까운 노드를 우선 탐색하고, A*는 최단 경로를 만들 수 있을 것 같은 노드를 우선 탐색합니다.
그래서 A*는 best-first search라고도 불립니다. 반면, 다익스트라는 unweighted graph에서는 breadth-first search가 되죠.
둘 다 결과는 똑같은데 과정이 다릅니다.
둘 다 결과는 똑같은데 과정이 다릅니다.
다음 탐색할 노드를 선택할 때, 다익스트라는 d(n)이 최소인 노드 n을 선택하고 A*는 d(n) + h(n)이 최소인 노드 n을 선택한다는 차이가 있습니다. 여기서 d(n)은 출발점에서 노드 n까지 거리, h(n)은 노드 n에서 도착점까지의 거리 추정치.
다르게 설명하자면 다익스트라는 출발점에서 가장 가까운 노드를 우선 탐색하고, A*는 최단 경로를 만들 수 있을 것 같은 노드를 우선 탐색합니다.
그래서 A*는 best-first search라고도 불립니다. 반면, 다익스트라는 unweighted graph에서는 breadth-first search가 되죠.