Uninformed search, BFS, UCS

Uninformed search (= Blind search)

문제 정의 외에는 다른 정보 없이 검색하는 알고리즘

• Breadth-first search

• Uniform-cost search

• Depth-first search

• Depth-limited search

• Iterative deepening depth-first search

• Bidirectional search

 

Breadth-first search

루트노드 EXPAND -> 모든 후임자(successors) EXPAND -> 모든 후임자(successors) EXPAND -> …

 

Graph search 에서 frontier를 FIFO 큐로 구성하면 됨

 

function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure
  node <- a node with STATE = problem.INITIAL_STATE, PATH-COST = 0
  if problem.GOAL-TEST(node.STATE) then return SOLUTION(node) // 초기상태에서 Goal test
  frontier <- a FIFO queue with node as the only element
  explored <- an empty set
  loop do
    if EMPTY(frontier) then return failure
    node <- POP(frontier)
    add node.STATE to explored
    for each action in problem.ACTIONS(node.STATE) do
      child <- CHILD-NODE(problem, node, action) // EXPAND
      if child.STATE is not in explored or frontier then // 이 전에 방문한 적이 없던 노드라면
        if problem.GOAL-TEST(child.STATE) then return SOLUTION(child) // goal test
        frontier <- INSERT(child, frontier)

BFS 는 초기상태에 goal test를 하고, frontier에 노드를 넣기 전에 goal test를 합니다.

Frontier에 Goal state가 들어갈 때까지 반복합니다.

 

평가

• Completness : Branching factor b가 유한하다면 yes

• Optimality : path cost 가 node depth에 따라 nondecreasing 하다면 yes.
  즉 얕은 답을 찾을 수록 optimal 하다면 이는 ok

• Time complexity
  b + b^2 + b^3 + … + b^d = O(b^d)   -> depth 한 개마다 최대 b개의 노드가 생겨나기 때문
  d = 가장 얕은 goal node 의 깊이
  만약에 frontier에 넣을 때 goal test를 하지 않고, 나올 때 한다면 시간 복잡도는 O(b^d + 1)

• Space complexity
  생성된 모든 노드가 메모리에 올라왔을 때 O(b^d)

• Explored set  = O(b^(d-1))

• frontier = O(b^d)

 

Optimality

Space complexity

BFS의 메모리문제

BFS는 b가 10만 되어도 메모리가 10 테라바이트 이상 필요합니다. 따라서 메모리 문제로 실제 사용이 어렵습니다.

 

Uniform-cost search

bfs에서는 최적을 보장하지 못했던 depth와 path cost 가 비례하지 않던 문제들을 해결하기 위해 사용하는 알고리즘입니다.

FIFO 큐를 사용하지 않고 priority queue 를 frontier 로 사용함으로서 path cost 가 낮은 노드를 먼저 EXPAND 하게 됩니다.

 

주요한 특징으로는 Goal test를 넣을때가 아닌 꺼낼 때 한다는 것입니다. 왜냐하면 같은 goal state 이더라도 더 최적의 값이 있을 수 있고, 더 늦게 들어간 goal state가 앞서 들어간 goal state보다 최적일 경우 이는 들어갈 때가 아닌 나올때 판별 가능하기 때문입니다.

이런 경우 먼저 들어간 goal node는 교체될 수 있습니다.

 

function UNIFORM-COST-SEARCH(problem) returns a solution, or failure
  node <- a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
  frontier <- priority queue ordered by PATH-COST
  explored <- an empty set
  loop do
    if EMPTY(frontier) then return failure
    node <- POP(frontier)    // pq라서 가장 낮은 cost 의 노드를 찾게됨
    if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)  // expand, 나올 때 goal test
    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 // 프론티어 혹은 explored에 없다면
	      frontier <- INSERT(child, frontier)
      else if child.STATE is in frontier with higher PATH-COST then // 프론티어에 이미 있는 노드보다 현재 자식 노드의 cost 가 더 작다면 바꿔치기
    	  replace that frontier node with child

 

평가

• Completeness : 모든 step cost 가 양수이면 yes.   0이나 음수면 불가능

• Optimality : 자명함

• Time and space complexity
  O(b^(1 + floor(C* / e))

• C* = 최적 해의 cost

• e  = cost가 가장 적은 action의 cost