#2 문제해결 및 탐색 전략

추상화

추상화란 문제를 단순화시켜 불필요한 부분을 제거하고

핵심 요소와 개념 또는 기능을 간추려 일반화된 모델을 만드는 과정이다.

실제 세계의 문제는 매우 복잡하기 때문에 인공지능에서 문제를 풀기 위해 단순화 과정이 필요한 것이다.

 

탐색 전략 선택의 4가지 기준

 - 완전성 : 해가 있다면 반드시 찾을 수 있는가?

 - 시간 복잡도 : 얼마만큼 노드를 확장해야 목표상태에 도달할 수 있는가?

 - 공간 복잡도 : 메모리 공간에 저장할 수 있는 최대 노드의 개수는 몇 개인가?

 - 최적성 : 가장 적은 비용이 드는 최적의 해를 찾을 수 있는가?

 

BFS vs DFS

	BFS	DFS
완전성	Yes	No
시간 복잡도	O(b^(d+1))	O(b^m)
공간 복잡도	O(b^(d+1))	O(bm)
최적성	Yes	No

BFS는 완전성과 최적성을 만족하지만 시간, 공간 복잡도가 DFS보다 더 크다.

( b : 한 노드에서 펼쳐질 수 있는 최대의 숫자,

  d : 목표상태가 있는 깊이,

  m : 검색하게될 깊이 )

 

반복적 깊이심화탐색(IDS)

DFS와 BFS의 장점을 합친 방법이다.

깊이 한계를 0에서 점차 1씩 증가시켜가면서 DFS로 탐색하는 방법이다.

최단 경로 해를 보장하고 메모리 공간 사용이 효율적이다.

 

양방향탐색

BFS의 경우 탐색 범위가 넓어지면 생성해야하는 노드의 개수가 크게 증가할 수 있다.

이러한 문제를 해결하기 위해 초기상태와 목표상태를 기준으로 번갈아 가면서

BFS를 진행하는 양방향 탐색을 수행하는 것이다.

(중간지점에서 만나도록 하여 최적의 해를 찾는 방법)

BFS의 장점을 취하면서 적은 노드의 수를 사용하여 시간 및 공간복잡도가 BFS보다 우수하다.

 

 

 

최선우선탐색(Best-First Search)

확장 중인 노드들 중에서 목표 노드까지 남은거리가 가장 짧은 노드를 확장하여 탐색하는 방법이다.

이는 휴리스틱(평가함수)를 이용한다.

휴리스틱은 현재 노드 n에서 목표 노드 까지의 가장 저렴한 경로의 예상비용을 뜻한다.

 

A-star 알고리즘

추정한 휴리스틱(평가함수) f(n)의 값이 최소인 노드를 확장해 가는 방법이다.

 f(n) = g(n) + h(n)

g(n) : 시작 노드에서 현재 노드 n 까지의 비용

h(n) : 현재 노드 n에서 목표 노드까지의 비용

f(n) : 노드 n을 경유하여 목표 노드까지 도달하는데 드는 전체 비용

목표 노드를 발견해도, 더 좋은 솔루션이 있는지 다시 탐색한다. DFS,BFS와의 차이점이다.

 

A-star 알고리즘의 허용가능한 휴리스틱

A-star 알고리즘이 최적의 해를 보장받기 위해서는

휴리스틱 함수 값이 현재 노드에서 목표 노드까지의 실제 비용보다 항상 작거나 같은 경우

최적의 해를 보장하며 이를 허용가능이라고 한다. (허용가능한 휴리스틱)

 

Best-First Search vs A-star

	Best-First-Search	A-star algorithm
완전성	No	Yes(단, 허용가능한 경우!)
시간 복잡도	O(b^m)	O(bm)
공간 복잡도	O(b^m)	O(b^m)
최적성	No	Yes(단, 허용가능한 경우!)

시간복잡도 : 휴리스틱 알고리즘에 따라 차이가 있으나 A-star가 빠르다.

공간복잡도 : 동일하다.

 

Min-Max 알고리즘, Alpha-Beta 알고리즘

 

단말 노드부터 위로 올라가면서 최소-최대 연산을 반복하여
자신이 선택 할 수 있는 방법 중 가장 좋은 것을 선택한다.

 

MIN노드의 현재값이 부모노드의 현재값보다 작거나 같을 경우 나머지 자식노드의 탐색은 중지된다. (알파자르기)

MAX노드의 현재값이 부모노드의 현재값보다 크거나 같을 경우 나머지 자식노드의 탐색은 중지된다. (베타자르기)