인공지능의 기초 - 문제 해결 과 탐색 전략

문제 해결 ( Problem Solving )

대표적으로 루마니아 문제

비행기를 타기위해 Arad에서 공항이있는 Bucharest로 가는 가장 최적의 경로 구하기.

문제 해결을 위한 핵심 2가지 요소

State : Agent의 상태

예제에서는 경유지.

Action : Agent가 어떤 상태에서 어떤 상태로 이동하기 위한 행동.

예제에선 경유지간 이동하는 행위.

좀더 세밀한 4가지 요소

Initial State : 초기 상태를 정의. 

Arad

Possible actions : 가능한 Action들을 정의. Successor function, f(state) = {(action, successor state), ...} 를 정의. (action, successor) 쌍으로 만드는 이유 : 문제에 따라 서로 다른 action이 같은 state와 successor state를 가질수도 있다.

S(Arad) = {(Arad->Zerind, Zerind), (Arad->Timisoara, Timisoara), (Arad->Sibiu, Sibiu)}

Goal test : 목표(Goal State)를 정의하고 각 State별로 Goal State임을 검사하는 방법을 정의

Goal state : Bucharest, Goal test : state = Bucharest

채스처럼 Goal State가 많은 경우. 조건함수를 사용해 implicit하게 정의. Goal test : Checkmate(state)

Path cost : 어떤 path를 통틀어 각 action이 발생시키는 cost(Step cost)를 더한 값. 

각 action별로 0이상의 Step cost, Sc(state, action, successor state)>=0 를 정의

사실상 Sc(action.state, action, action.successor) 즉 ,Sc(action)과 같다.

이때 음수의 cost를 정의하면 루프를 돌면서 cost를 무한으로 낮추는등의 여러가지 변수를 고려해야하는 등 문제해결이 복잡해진다.

소모 시간, 연료비, 운임비

결국 인공지능에서의 해 (Solution)는 Initial State에서 Goal test에 도달하는 Action(또는 State)들의 Sequence. path cost의 합이가장 적은 해가 최적의 해(Optimal Solution)가된다.

추상화(Abstraction)

주어진 문제상황에서 문제해결과 관련없는 복잡성을 배제하고 문제해결의 4가지 요소으로 단순화 하여 해결 가능하게 하는것

탐색 전략 (Search Strategies)

Tree Search Algorithms

경로 탐색을 위해 사용하는 가장 기본적인 알고리즘.

Initial State를 루트로하고 action을 에지로 가지는 트리 자료구조를 통해 goal state로 가는 해(path)를 찾는다.

4가지 전략 평가 기준

completeness : 반드시 해를 찾을수 있는가?

Time complexity : 해를 찾기까지 몇개의 노드들이 만들어지는가?

Space complexity : 동시에 최대 몇개의 노드를 메모리에 저장하는가?

Optimality : 반드시 가장 최적의 해를 찾는가?

Uninformed Search

문제 정의로 주어진 4가지 정보만을 활용.

Breadth-firth search (너비 우선 탐색)

- Uniform-cost search

Depth-first search (깊이 우선 탐색)

- Depth-limited search

- Iterative deepening search

Breadth-First Search

FIFO queue를 Fringe 로 사용.

Fringe: 트리에 생성은 되었으나 아직 방문(=확장 expand 이라고도 표현) 하지 않은 노드의 집합.

시작 : initial state를 root node로 생성하고 fringe queue에 저장.

반복 : fringe queue에서 FIFO 방식으로 expand를 수행

-> goal state가 맞으면 종료, 아니면 successor state들을 생성해서 fringe queue에 넣는다

Depth-first search

LIFO Queue를 Fringe로 사용.

시작 : initial state를 root node로 생성하고 fringe queue에 저장.

반복 : fringe queue에서 LIFO 방식으로 expand를 수행

-> goal state가 맞으면 종료, 아니면 successor state들을 생성해서 fringe queue에 넣는다.

BFS vs DFS의 전략적 평가

Completeness : Yes vs No

Time complexity : O(b^(d+1)) vs O(b^m)

Space : O(b^(d+1)) vs O(bm)

Optimality : Yes vs No

b : 최대 브랜치(에지) 수. 최대 자식 노드 수(b>1)

d : 가장 얕은 goal node의 깊이(루트 노드로 가는 에지 수)

m : 트리의 높이

시간, 공간복잡도의 증명

BFS 는 goal state를 찾는 순간 탐색 알고리즘이 끝난다. 

-> 찾는 순간에 해당 레벨의 선 확장 노드들의 자식노드들까지는 만들어진다

-> 노드가 최악의 경우 b^(d+1)+b^d+...+b^2+b^1+b^0-b

=(b^(d+2)-1)/(b-1)-b<(b^(d+2))/(b-1)=(b^(d+2)/b)*(b/b-1)<=2*(b^(d+1)) 개 만들어진다

-> 고로 시간복잡도는 O(b^(d+1))

-> 찾는 순간까지 만든 노드들을 계속 메모리에 유지하고 있어야 역방향으로 path를 구성할수 있다.

-> 공간 복잡도도 마찬가지로 O(b^(d+1))이다.

DFS 는 높은 확률로 중간에 goal state를 못 찾고 트리의 말단 노드에 도달한다.

각 레벨별로 해당 레벨에서의 Goal을 피하는 확률을 곱한만큼의 확률, 임의의 레벨에서 다른 노드보다 Goal node가 많은 특수한 경우는 거의없다.

->최악의 경우는 모든 노드가 d개의 애지를 가지고 Goal이 없는 길만 골라서 가능한 모든 말단(깊이 m)까지 도달하고 나서 깊이 (d~m)에 있는 가장 깊은 goal을 찾아내는 경우)

->그러면 확장 안한 노드는 깊은 곳부터 봐야하므로 무조건 가장 깊은 위치에 있는 goal을 먼저 찾을수 있다.

->n개의 goal의 깊이를 {d1,d2,d3,dn...>=d}라 한다면

최대 (b^m+b^(m-1)+...+b+b^0)-(b^(m-d1)+...+B^0-1)-...-(b^(m-dn)+...+b^0-1)

= (b^(m+1)-1)/(b-1)-(b^(m-d1+1))/(b-1)-...-(b^(m-dn+1))/(b-1)+n

< (b^(m+1)-1)/(b-1) < (b^(m+1)/b)*(b/(b-1)) < b^m*(b/(b-1))

< 2*b^m

->따라서 시간복잡도는 O(b^m)

->어떤 노드로 부터 말단노드까지의 path에 goal이 없는것을 알아낸다면 해당 path는 필요없어지므로 지우게 된다.

-> 따라서 최악의 경우 b*m+1개의 노드를 메모리에 유지하고 있게 된다.

->고로 공간 복잡도는 O(b*m)

DFS는 왜 completeness를 보장 못할까?

m이 무한히 큰 문제에서는 영원히 말단노드를 찾아 해매느라 해를 못찾게 되는 경우가 생긴다.  방향 그래프상 싸이클이 존재하는 경우, 무한한 state를 가지고 있는 경우

Optimality에서의 차이는 왜 나는 걸까?

BFS는 무조건 최소 깊이의 해를 먼저 구하게 된다. 이는 간선 갯수를 path cost로 정의했을때의 최적의 해가 된다. 반면 DFS는 어느 해를 먼저 구하게 될지 모른다. 애초에 DFS는completeness도 보장 못한다.