Djkstra 알고리즘과 A* 알고리즘

 

1. 휴리스틱을 강조한 A* 알고리즘의 개요

가. A* 알고리즘의 정의

- 초기 상태에서 인접한 상태들을 조사해 나가면서 목표 상태에 이르는 가장 싼 비용을 휴리스틱 함수로써 경로를 찾는 알고리즘

나. A* 알고리즘의 특징

 

휴리스틱	정보와 시간이 불충분한 주어진 상황에서 신속하게 어림잡는 기술
Greedy	그 순간에 최적이라는 선택을 단계별 진행해서 최종적 해를 구하는 방식

 

2. A* 알고리즘의 평가함수

가. A* 알고리즘의 평가함수의 이해

 

1. n0를 open list에 입력 2. n1을 open->closed list에 넣음 3. nm이 목표 노드이면 n0 ~ nm을 추적하여 답을 얻고 끝냄 F(n) = g(n) + h(n)

 

나. A* 알고리즘의 평가함수 상세 설명

 

f(n) = g(n) + h(n) g(n):출발노드 ~ 현재노드n의 경로비용 h(n):현재노드n ~ 목표노드의 경로비용

- h(n)은 아직 탐색 하지 않은 경로 - 정확히 계산하기 어렵거나 불가능 - 경험적 규칙h^(n)을 사용하여 예측

 

3. A* 알고리즘의 예시

- g(n) : 현재 노드까지의 경로비용 / h(n)은 남은 노드의 개수로 가정

 

단계	노드	상세 설명
1단계	B선택	f(n) = 5
2단계	C선택	f(n) = 5+ C, F (2개) = 7 / 따라서, C를 선택해서 이동 (결과 : 비용은 10 추가됨) f(n) = 5+ E, C, F (3개) = 8 f(n) = 5+ D, E, C, F (4개) = 9
3단계	F선택 도착	f(n) = 15 + F(1개)  = 19의 비용으로 도착.

 

- 결과적으로 A->B->C->F 를 선택하여 19 비용으로 목적지 도착함.

- 최적해는 A->B->D->E->C->F 15비용이 최적의 해

- 좋은해를 빨리 구하지만, 항상 최적해가 아닐 수 있음. (검증이 필요함.)

 

 

 

 

 

 

다익스트라 알고리즘(Dijkstra algorithm)은 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘이다.

 

 

 

1. 개요

2. 알고리즘의 실질적 이용

3. 그림 설명

4. 알고리즘

4.0.1. 의사코드

 

 

1. 개요[편집]

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 

 

방향그래프,무방향 그래프 모두 상관없다.

 

당연히도 에츠허르 다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은 O(V^2)O(V

2

)의 시간복잡도를 가졌다. 이후 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나오며, O(ElogV)O(ElogV)의 시간복잡도를 가지게 되었다.

O(ElogV)O(ElogV) 의 시간복잡도를 가지는 이유는 힙에 최악의 경우 EE번의 탐색한 노드를 집어넣는 경우가 발생하게 되는데, 이러한 경우에 O(ElogE)O(ElogE)의 시간 복잡도가 나오며, 중복 간선을 허용하지 않는 그래프라면 O(E) <= O(V^2)O(E)<=O(V

2

) 이므로 O(log E) <= O(log V^2)O(logE)<=O(logV

2

)와 같다. 이때 O(log V^2) = O(2 \times logV)O(logV

2

)=O(2×logV) 이므로, 상수를 제거하면 O(ElogV)O(ElogV)가 된다. 물론 여기서 탐색에 소요되는 시간 O(V+E)O(V+E) 는 O(ElogV)O(ElogV)보다 작으므로 무시한다.

 

최단경로를 구하는 다른 알고리즘인 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리를 구하는 알고리즘인 반면, 다익스트라 알고리즘으로는 하나의 노드에서부터의 최단경로 밖에 구할 수 없다. 다만 시간은 플로이드 알고리즘이 더 오래걸리므로, 문제 상황에 따라 그때 그때 적합한 알고리즘을 사용하도록 하자.

 

다익스트라 알고리즘을 확장시킨 알고리즘이 A* 알고리즘이다.

2. 알고리즘의 실질적 이용[편집]

가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 고로 실질적 이용 예가 얼마나 많은지에 대해 더이상의 자세한 설명은 생략한다. 

 

예를 들어 루빅스 큐브를 푸는 프로그램을 다익스트라 알고리즘으로 만들 수 있고, 내비게이션에서 지도를 각 도시들을 노드로, 도로들을 간선으로 갖는 그래프로 간주한다면, 두 도시를 잇는 가장 빠른 길을 찾는 문제로 볼 수 있다. 미로탐색 알고리즘으로 사용할 수 있다. 라우팅에서도 OSPF 방식의 프로토콜의 경우가 좋은 예가 될 수 있다.

3. 그림 설명[편집]

예를 들어, 다음과 같은 네트워크가 존재한다고 가정하자. 먼저, A 라우터의 목표는 F까지의 최단 거리 계산이며, 수단으로는 다익스트라 알고리즘을 활용한다. 이때, 각 데이터의 의미는 다음과 같다.

• S = 방문한 노드들의 집합
• d[N] = A -> N까지 계산된 최단 거리
• Q = 방문하지 않은 노드들의 집합

 

1. 다익스트라 알고리즘은 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡는다.

 

 

 

초기화가 실행된 후의 그래프.

• 출발지를 A로 초기화했기 때문에, 출발지와 출발지의 거리는 방문할 필요도 없이 당연히 0 값을 가진다. 즉, d[A]=0이 된다. (A노드를 방문한 것은 아니다.)
• 출발지를 제외한 모든 노드들도 아직 방문하지 않았기에, d[다른 노드]=무한이 된다.
• Q는 방문하지 않은 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.
• S는 공집합 상태이다.

 

2. 루프를 돌려 이웃 노드를 방문하고 거리를 계산한다.

 

첫 루프를 마치고 난 뒤의 그래프.

• 루프의 시작은 거리가 최소인 노드(d[N]이 최소값인 노드 N)를 Q(방문하지 않은 노드의 집합)에서 제거하고, 그 노드를 S(방문한 노드의 집합 및 최소 경로)에 추가한다. 즉, N을 '방문한다'는 의미이다.
• 이후, 모든 이웃 노드와의 거리를 측정하여 d[N](=출발지로부터 N까지 계산된 최소 거리값) + (N과 이웃 노드 간의 거리값) = (출발지부터 이웃 노드까지의 거리값)이 계산된다.
• 다만, 지금은 첫 번째 루프만을 끝낸 상태이므로, 단순히 0 + (이웃 노드와 출발지 사이의 거리값) = (출발지와 이웃 노드 간의 거리값)이 각 이웃 노드에 기록된다. 따라서, d[B] = 10, d[C] = 30, d[D] =15로 값을 변경한다.

 

3. 첫 루프 이후의 그래프의 상태가 업데이트되는 방식

 

두 번째 루프를 마치고 난 뒤의 그래프.

 

이제 루프가 반복적으로 작동하는 방법을 설명한다. 밑의 그림들 또한 루프 안에서 알고리즘이 진행되는 순간들을 반복 설명한다.

• 이전에 설명했듯이, 방문할 노드는 Q에 남아있는 노드들 중 d[N] 값이 제일 작은 것으로 선택된다. 따라서, Q {B, C, D, E, F} 중 B가 d[B]=10으로 제일 작은 값을 가지므로, B를 방문하여 S에 추가하고 Q에서 제거한다.
• 이제, B의 이웃 노드들을 모두 탐색하여 거리를 재고 d[N]에 기록한다. B의 이웃 노드는 E 뿐이므로, d[E] 값이 무한에서 d[B]+(B와 E 사이의 값 = 20) = 30 으로 업데이트된다.[1] 여기서 d[B] 값을 추가하는 이유는 출발지부터의 거리값을 재기 위해서다.

 

4. 더 빠른 경로를 발견한 경우

 

• 3번째 그림에서 설명했듯이, 이번에 선택·방문되는 노드는 D이다. Q의 원소 중에서 제일 낮은 d[N] 값을 가지고 있기 때문이다. 그래서, S에 D가 추가되어 있다.
• 이제 D의 이웃 노드들(C, F)의 거리를 잰 후, d[N]값을 업데이트한다. 특별한 상황은 d[C]의 값이 A를 방문할 때 이미 계산되어 30으로 정해져 있었으나, D를 방문하여 C와의 거리를 확인해 보니 20으로 더 짧은 최단 경로가 발견되었다! 그러므로, d[C]의 값을 30에서 20으로 변경한다.
• d[F]의 경우는 원래의 값이 무한이므로, 더 작은 값인 15+20=35로 변경한다.

 

5. 또 다른 반복 루프 상황

 

• Q{C,E,F}에서 d[C]=20으로 C를 방문하여, S는 {A,B,D,C}가 되었다.
• 다시 이웃 노드와의 거리 계산을 해보니, 이번에는 (A→D)+(D→F)=15+20=35보다, (A→D)+(D→C)+(C→F)=15+5+5=25로 더 작은 값을 가지는 것이 발견되었다. d[F]=25로 업데이트한다. 아쉽게도 그림이 더 이상 존재하지 않아서, 더 이상의 자세한 설명은 생략한다.

 

이 일련의 과정이 반복되어 Q가 공집합이 되었다면, 남아 있는 데이터로 추론하여 최단 거리를 결정한다.

 

마지막 루프 이후,

• S = {A, B, D, C, F, E} (방문한 순서대로 정렬)
• d[A] = 0
• d[B] = 10
• d[C] = 20
• d[D] = 15
• d[E] = 30
• d[F] = 25
• Q = ∅

 

목적지가 F였으므로, A→D→C→F가 최단 경로이며, 거리는 25로 결정된다.

4. 알고리즘[편집]

다익스트라 알고리즘은 다음과 같다. P[A][B]는 A와 B 사이의 거리라고 하자.

1. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다.

   보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.[2][3]

2. 현재 노드 A에 출발 노드를 저장한다.
3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A]+P[A][B][4]와 d[B][5]의 값을 비교한다.
4. 만약 d[A]+P[A][B]가 더 짧다면, d[B]의 값을 이 값으로 갱신시킨다.
5. 모든 이웃 노드 B에 대해 이 작업을 수행한다.
6. A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.
7. "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.
8. 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

 

이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.

 

7번 단계에서, 거리가 가장 짧은 노드를 고르는 것은 공짜가 아니다. 모든 노드를 순회해야 하므로 시간복잡도에 결정적인 영향을 미치게 되는데, 이때 제대로 구현된[6] 우선순위 큐를 활용한다면 이 비용을 줄일 수 있다. 최단거리를 갱신할 때 우선순위 큐에도 <위치, 거리>의 쌍을 넣어주고, 거리가 가장 짧은 노드를 우선순위 큐를 이용해 고르면 된다. 이 비용은 삽입에 최대 O(lgN) 출력에 O(lgN)이므로, 모든 노드 순회(O(N))보다 저렴하다.

4.0.1. 의사코드[편집]

 

Graph는 모든 노드와 노드 간의 거리, 이웃노드에 관한 정보를 포함한다.

Source는 출발할 노드를 의미한다.

 

prev[(node)]는 출발지까지 가장 빠르게 갈 수 있다고 계산된 이웃 노드를 가리킨다. 즉, 출발지부터 목적지까지의 경로가 아니라, 목적지부터 출발지까지의 경로를 기록한다.

dist[(node)]는 출발지부터 현재 node까지의 cost 값을 의미한다.

 

 

function Dijkstra(Graph, Source):

dist[source] ← 0 // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0--

prev[source] ← undefined // 출발지 이전의 최적 경로 추적은 없으므로 Undefined

 

create vertex set Q //노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작

 

for each vertex v in Graph: // Graph안에 있는 모든 노드들의 초기화

if v ≠ source: // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!)

dist[v] ← INFINITY // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 ( 모든 노드들을 초기화하는 값)

prev[v] ← UNDEFINED // V노드의 최적경로 추적 초기화

add v to Q // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가

 

//요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.

while Q is not empty: // Q 집합이 공집합 아닐 경우, 루프 안으로!

u ← vertex in Q with min dist[u] // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작

remove u from Q // U 노드를 방문한 것이므로 Q집합에서 제거

for each neighbor v of u: // U의 이웃노드들과의 거리 측정

alt ← dist[u] + length(u, v) // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리

//= source to U + V to U = source to U

if alt < dist[v]: // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우

dist[v] ← alt // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈

prev[v] ← u // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈

 

return dist[], prev[] //계산된 거리값과 목적지를 리턴

 

 

[1] 30은 무한값보다 당연히 작으므로 업데이트가 되는 것이다.

[2] C++의 경우 std::numeric_limits::max, Python의 경우 타입에 따라 sys.maxint나 sys.float_info.max 등을 사용하면 안전한 값을 구할 수 있다. math.inf도 있다.

[3] 참고로 자주 사용되는 int의 경우 2,147,483,647이 양의 최대값으로, 이걸 16진수로 표현하게 되면 0x7FFFFFFF이다. F가 7개. 이걸로도 모자랄 것 같으면 64비트 정수 타입을 쓰거나 아예 실수 타입을 써야 한다.

[4] A를 거쳐서 B로 가는 최단 거리

[5] 현재까지 알려진 B까지의 최단 거리

[6] 우선순위 큐는 값을 받아 지정된 우선순위대로 내보낸다는 사양이 정의되어있을 뿐, 시간/공간 복잡도는 정의하지 않는다. 다만 제대로 구현된 경우 로그시간이 걸리는 것이 일반적.

 

 

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

다익스트라 알고리즘 - 나무위키