이전까지의 search는 state에 대한 평가 없이 그냥 탐색만 했음.
하지만 이제는 state에 대한 평가인 f가 있고, f가 작은 순으로 state를 골라가면서 탐색을 함.
informed search의 제일 기본은 best first search
best-first search
function BEstFirstSearch(f){
frontier.insert(intialState);
reached[intialState] = makeNode(initialState);
while(!frontier.empty()){
node = frontier.pop();
if(goal(node)) return solution;
for(s in node.successors){
if(s is not in reached or node.f+cost(n, s) < reached[s]){
reached[s] = makeNode(s);
frontier.insert(s);
}
}
}
} greedy best first search
greedy best first search에서 f=h
즉, node를 선택할 때 미래에서의 cost가 제일 적은 node를 선택함.
당장 미래가 좋아보이는 node를 선택하기 때문에(과거를 고려하지 않기 때문에) optimal한 solution은 나오지 않음.
- completeness : state space가 유한하면 yes
- time complexity : search state의 제일 깊은 곳의 depth가 m이면, O(b^m)
- space complexity : O(b^m)
- optimality : no
A*
f = g + h
이 f값이 작은 노드를 선택해서 계속 expand해나가면서 solution에 도달하는 search
heuristic
이때 a에서 사용하는 h를 heuristic function이라고 함
heuristic function은 admissible하고 consistent 해야 A에 적용이 가능함.
admissible
heuristic이 admissible하다는 건 h(n)값이 실제 n에서 goal로 가는 cost보다 작다. 즉 절대 overestimate 하지 않는다!
만약에 heuristic이 admissible하면 그 heuristic을 사용한 A*는 optimal함
!증명
어떤 suboptimal goal G2와 optimal goal G로 가는 노드 n이 둘 다 fringe에 있다고 하자.
이때 f(G2)=g(G2)+h(G2) = g(G2) > f(G)=g(n)+h*(n) >= g(n) + g(n) = f(n)
f(G2)>f(n) 이므로 fringe에서 G2가 절대 pop되지 않음.
consistent
graph search에서는 repeated state로 가는 새로운 path를 허용하지 않음. 근데 search로 하다 보면 예전에 방문했던 state의 f값이 작아질수도 있는데 방문을 허용하지 않으면 결국엔 optimal path를 못찾게 될수도 있음
따라서 항상 최적의 f는 처음부터 찾아져야 하는데 이를 보장하는 게 consistency라는 특징임.
heuristic이 consistent하다는 것은 h(n) <= c(n, n') + h(n')을 만족한는 것.
만약에 heuristic이 consistent하면
f(n') = g(n')+h(n') = g(n)+c(n, n')+h(n')>=g(n)+h(n)=f(n)
즉 f(n')>=f(n)으로, heuristic으로 찾은 optimal path의 f값은 항상 증가가 보장된다.
heuristic이 consistent하면 그 heuristic을 사용한 A*는 optimal하다
이때 heuristic이 consistent하면 admissible하지만, 그 역은 성립하지 않음!
A* evaluation
- completeness : search space가 유한하면 yes
- optimality : yes
- time complexity : solution이 있는 depth에 exponential함
- space complexity : generate된 node들을 전부 maintain해야 하므로, time complexity랑 똑같음 -> A*는 메모리 문제가 큼
weighted A*
f(n) = g(n) + w*h(n)
search state가 엄청 큰데 굳이 엄청 optimal한 solution을 찾지 않아도 될때 사용
memory-bounded heuristic search
앞에서 봤다싶이, A의 가장 큰 문제는 메모리임. 따라서 A의 메모리 문제를 개선하는 알고리즘이 몇개 존재
Beam Search
expand할 노드의 개수를 제한하는 방법
iterative-deepning A*(IDA)
A에서 cutoff할 f값을 정해두고 답을 찾을때까지 f값을 증가시키면서 A를 반복하는 방법
하지만 f값을 얼마나 증가시킬 것인지에 대한 어려움이 있음
RBFS(Recursive Best First Search)
best first search를 dfs처럼 해서 linear space만을 사용하려는 알고리즘
여기서 사용하는 아이디어는 f_limit!
f_limit은 내 부모나 sibling 중 이미 이만큼 작은 f가 있다는 정보를 바탕으로 자식들을 search하는 것. 내 자식들의 f값이 f_limit보다 크면, 더 이상 볼 필요가 없으므로 리턴한다.
function RBFS(node, f_limit){
if(goal(node)){
return node;
}
successors = expand(node);
if(successors.empty()){
return (failure, infinity);
}
while(true){
for(s in successors){
best = s 중 f값이 제일 작은 node;
if(best.f > f_limit){
return failure, best.f;
}
alternative = s 중 f값이 두번째로 작은 node;
result, best.f = RBFS(best, min(f_limit, alternative.f));
if(result != failure){
return result, best.f;
}
}
}
}- completeness : state space가 유한하면 yes
- optimality : heuristic이 admissible하면 yes
- time complexity : difficult to characterize
- state complexity : O(bd) (dfs처럼 보므로)
Memory-bound A*
A*처럼 하는데 미리 정한 메모리가 꽉차면 f 값이 가장 큰 노드는 버림
메모리가 충분하다면 complete, optimal
heuristic 정하는 방법
dominance
어떤 heuristic h2, h1이 있을 때 모든 node n에 대해 h2(n)>=h1(n)이면 "h2 dominates h1"이라고 한다.
그리고 heuristic set {h1, ..., hn}에 대해 전부 admissible하다면 각 상황에서 서로 다른 heuristic을 적요해도 됨
admissible heuristic
- relaxed-문제의 heuristic은 원래 문제의 heuristic으로 적용 가능하다
- subproblem의 heuristic은 원래 문제의 heuristic으로 적용 가능하다
