차이가 있는 것을 어렴풋이 알겠는데 어떻게 딱 설명을 할 수가 없네요..
누군가 물어본다면 어떻게 설명을 해야될까요.
두 알고리즘다 최소비용을 갖는 노드를 탐색하는데 정확히 어떻게 말해야되는지...
둘 다 결과는 똑같은데 과정이 다릅니다.
다음 탐색할 노드를 선택할 때, 다익스트라는 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가 되죠.
텍스트 포맷에 대한 자세한 정보
<code>
<blockcode>
<apache>
<applescript>
<autoconf>
<awk>
<bash>
<c>
<cpp>
<css>
<diff>
<drupal5>
<drupal6>
<gdb>
<html>
<html5>
<java>
<javascript>
<ldif>
<lua>
<make>
<mysql>
<perl>
<perl6>
<php>
<pgsql>
<proftpd>
<python>
<reg>
<spec>
<ruby>
<foo>
[foo]
둘 다 결과는 똑같은데 과정이 다릅니다.
둘 다 결과는 똑같은데 과정이 다릅니다.
다음 탐색할 노드를 선택할 때, 다익스트라는 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가 되죠.
댓글 달기