Dijkstra, A*, weighted A* 구현 및 비교

0. 개요

Dijkstra와 A* 알고리즘으로 각각 optimal한 경로를 얻고 결과를 비교 분석한다. 결과를 쉽게 비교하기 위해서 matplot 라이버리로 시각화를 진행할 필요가 있다. 이 공부의 개요는 다음과 같이 4개의 파트로 구성했다.

 

1. Map 만들기

2. Dijkstra 알고리즘 구현

3. A* 알고리즘 구현

4. 두 알고리즘 결과 비교

 

알고리즘의 비교를 위해 cost와 방문한 노드 수를 추가적으로 비교한다.

 

1. Map 만들기

1) matplotlib의 pcolor 사용

import matplotlib.pyplot as plt
from matplotlib import colors

data = [[1,1,1,1,1,1,1,1,1,1],
        [1,1,1,1,1,1,1,1,1,1],
        [1,1,1,1,1,1,1,1,1,1],
        [1,1,1,1,1,1,0,0,1,1],
        [0,1,1,1,1,0,0,0,0,1],
        [0,0,1,1,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0]]

cmap = colors.ListedColormap(['Blue', 'red'])
plt.figure(figsize=(6,6))
plt.pcolor(data[::-1], cmap=cmap, edgecolors='k', linewidths=3)
plt.show()

colors.ListedColormap의 인자로 색상(['Blue', 'red'])을 넘겨주면 해당 plt.pcolor의 data의 값에 맞춰 색이 변한다.

ex) 0 : Blue, 1 : red

 

2) 이를 이용해 Map을 형성한다.

 

2. Dijkstra 알고리즘 구현

start state를 중심으로 원형 search를 진행하다가 goal state를 만나면 최소 cost의 경로를 return

Map Data와 start, goal state를 입력으로 path를 얻을 수 있다.

*state는 좌표 (코드에서는 index)

자세한 설명은 http://www.gisdeveloper.co.kr/?p=3881 참고.

 

1) 코드

  ① 변수 초기화 및 시작노드 삽입

(main loop)

  ② 현재 노드(cur_node) 선택 - cost가 낮은 노드

  ③ 종료조건 확인 - cur_node 좌표와 goal_node 좌표가 같은지

    ----> True면 Optimal한 path return 하면서 종료

    ----> False면 현재 노드를 이미 방문한 노드로 기록

(이동 loop)

  ④ 이동한 노드(child_node) 유효성 확인 - 벽인지 확인, 이미 방문한 노드인지 확인

    ----> True면 해당 노드 소멸 - 벽이거나 이미 방문했기 때문에

    ----> False면 cost 갱신하면서 방문 할 노드에 기록

 

2) 결과

 

3. A* 알고리즘 구현

Dijkstra가 그저 원형으로 search 한다면 A*는 휴리스틱 추정값(goal state와의 거리)을 고려해 search 한다.

위 그림을 보면 원형으로 탐색한 Dijkstra에 비해 타원형의 search를 볼 수 있다. 이는 goal state와의 유클리안 거리(두 점 사이의 최소거리)를 고려했기 때문에 goal과 가까운 방향으로 우선 탐색하는 것.

 

1) 코드

Dijkstra와 거의 동일하며 위 코드의 ④ 중 cost 갱신부분을 추가한다.

cost = (start state와의 거리) + (goal state와의 거리) 로 갱신한다.

* (start state와의 거리) 는 Dijkstra의 cost 갱신과 동일

* (goal state와의 거리) 는 heuristic cost로 추가된 것

 

2) 결과

4. 두 알고리즘 결과 비교

위 그림은 Dijkstra(왼쪽)와 A*(오른쪽) 알고리즘의 결과이다. 해당 Map에서 cost의 변화는 없지만 방문한 노드 수가 감소한 것을 볼 수 있다. 수치로는 3254 -> 2615로 639(약 20%) 감소했다. 이는 그저 원형으로 serach 하는 것이 아닌 heuristic을 고려해 search하여 방문한 노드 수를 줄일 수 있었다. 방문한 노드 수가 감소한 만큼 계산량도 그만큼 적어졌다는 것으로 볼 수 있다.

 

5. 추가사항(weighted A*)

다음은 weighted A*를 확인하겠다. weighted A*는 A*와 다르게 그대로 heuristic cost(goal state와의 거리)를 갱신하는 것이 아닌 heuristic cost에 가중치(w)를 곱해서 갱신한다. 이는 heuristic cost에 비중을 얼만큼 줄 것인가라는 의미이고 가중치가 크면 heuristic cost의 비중이 높아져 goal state에 더 빠르게 가려고 할 것이고, 낮으면 그와 반대의 영향을 줄 것이다. 아래의 그래프는 하나의 예시이다.

weighted A*의 방문한 노드는 기존 A*보다 감소하였지만 cost는 더 증가한 결과를 보인다. 이는 기존 A*와는 다르게 weighted A*가 goal state로 가려는 경향이 더 크기 때문으로 생각된다. 그래서 처음에 벽이 있는지 모른 채 goal state로 향하는 모습을 보이고 가운데 세로벽을 지났을 때도 동일하게 goal state로 가려다가 두번째 가로벽에 막히는 모습을 볼 수 있다.