지난 포스팅에서는 탐색 알고리즘의 기본이 되는 Depth-First Search, Breadth-First Search 에 대해 알아봤습니다. 그리고 글 마무리에 Uniform Cost Search에 대해서도 간단히 알아봤는데요. 상세 내용은 아래 링크 참조하시면 됩니다.
https://dev-cock.tistory.com/17
이번 포스팅에서는 Python 코드를 통해 각각의 Search를 어떻게 구성하는 지에 대해 알아보겠습니다.
Breadth First Search
먼저 너비우선탐색에 대한 파이썬 코드입니다.
def bfs(graph, start, goal):
reached = []
frontier = []
frontier.append(start)
parents = {}
notFound = True
while(frontier and notFound):
item = frontier.pop(0)
if item not in reached:
reached.append(item)
for items in graph[item]:
if items not in reached and items not in frontier:
if items == goal:
reached(item)
notFound = False
parents[items] = item
break
frontier.append(items)
parents[items] = item
temp = goal
answer = [goal]
while (True):
answer.append(parent[temp])
if parents[temp] == start:
break
temp = parents[temp]
answer.reverse()
return answerBFS는 우선순위가 없고, 그저 모든 노드의 child를 프론티어에 넣고 순서대로 탐색하는 방식이기 때문에 별도의 우선순위 큐를 구현할 필요는 없습니다. 다만 일반적인 큐의 형태로 FIFO 자료형을 사용해야 편리하며, 파이썬 리스트의 append와 pop을 사용했습니다.
- 탐색을 시작할 노드가 frontier에 저장되며, while loop 가 시작됩니다. 목적 노드를 찾기 전까지 계속 반복합니다.
- 해당 노드가 아직 탐색하지 않은 노드라면, reached에 저장하고 child를 탐색합니다.
- child 노드에 대해, 탐색하지 않은 노드이면서, frontierd도 없다면 완전히 미개척지이므로 frontier에 저장합니다.
- 만약 해당 child노드가 목적 노드라면, 정답을 찾았으므로 루프를 break 합니다.
위 코드에서 parents 딕셔너리는 경로를 찾기 위해 사용됩니다. 즉, 예를 들어 로마니아의 맵 예제를 다시 가져와보겠습니다.
Arad - Sibiu - Rimnicu Vilcea - Pitesti - Bucharest 까지 가는 경로를 찾았다고 한다면, 이 경로를 어떻게 기억할까요?
저는 parent-child 간 연결 노드를 딕셔너리 타입으로 저장했습니다. 즉, parent[child] = parent가 되는 구조로 말입니다.
탐색을 이어가다가 bucharest에 도달하게 되면, 모든 노드를 잇는 정보가 딕셔너리에 담기게 됩니다. 마치 C++에 있는 어레이 리스트 자료구조처럼요.
파이썬 코드에 있는 두번째 while_loop가 경로를 찾습니다. 딕셔너리를 역으로 추산해가면서 목적노드부터 출발노드까지를 반환하는 방식입니다. 결과적으로 얻은 리스트를 reverse해주면, 출발노드부터 목적노드까지 거쳐간 노드들의 리스트가 반환됩니다.
Uniform Cost Search
UCS는 노드 간 최단거리를 우선순위 큐에 반영합니다. 즉, 단순히 노드의 자식이라고 해서 frontier에 반영하고, pop하는 일반적인 BFS와 달리 현재 노드까지 오면서 계산된 거리의 총합을 기준으로 삼습니다.
def ucs(graph, start, goal):
visited = []
frontier = PriorityQueue()
frontier.append((0, start))
frontier_name = []
frontier_name.append(start)
frontier_weight = {}
frontier_weight[start] = 0
parent = {}
cost = 100000
while (frontier.size() != 0):
item = frontier.pop()
frontier_name.remove(item[1])
if item[1] not in visited and frontier_weight[item[1]] < cost:
visited.append(item[1])
tempGraph = graph[item[1]]
if goal in nextList:
cost = min(cost, graph.weight(goal, item[1]) + item[0])
if cost == graph.weight(goal, item[1]) + item[0]:
parent[goal] = item[1]
frontier.append((graph.weight(goal, item[1]) + item[0], goal))
frontier_weight[goal] = (graph.weight(goal, item[1]) + item[0])
frontier_name.append(goal)
else:
for items in nextList:
if items not in visited:
if items in frontier_name:
# already exist in frontier. then compare weight and update if necessary (remove->append)
if frontier_weight[items] > (graph.weight(items, item[1]) + item[0]):
frontier.remove((frontier_weight[items], items)) # delete it!
frontier_weight[items] = graph.weight(items, item[1]) + item[0]
frontier.append((frontier_weight[items], items))
parent[items] = item[1]
else: # not in frontier. then see if frontier_hoobo cost is greater than current one.
frontier.append((graph.weight(items, item[1]) + item[0], items))
frontier_weight[items] = (graph.weight(items, item[1]) + item[0])
frontier_name.append(items)
parent[items] = item[1]
temp = goal
answer = [goal]
while (True):
answer.append(parent[temp])
if parent[temp] == start:
break
temp = parent[temp]
answer.reverse()
return answer코드가 갑자기 확 길어져서 복잡한 느낌이 들지만 하나씩 설명해보겠습니다.
- BFS처럼 시작은 하지만, 이번에는 priorityQueue를 사용합니다. 즉, 노드마다 어떤 값이 있어서 그 값이 낮은 순서대로 pop하게 되는 구조입니다. 이 문제에서 기준치는 노드까지 오는데 소요된 거리가 되겠습니다. 최단거리를 찾는 것이 목적이니까요.
- cost는 목적 노드에 도달했을 때 거리를 저장합니다. 처음 시작때는 도달하지 못했으므로 임의로 큰 값으로 초기화를 진행했고, while loop을 돌면서 cost보다 큰 노드의 거리 값이 pop 되는지를 비교합니다. 사실 위 코드에는 넣지 않았지만, pop되는 원소의 거리합계가 cost보다 클 경우 더 이상 루프를 진행할 이유가 없습니다. 노드가 깊어질수록 거리는 길어지기 때문입니다.
- BFS와 유사하지만, frontier에 child 노드를 추가하기에 앞서 기준이 되는 거리값을 비교합니다. 거리가 짧은 노드가 발견되었을 경우, 기존에 frontier에 있던 동일한 노드(이면서 거리는 길었던)를 업데이트합니다. 만약 거리가 더 긴 노드라면, 어차피 돌아가는 경로일 뿐이므로 업데이트하지 않고 지나갑니다.
- 만약 frontier에 없는 노드라면, frontier에 추가합니다.
- graph.weight(node1, node2) : 두 노드 간 거리를 반환하는 인자입니다.
- parent 딕셔너리는 여기서도 BFS와 동일하게 사용됩니다. 최단거리를 가지는 경로를 반환하는데 사용됩니다.
UCS의 단점은 목적 노드가 어디에 있는지, 그 정보가 path finding에 전혀 도움이 되지 않는다는 점입니다. 오로지 노드 간 거리의 총합이라는 정보만으로 길을 찾아나서기 때문입니다.
지도에서 경로찾기를 예로 들면, UCS는 아래 두 지점 사이를 탐색할 때 지도의 거의 전체를 다 탐색하는 것을 알 수 있습니다. 매우 비효율적이죠.
그래서 Bi directional UCS를 사용해볼 수도 있습니다. 위의 방법은 출발 -> 도착 이라는 일방향적인 탐색만 했다면, bi search는 출발->도착, 도착->출발 양 방향에서 모두 탐색을 하는 것입니다.
그러다 두 탐색 경로 간 접점이 생기면, 그 지점을 기준으로 최단거리를 찾는 알고리즘입니다. 탐색하는 노드의 수를 획기적으로 줄일 수 있게 됩니다. (코드는 따로 첨부하지 않겠습니다.)
그림에서와 같이 회색으로 표시된 영역은 탐색하지 않고도 최단거리를 찾을 수 있게 됩니다. 이런식으로 tri directional search도 할 수 있습니다. 중간 지점에 하나 더 둠으로써 또 최접점을 찾는 식입니다. 탐색하는 노드의 수는 줄어들겠지만, 어쨌거나 궁극적인 목적 노드에 대한 정보가 없어서 한계가 있습니다.
목적노드와의 현재 탐색중인 노드 간의 관계를 이용해서 최적화하는 탐색 방법이 있습니다. 바로 A Star Search 입니다.
A Star Search
A Star Search는 UCS에 추가로 Heuristic funtion을 사용한다는 차이점이 있습니다. 여러가지 heuristic function이 있겠지만, 대표적으로 목적 노드와 현재 탐색중인 노드 간의 거리가 있겠습니다. 즉, 어쨌거나 출발/목적 노드의 위도 경도 정보는 지도 상에서 제공되어 있으니, 현재 탐색중인 노드가 얼마나 떨어져있는지에 대한 정보를 우선순위 큐에 반영하는 것입니다.
다시말해, UCS에서는 탐색 중인 노드까지 오는데 소요되는 거리의 총 합만을 사용했다면, 이제는 총 합 + 목적노드까지의 거리를 반영하는 셈입니다.
- f(v) : 우선순위 큐에 반영되는 값
- g(v) : ucs에서 사용하는, 탐색중인 노드까지의 총 Path cost
- h(v) : 특정 노드~목적 노드 사이의 거리 (heuristic)
이와 같이 반영하여 A-star alrogithm을 작성해봤습니다.
def astar_Algorithm(graph, start, goal, heuristic):
visited = []
frontier = PriorityQueue()
frontier.append((0, start))
frontier_name = []
frontier_name.append(start)
frontier_weight = {}
frontier_weight[start] = 0 + heuristic(graph, start, goal)
path_weight = {}
path_weight[start] = 0
parent = {}
cost = 10000
if start == goal:
return []
while (frontier.size() != 0):
item = frontier.pop()
frontier_name.remove(item[1])
# compare goal cost with item priority!! if it is bigger than goal cost, we don't have to visit. Just pop it up.
if item[1] not in visited and item[0] < cost:
visited.append(item[1])
tempGraph = graph[item[1]]
if goal in nextList:
cost = min(cost, graph.weight(goal, item[1]) + path_weight[item[1]])
if cost == graph.weight(goal, item[1]) + path_weight[item[1]]:
# found cheapest path!
parent[goal] = item[1]
else:
for items in nextList:
# items: 'a', 'b', ...
if items not in visited:
if items in frontier_name:
# already exist in frontier. then compare weight and update if necessary (remove->append)
if frontier_weight[items] > (
graph.weight(items, item[1]) + path_weight[item[1]] + heuristic(graph, items, goal)):
frontier.remove((frontier_weight[items], items)) # delete it!
frontier_weight[items] = (
graph.weight(items, item[1]) + path_weight[item[1]] + heuristic(graph, items, goal))
frontier.append(
(frontier_weight[items], items))
parent[items] = item[1]
path_weight[items] = path_weight[item[1]] + graph.weight(items, item[1])
else: # not in frontier. if distance is smaller than current node, add it!
frontier.append((graph.weight(items, item[1]) + path_weight[item[1]] + heuristic(graph, items, goal), items))
frontier_weight[items] = (graph.weight(items, item[1]) + path_weight[item[1]] + heuristic(graph, items, goal))
frontier_name.append(items)
path_weight[items] = path_weight[item[1]] + graph.weight(items, item[1])
parent[items] = item[1]
temp = goal
answer = [goal]
while (True):
answer.append(parent[temp])
if parent[temp] == start:
break
temp = parent[temp]
answer.reverse()
return answerUCS와의 차이점만 보자면 다음과 같습니다.
- UCS는 노드 간 거리의 총합을 기준으로 frontier를 업데이트 했습니다만, a star는 노드 간 거리의 총합 + heuristic 거리를 기준으로 업데이트합니다.
- UCS 코드와 마찬가지로, 만약 frontier에서 pop한 원소의 cost가 현재 저장된 cost보다 클 경우 while loop을 돌 이유가 없습니다. break해서 나오면 되는데 위 코드에는 반영되어 있지 않습니다.
A-star 의 경우 탐색하는 노드의 수가 UCS 보다 줄어들게 됩니다. 아무래도 목적 노드에 가까운 노드일수록 cost가 낮아지게 되니, 가까운 노드들부터 계속 탐색을 지속하기 때문입니다. 여기서도 Bi-directional, Tri-directional search algorithm을 적용해볼 수 있습니다만, ucs보다 조금 더 까다롭습니다. heuristic function을 어떻게 적용해야되는지가 애매해지기 때문인데요. 이부분은 추후 시간이 나면 다시 다뤄보도록 하겠습니다.
긴 글 읽어주셔서 감사합니다.
'Artificial Intelligence' 카테고리의 다른 글
| 탐색 알고리즘 - 깊이우선탐색, 너비우선탐색 기본개념 (0) | 2022.02.15 |
|---|---|
| PID Control 개념 정리 / 파라미터 튜닝 방법 (Twiddle) (0) | 2022.02.14 |
| [Localization] 칼만 필터 Kalman Filter (0) | 2022.02.14 |
| [Localization] Particle Filter 파티클 필터 (0) | 2022.02.14 |