[AI] 1. Uninformed Search (DFS, BFS, UCS)

Search 알고리즘은 Planning agent 문제를 해결하기 위한 가장 기초적인 기술이다.

Planning agent를 이해하기 위해서는 Reflex agent를 이해할 필요가 있다.

Reflex agent는 주어진 입력에 의해 행동만 하는 것이다.

즉, 문제를 어떻게 효율적으로 해결하느냐, 해결한 후 상황 등은 궁금하지 않는다.

반면 Planning Agent는 Action을 효율적으로 계획하는 것이며, 현재 State를 파악하고, Cost를 최소화하기 위한 합리적인 의사결정을 하는 것을 의미한다.

Search problem을 풀기위해 정의되는 기본적인 Notation을 Packman game에 비유하면 아래와 같다.

 1) State space : Search 대상인 Game map

 2) State : 현재 User 의 X-Y Location

 3) Successor function : Action에 의한 Location을 update하고 Cost를 산출한다.

   - Action : N, S, E, W 방향으로 이동

 4) Goal test : 목적을 달성했는지를 파악한다.

또 다른 예제로 Bucharest로 가는 최단경로를 찾는 Traveling in Romania 문제의 경우 아래와 같이 표현할 수 있다.

 1) State space : Cities

 2) Successor function

   - Action : 다음 도시로 이동

   - Cost : 다음 도시까지의 거리

 3) Goal test : Is state == Bucharest?

이 중 State space를 Graph로 표현하느냐 Tree로 표현하느냐 에 따라 장단점이 있다.

먼저 Graph로 나타낼 경우, 각 Node는 현재 state, Arc는 Successor의 역할을 한다.

그리고 Goal node에 다다르는 경우를 따져 Goal test를 할 수 있다.

Graph를 State space로 사용할 경우 모든 경우를 Node에 할당하여 직관적으로 문제를 표현할 수 있는 장점이 있지만,

Full graph를 memory에 할당하기에는 비효율적이기 때문에, 필요한 노드만 memory에 저장해가면서 Search문제를 풀게된다.

반면 Tree로 나타낼 경우, Root node가 start state가 되며, Arc가 Action,  Child node는 Successor로 표현되는 점은 Graph와 비슷하지만, Cycle이 있는 graph는 Tree에서 표현하지 못한다. (아래로 무한히 가지가 쳐 짐)

그렇기 때문에 대부분의 문제에서 전체 Tree를 build하지 않는 등 단점이 있으나, Goal을 설정하는 것은 용이하다. (최소 깊이의 Tree 설계가 Goal이 된다.)

Uninformed Search

Search problem 중 현재 State에서 Goal state까지 가기 위해 필요한 Cost, Step을 모르는 상태에서 Goal state를 찾는 방법을 Uninformed Search라 하며 Blind Search라 부르기도 한다.

Uninformed Search에는 여러가지 알고리즘이 있지만, 아래 4가지 알고리즘이 대표적이다고 할 수 있다.

DFS (Depth-First Search)

DFS는 '깊이 우선 탐색' 이란 단어에서도 알 수 있듯, 탐색 우선 순위는 깊이 방향이다.

즉, 깊이 방향으로 탐색을 모두 마치고 나서 폭방향으로 이동하며, 폭방향 이동 후에 깊이 방향으로 탐색을 진행한다.

위 그림을 예로 들어 Implementation 해보자.

 - 탐색할 후보군이 저장된 변수를 Stack이라고 지칭하자.

 - 가장 처음에는 (s)가 탐색 후보이며, Pop을 통해 (s) 를 꺼낸다.

 - Pop 된 (s)와 연결된 노드를 Stack에 차례대로 저장한다. 

   (위 그림에서는 p, e, d 순으로 저장되었다고 가정한다.)

 - 가장 마지막에 저장된 (d)를 Pop하고, (d)에 저장된 b, d, e를 차례대로 Stack에 저장한다.

 - 가장 마지막에 저장된 (e)를 Pop하고, 위 과정을 반복한다.

 - 어느 순간 (C), (G)가 Stack에 저장되고, 가장 마지막에 들어온 (G)가 Pop 된다.

 - 그리고 더이상 아래로 내려갈 수 없는 상태에서 가장 마지막에 저장된 것은 

    (C)이기 때문에 (C)가 Pop된다.

이렇듯, 가장 마지막에 저장된 변수를 꺼내서 탐색을 진행하면 깊이 우선 탐색이 진행되며,

LIFO(Last In First Out) 성질을 갖는 Stack 구조를 사용하면 쉽게 구현할 수 있다.

BFS(Breadth-First Search)

BFS는 '너비 우선 탐색'이란 단어에서 알 수 있듯, 탐색 우선 순위 방향은 폭방향이다.

위 그림을 예로 들어 Implementation 해보자.

 - 탐색할 후보군이 들어있는 저장공간을 Queue라 지칭하자.

 - 가장 처음에는 (S)가 Queue에 저장되어 있으며 Pop 된다.

 - 이후 (d), (e), (p) 가 차례대로 저장된다.

 - DFS와는 다르게 가장 먼저 저장된 순서대로 Pop이 된다.

 - (d)가 Pop되고, (d)에 연결된 (b) (c) (e)가 Queue에 저장된다.

 - 남은 변수 중 가장 먼저 저장된 (e)가 Pop된 후 (h) (r)이 저장된다.

위 과정을 반복하면 s-d-e-p-b-c-e... 와 같이 폭방향으로 탐색을 시작함을 알 수 있다.

즉, 가장 먼저 저장된 변수를 꺼내서 탐색을 진행하며, FIFO (First In First Out) 특징을 갖는 Queue 구조를 사용하면 쉽게 구현할 수 있다.

DFS vs. BFS

2개의 Search 알고리즘을 언제 써야하는지는 Branching factor에 의해 좌우된다.

Branching factor는 1개 Parent node에서 나온 Child node의 수이며,

Branching factor가 크다는 것은 폭방향으로 Tree가 크다는 것이다.

이렇게 Branching factor가 큰 경우에는 DFS보다 BFS가 

Goal state를 찾는데 훨씬 효과적이다.

Iterative Deepening Search

Iterative Deepening은 DFS와 BFS의 장점을 모두 취하고자 하는 기법이다.

원리는 depth의 limit을 두고 그 깊이까지 DFS를 실행한다.

그리고 Goal state를 찾지 못하면 다시 depth limit를 설정하는데, 이렇게 Search를 하면 마치 BFS와 유사하게 동작하게 된다.

이렇게 Search를 했을 때 장점은, DFS를 실행하면 가장 아랫 node까지 내려가는데, 통상 가장 하위 node의 수는 상위 node수를 모두 합친 것에 육박하기 때문에 많은 시간을 소요하게 된다.

하지만 Iterative deepening은 단계별로 depth를 낮춰가며 DFS를 수행함으로써, 폭방향에 Goal state가 있을 경우 early stop 될 수 있다는 장점이 있다.

Uniform Cost Search

DFS와 BFS는 단순히 Goal state를 찾기 위한 알고리즘이었다면, UCS는 어떻게 해야 '효율적으로' Goal state에 도달할 수 있는지를 찾는 알고리즘이다.

(학술적으로는 Dijkstra 알고리즘으로 불리며, Dijkstra 알고리즘을 실용적으로 개선한 것이 UCS라 생각하면 된다. UCS = Dijkstra 알고리즘 + Start/Goal state setting)

즉, 각 Arc에는 Cost가 존재하며, (Action을 취할때 마다 Cost가 누적) 가장 적은 Cost를 소비하면서 Goal state에 도달하기 위한 Path를 찾는 알고리즘이다.

UCS의 원리는 생각보다 단순하다.

 - Next state가 저장된 저장소의 이름을 Priority Queue 라고 정의하자

 - Priority Queue에 저장되어있던 Start node가 Pop되며, 

   Pop된 Start node에 연결된 노드인 (d) (e) (p) 가 저장된다.

 - 이때 next state만 저장되는 것이 아니라 (d, 3) (e, 9) (p, 1) 와 같이 cost도 함께 저장된다.

 - 다음은 cost가 가장 낮은 (p, 1)이 Pop 되며, (p)에 연결된 (q)가 저장된다

 - (q)역시 cost와 함께 저장되는데, Start 부터 소요된 cost가 반영되어 (q, 16)이 저장된다.

 - 현재 Priority Queue에는 (d, 3) (e, 9) (q, 16)이 저장되어 있으며 가장 낮은 cost를 가진

   (d, 3)이 Pop되면서 (d)와 연결된 (b) (c) (e) 가 저장된다

 - 마찬가지로 Start state에서부터의 거리가 cost로 저장되면

   (e, 9) (q, 16) (b, 4) (c, 11) (e, 5)가 Priority Queue에 저장된다.

 - 다음에도 cost가 가장 낮은 (b, 4)가 pop되며, 이 과정을 반복하다 보면

   (Goal, cost)가 저장되면서 Search 알고리즘을 종료한다.

 - 여전히 Priority Queue에는 다른 state가 저장되어 있지만,

   cost가 가장 낮은 state를 Pop 하며 저장하였기 때문에, 현재까지 저장된 후보들은

   가장 처음 Goal까지의 cost보다 무조건 크기 때문에 고려할 필요가 없다.

위 동작 원리처럼 Implementation을 할때도, 내부에서 Pop우선순위가 있는 Priority Queue를 활용한다면 쉽게 구현할 수 있다.