A*(A-star) 알고리즘은 그래프기반의 최단 경로 탐색 알고리즘입니다. 이 글은 그래프 및 그래프 탐색 알고리즘(DFS, BFS..)의 선행학습을 필요로 합니다.
Dijkstar Algorithm
A* 알고리즘은 Dijkstra 알고리즘과 유사한 점이 많습니다. 먼저 Dijkstar 알고리즘을 간단히 살펴보겠습니다.
function Dijkstra(Graph, source):
create vertex set Q
for each vertex v in Graph:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u: // only v that are still in Q
alt ← dist[u] + length(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]
위키피디아 Dijkstra’s algorithm pseudocode입니다. Breadth-first Search알고리즘과 비슷한 구조를 가지고 있음을 알 수 있습니다. 인접노드를 탐색하고 각 노드까지의 비용을 계산해서 최저 비용으로 갱신하는 방식으로 구현할 수 있습니다. 간단한 구현을 위해 인접 셀과 연결되어 있는 grid구조를 이용하겠습니다.
from collections import deque
import matplotlib.pyplot as plt
import matplotlib.patches as pts
import random
import numpy as np
GRIDSIZE = 50
grid = np.array([[0 for col in range(GRIDSIZE)] for row in range(GRIDSIZE)])
path = [[0 for col in range(GRIDSIZE)] for row in range(GRIDSIZE)]
# 비용의 초기값은 항상 계산된 cost보다 커야함
cost = np.array([[GRIDSIZE*GRIDSIZE for col in range(GRIDSIZE)] for row in range(GRIDSIZE)])
dx = [-1,0,0,1,-1,-1,1,1]
dy = [0,1,-1,0,-1,1,-1,1]
dCost = [1,1,1,1,1.414,1.414,1.414,1.414]
goal = [45,45]
plotStep = 10
plotcheck = 0
# 탐색 결과 plot
def plotPath(start,goal):
global path
node = goal
start = [0,0]
while node != start:
nextNode = path[node[0]][node[1]]
# print(node)
plt.plot([node[0],nextNode[0]],[node[1],nextNode[1]],color='r',linewidth=3)
node = nextNode
def dijkstra(start):
global grid, plotcheck,path,plotStep,fname
plt.scatter(goal[0],goal[1],marker='+')
Q = deque()
# 시작점에 대한 큐, cost initialize
Q.append(start)
cost[start[0]][start[1]] = 1
plt.scatter(start[0],start[1],color='r',s=1)
found = False
while not len(Q) == 0:
# 목표지점에 도달하거나 더이상 갈곳이
# 없을 경우 종료
if found:
break
# 큐에 저장된 node
current = Q.popleft()
# grid 기반이므로 인접 그리드 8개 탐색
for i in range(8):
next = [current[0]+dx[i],current[1]+dy[i]]
# grid 안의 셀이어야함
if next[0] >= 0 and next[1] >= 0 and next[0] < GRIDSIZE and next[1] < GRIDSIZE:
# obstacle check
if grid[next[0]][next[1]] == 0:
# cost가 더 낮은 경우 갱신
# A star구현시 이부분 수정
if cost[next[0]][next[1]] > cost[current[0]][current[1]] + dCost[i]:
# 갱신된 node를 큐에 넣고 계속 탐색
Q.append(next)
# 갱신되었을때 현재 셀을 path로 저장
path[next[0]][next[1]] = current
# 갱신
cost[next[0]][next[1]] = cost[current[0]][current[1]] + dCost[i]
# A star구현시 여기까지 수정
plt.scatter(next[0],next[1],color='r',s=1)
if next == goal:
found = True
if plotcheck > plotStep:
plotcheck = 0
plt.pause(0.1)
plotStep = plotStep + 1
plotcheck = plotcheck + 1
# random하게 장애물을 생성
def randomObstacle(num,max,min):
global grid
for i in range(num):
size = random.randrange(min,max)
startPointX = random.randrange(GRIDSIZE-size)
startPointY = random.randrange(GRIDSIZE-size)
for x in range(size):
for y in range(size):
grid[startPointX+x][startPointY+y] = 1
# visualize obstacles
rect = pts.Rectangle((startPointX,startPointY-1),size,size,facecolor='k')
plt.gca().add_patch(rect)
def main():
#visualize grid
plt.scatter([-1]*(GRIDSIZE+1),range((GRIDSIZE+1)),color='k',s=1)
plt.scatter([(GRIDSIZE+1)]*(GRIDSIZE+1),range((GRIDSIZE+1)),color='k',s=1)
plt.scatter(range((GRIDSIZE+1)),[-1]*(GRIDSIZE+1),color='k',s=1)
plt.scatter(range((GRIDSIZE+1)),[(GRIDSIZE+1)]*(GRIDSIZE+1),color='k',s=1)
randomObstacle(10,20,5)
dijkstra([0,0])
plotPath([0,0],goal)
print('end')
plt.show()
if __name__ == "__main__":
main()
위코드의 실행 결과는 다음과 같습니다.
A* algorithm
A star알고리즘은 cost를 계산하는 부분에서 차이가 있습니다.
def heuristics(node):
return sqrt((node[0] - goal[0])**2+(node[1] - goal[1])**2)
# dijkstra에 표시된 곳 내용 수정
deltaCost = dCost[i] + heuristics(next)
if cost[next[0]][next[1]] > cost[current[0]][current[1]] + deltaCost:
Q.append(next)
path[next[0]][next[1]] = current
cost[next[0]][next[1]] = cost[current[0]][current[1]] + deltaCost
위의 dijkstra 알고리즘을 A star알고리즘으로 구현했을때 차이가 있는 부분입니다.
heuristics 함수의 값이 cost에 추가 되어 계산 됩니다. heuristics는 간단히 어림 짐작한 cost라고 볼 수 있습니다. 지금 예제에서는 이 heuristics를 목표지점까지의 거리로 계산 했습니다. heuristics를 추가한 결과는 다음과 같습니다.
아래의 파란색 네모박스부분이 dijkstra algorithm과 다른것을 알 수 있습니다.
좀더 확실한 비교를 위해 장애물의 위치가 같을때를 살펴 보겠습니다. 위 그림이 A*, 아래그림이 dijkstra 의 결과입니다. Heuristic 함수를 목표 지점까지의 거리로 잡았기 때문에 그에 대한 결과를 확인 할 수 있습니다.
heuristic함수의 값이 오히려 좋지 않은 경로를 탐색할 수도 있습니다. A*의 성능은 heuristic함수가 얼마나 잘 설계되느냐로 성능이 결정된다 라고 볼 수 있겠습니다.
우선순위 큐로 구현
여기서 다음 탐색할 node를 넣는 queue를 cost에 대한 우선순위 큐로 구현한다면 시간복잡도가 감소합니다. python에서 제공되는 우선순위큐는 내부구조가 heap으로 구현되어있기 때문에 더 빠른 실행시간을 가지지만 이 예제에서는 큰차이로 나타나지는 않습니다.
구현 코드 펼쳐보기
from queue import PriorityQueue as PQ
import matplotlib.pyplot as plt
import matplotlib.patches as pts
import random
import numpy as np
GRIDSIZE = 50
grid = np.array([[0 for col in range(GRIDSIZE)] for row in range(GRIDSIZE)])
path = [[0 for col in range(GRIDSIZE)] for row in range(GRIDSIZE)]
# 비용의 초기값은 항상 계산된 cost보다 커야함
cost = np.array([[GRIDSIZE*GRIDSIZE for col in range(GRIDSIZE)] for row in range(GRIDSIZE)])
dx = [-1,0,0,1,-1,-1,1,1]
dy = [0,1,-1,0,-1,1,-1,1]
dCost = [1,1,1,1,1.414,1.414,1.414,1.414]
goal = [45,45]
plotStep = 10
plotcheck = 0
# 탐색 결과 plot
def plotPath(start,goal):
global path
node = goal
start = [0,0]
while node != start:
nextNode = path[node[0]][node[1]]
# print(node)
plt.plot([node[0],nextNode[0]],[node[1],nextNode[1]],color='r',linewidth=3)
node = nextNode
def dijkstra(start):
global grid, plotcheck,path,plotStep,fname
plt.scatter(goal[0],goal[1],marker='+')
Q = PQ()
Q.put((1,start))
cost[start[0]][start[1]] = 1
plt.scatter(start[0],start[1],color='r',s=1)
found = False
while not Q.empty():
if found:
break
current = Q.get()[1]
for i in range(8):
next = [current[0]+dx[i],current[1]+dy[i]]
if next[0] >= 0 and next[1] >= 0 and next[0] < GRIDSIZE and next[1] < GRIDSIZE:
if grid[next[0]][next[1]] == 0:
if cost[next[0]][next[1]] > cost[current[0]][current[1]] + dCost[i]:
path[next[0]][next[1]] = current
cost[next[0]][next[1]] = cost[current[0]][current[1]] + dCost[i]
Q.put((cost[next[0]][next[1]],next))
plt.scatter(next[0],next[1],color='r',s=1)
if next == goal:
found = True
if plotcheck > plotStep:
plotcheck = 0
plt.pause(0.0001)
plotStep = plotStep + 1
plotcheck = plotcheck + 1
def randomObstacle(num,max,min):
global grid
for i in range(num):
size = random.randrange(min,max)
startPointX = random.randrange(GRIDSIZE-size)
startPointY = random.randrange(GRIDSIZE-size)
for x in range(size):
for y in range(size):
grid[startPointX+x][startPointY+y] = 1
# visualize obstacles
rect = pts.Rectangle((startPointX,startPointY-1),size,size,facecolor='k')
plt.gca().add_patch(rect)
def main():
#visualize grid
plt.scatter([-1]*(GRIDSIZE+1),range((GRIDSIZE+1)),color='k',s=1)
plt.scatter([(GRIDSIZE+1)]*(GRIDSIZE+1),range((GRIDSIZE+1)),color='k',s=1)
plt.scatter(range((GRIDSIZE+1)),[-1]*(GRIDSIZE+1),color='k',s=1)
plt.scatter(range((GRIDSIZE+1)),[(GRIDSIZE+1)]*(GRIDSIZE+1),color='k',s=1)
randomObstacle(10,20,5)
dijkstra([0,0])
plotPath([0,0],goal)
print('end')
plt.show()
if __name__ == "__main__":
main()
결론
Dijkstra부터 A star까지 간단하게 살펴보았습니다. 이 두 알고리즘의 단점은 Map이 클 경우 (Graph가 복잡한 경우)에 메모리소모가 크다라는 점이 있겠고, 특히 A star의 경우 heuristic 함수의 의존도가 크다 라는 점을 들 수 있겠습니다.
참고문서
- Wikipedia contributors, “Dijkstra’s algorithm,” Wikipedia, The Free Encyclopedia,
- Hart et al. “A formal basis for the heuristic determination of minimum cost paths.” (1968)
- A.M. Turing Award. - Richards, Hamilton. “Edsger Wybe Dijkstra”
- Wikipedia contributors, “A* search algorithm,” Wikipedia, The Free Encyclopedia,
