지난시간에 Uninform Search을 배웠다. 현재 상태와 목적지의 정보를 갖지않고 상태공간을 탐색을 탐색하였다.
Informed Search는 목적지와 현재 상태 정보를 가지고 Goal에 다가가기 좋은 방향으로 탐색한다. (Heuristic 함수 사용)
참고로 Informed Search는 Heuristic Search라고도 불린다.
Informed Search 개요
Informed Search는 Uninformed Search의 한계를 보안하기 위해 나왔다.
Informed search는 효율성을 향상시키기위해 문제마다 heuristic 함수를 사용하고 다음과 같은 방법들이 있다.
- Best-first
- A*
또한 이번글의 마지막 부분에서 heuristic을 만드는 기술도 알아볼 것이다.
worst case일 때 여전히 시간복잡도가 지수적으로 증가하지만( O( b^d ) ) Informed Search는 실제적으로 상당한 speed-up을 가질 수 있다. 여기서는 8퍼즐 문제에 대해 예를 들어 설명할 것이다.
Uninformed Search의 한계
8 퍼즐 문제를 Uninformed Search로 풀었을 때 나타나는 문제점을 살펴보도록 하겠다.
solution cost는 평균적으로 22이다. 즉 22번 차례를 거쳐야 goal에 도달할 수 있다.
branching factor 는 약 3에 수렴한다. 즉 상태에서 움직일 수 있는 가짓수가 3개이다. (예를들어 위 아래 오른쪽으로 이동)
완전탐색을 했을 때 goal node의 depth는 22이고 약 3^22( b ^ d )개의 node가 생성된다.
추가적으로 d=12일때, IDS는 약 3.6백만개의 node가 생성된다.
Best-first Search
Best-first Search 자체가 알고리즘이라기 보다는 하나의 탐색 방안을 말하는 것이다.
Idea는 각 node 마다 evalutation funtion f(n)을 사용해 좋은 f(n)값을 갖는 node로 expand한다. 따라서 f(n)에 따라 node를 순서화하여 구현한다. Evalutation function은 node의 quality를 나타내는 추정값이다.
Best-first Search가 적용되는 알고리즘은 다음과 같다.
- Uniform Cost Search : 여기서 evaluation f(n)은 g(n)과 같다. (이전 글에서 작성 : g(n)은 start node에서 현재 node까지의 비용 )
- Greedy Best-first Search
- A* search
Uniform Cost Search를 제외하고는 새롭게 f(n)을 정의해서 사용해야한다.
Heuristic Function
Heuristic : 답을 찾기위한 경험적 법칙(Rule of thumb)을 사용
Heuristic Function h(n)
- 현재 node n부터 goal까지의 비용을 추정하는 함수이다.
- n이 goal node라면 h(n) = 0 이다.
- 예를 들어 n 위치에서 학교까지의 직선거리를 h(n)이라고 할때, 실제 n위치에서 학교까지의 거리랑은 다르다. 즉 h(n)은 추정치이며 실제 값은 더 크다.
Evalutation Function과 Heuristic Function의 차이점
나는 위의 Evalutation Function과 Heuristic Function의 차이점에 대해 궁금했다. 내가 결론내린 차이는 Evaluation Function은 전반적인 현재 상태가 어떤지 나타내는 것이고 Heuristic Function 현재 노드에서 goal까지의 거리를 나타내는 함수이다. 두개 함수 모두 추정치이다.
Heuristic Function을 이용한 8 puzzle probelm
이전에 Informed Search로 풀었을 때는 다음과 같다.
- solution cost는 평균적으로 22이다. 즉 22번 차례를 거쳐야 goal에 도달할 수 있다.
- branching factor 는 약 3에 수렴한다. 즉 상태에서 움직일 수 있는 가짓수가 3개이다. (예를들어 위 아래 오른쪽으로 이동)
- 완전탐색을 했을 때, goal node의 depth는 22이고 약 3^22( b ^ d )개의 node가 생성된다.
이제는 Heuristic Function을 배웠으니 이것을 사용하면 탐색을 줄일 수 있다.
두가지 많이 사용되는 Heuristic은 다음과 같다.
h1 = Goal state와 비교했을 때, 잘못 놓여진 타일의 수
h1(s) = 8
h2 = Goal state와 비교했을 때, 각 타일들이 잘못 놓여진 거리의 합.(Manhattan distance를 생각하면 알기 쉽다)
h2(s) = 3 + 1+ 2 + 2 + 2 + 3 + 3 + 2 = 18
추가 설명
h*는 총 tile을 옮기는 횟수라고 하자
그러면 h* >= h2 >= h1 이라는 수식이 성립한다.
h*가 heuristic function보다 크거나 같으면 admissible하다고 한다.
Greedy best-first Search
위에서 배운 Best-first search 방법 중 특수한 경우인 Greedy best-first Search를 알아보도록 하겠다.
여기서는 h(n) heuristic function을 evaluation function으로 사용한다.
진행 방식은 goal과 가장 가까운 node로 expand한다.
아쉽지만 Greedy best-first Search는 Optimal Path를 찾아주지 않는다. 밑에 그림은 Arad에서 시작해서 Goal까지의 shortest path이다. Greedy best-first Search를 이용하면 위의 그림과 같이 찾아주기 때문에 Optimal Path(Shortest Path)는 아니다.
Greedy Best-first Search의 속성
Complete : Yes Loop와 infinite path가 있는 경우를 제외하고는 Goal을 찾는다.
Optimal : No 위의 예제처럼 optimal한 경로를 찾아주지는 않는다.
Time Complexity : O( b ^ m ) solution을 찾기전 깊이가 m인 모든 노드를 만들어 낼 수 있다.
m = 탐색 공간의 최대 깊이.
하지만 일반적으로 search space는 줄어들어 Goal을 빨리 찾을 가능성이 높다.
Space Complexity : O( b ^ m ) 위와 같이 worst case일 때, solution을 찾기 전 깊이가 m인 모든 노드를 만들어 낼 수 있다.
하지만 일반적으로Space Complexity 또한 줄여준다.
A* Search
현재 node에서 총 경로 비용의 추정치에 기반해 node를 확장해 나간다. 즉 현재 노드까지 왔던거리와 현재노드에서 앞으로 갈 거리의 추정치에 기반한다는 뜻이다.
이 알고리즘에서 Evaluation function은 다음과 같이 정의한다. f(n) = g(n) + h(n)
- g(n) = 현재 노드 n까지 오는데에 든 실제 비용
- h(n) = 현재 n 부터 goal까지 가는데 드는 비용의 추정치
- f(n) = n을 지나 goal까지 가는데 드는 총 비용의 추정치
탐색의 효율성은 heuristic 함수 h(n)에 따라 달라진다.
g(n)만 사용했던 것은 Uniform cost Search
h(n)만 사용했던 것은 Greedy best-first Search
A* Search의 예제이다. Arad에서 다음 노드를 탐색할 때 g(n)+h(n)을 이용해 그 비용이 작은 쪽으로 expand해나간다.
A* Search 의 속성
Complete : Yes 무한 Loop를 제외하고는 Goal을 찾는다.
Optimal : Yes 위의 예제처럼 optimal한 경로를 찾아주지는 않는다.
Time Complexity : worst case일때, 지수 함수적으로 증가.
Space Complexity : worst case일때, 지수 함수적으로 증가.
하지만 일반적으로 search space가 줄어들어 Goal을 빨리 찾고 memory 사용량도 좋다
Admissible heuristics
만약 모든 node n에 대해 h(n) <= h*(n)이라면 heuristic function h(n)은 admissible하다고 한다. (h*(n)은 n에서 goal까지 가는데 드는 실제 비용)
admissible heurisitic은 goal까지 도달하는데 드는 비용이 과대평가되지 않는다. 즉 h(n) <= h*(n)이기 때문에 optimistic 하다는 뜻이다.
우리가 사용했던 heuristic Function인 직선거리는 admissible하다. 모든 노드에서 goal까지 가는데 드는 실제 비용보다 h(n)이 작기 때문이다.
정리하자면
위의 조건을 만족할때 A* Search 알고리즘이라 하며 위의 조건을 만족하지 않는다면 A Search 알고리즘이다.
h(n)이 admissible 하다면 A* search 알고리즘은 optimal 하다.
Dominance 개념
모든 node n에 대하여, h2(n) >= h1(n)라면 h2는 h1을 dominate 한다고 한다. h2, h1 은 heuristic 함수이며 이때 h2는 탐색하는데 더 좋은 heuristic이라고 할 수 있다.
8 puzzle problem에서 평균적으로 expand되는 node의 수는 다음과 같다.
Relaxed problem을 통한 Heuristic Function을 만들기
실제 문제보다 제약조건을 줄여서 새로운 문제를 만드는 것을 relaxed problem이라고 한다.
이런 relaxed problem의 제약조건으로 만든 heuristic function 은 일반적으로 admissible하다. 실제로는 제약조건을 만족해야하기 때문이다.
8 puzzle 문제에서도 h1과 h2를 만들때 모두 relaxed problem으로 만들고 나서 생성된 heuristic이다. 그리고 모두 admissible하다.
요약
실제적으로 상당한 speed up을 경험할 수 있지만 worst case일 떄는 여전히 지수함수적 시간 복잡도를 가질 수있다.(8 puzzle 문제를 생각해 보면 상당한 speed up이 발생한다는 것을 알 수 있다.)