Uniform Cost Search와 A* Search

Artificial Intelligence: A Modern Approach 참고

Uniform Cost Search

Breadth First Search와 비슷한 알고리즘이지만 조금의 차이가 있다.

1. POP을 한 다음 Goal Test를 수행.
2. Path cost $g(n)$ 순으로 POP 수행.

• Time Complexity: $O(b^{1+c^/\epsilon})$, Space Complexity: $O(b^{1+c^/\epsilon})$

  • $c^*$: Optimal Cost.
  • $\epsilon$: 작은 양의 상수.

• 수도코드

출처: Artificial Intelligence: A Modern Approach

A* 탐색

A* 탐색은 node를 $f(n) = g(n) + h(n)$을 이용해 탐색한다.

• $g(n)$: start -> node까지의 cost.
• $h(n)$: node에서 goal까지의 cost.

$g(n)$은 시작 노드에서 현재 노드 n까지의 path cost를 의미하며, $h(n)$ 은 현재 노드 n부터 goal 노드까지의 cheapest path의 estimated cost를 의미한다. 즉 두개를 합한 $f(n)$은 노드 n을 관통하는 가장 estimated cost가 낮은 solution이 된다.

알고리즘 자체는 uniform-cost search와 비슷하다. 다만 A*는 $g$ 함수 대신 $g+h$ 함수를 사용한다는 점이다.

A* Search가 제대로 동작하기 위해선 heuristic 함수($h(n)$)가 두가지 조건을 만족해야한다.

• Admissible heuristic: 절대 goal까지의 cost를 과대평가해선 안된다.
• Consistency: $h(n) \le c(n,a,n')+h(n')$
  • 모든 consistent heuristic은 admissible하다.

function A*-Search(problem) returns a solution, or failure
    node <- a node with STATE = problem.INITIAL-STATE, PATH-COST=0
    frontier <- a priority queue ordered by PATH-COST,with node as the only element
    explored <- an empty set
    loop do
        if Empty?(frontier) then return failure
        node <- POP(frontier) #frontier에서 가장 h(n)이 낮은 node 선택
        if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
        add node.STATE to explored
        for each action in problem.ACTIONS(node.STATE) do
            child <- CHILD-NODE(problem.node, action)
            if child.STATE is not in explored or frontier then
                frontier <- INSERT(child.frontier)
            else if child.STATE is in frontier with higher h(n) then
                replace that frontier node with child

• Time Complexity: $O(b^m)$, Space Complexity: $O(b^m)$
  • m: solution까지의 action의 개수.