[인공지능] 3. Solving problems by searching - 2

4. Blind Search

  1) Breadth-First Search (너비우선 탐색) - FIFO(First in first out) 

   : root node를 처음으로 expand하고, 모든 successors(자손 노드)를 다음으로 expand한 다음에 또 다음 successors......

    

 

   - Performance of Breadth-First Search

    : complete 하지만 optimal 하지는 않다.

(* complete : 무조건 goal을 찾을 수 있음)

만약 가장 얕은 goal node가 depth d에 있다면, 모든 더 얕은 node들을 탐색한 다음에 찾을 수 있을 것. 그러나 그 가장 얕은 goal node가 항상 optimal하다고는 볼 수 없음. (단, 모든 cost가 같을 경우 optimal 함)

 

    - Time complexity : O(b^d)

    - Space complexity : O(b^d) 

       : BFS에서는 수행 시간보다도 메모리 requirements가 더 큰 문제임

 

(b = number of children at each node, 즉 한 노드에 달린 가지 수, d = 가장 얕은 정답의 깊이)

depth가 깊어질 수록 차지하는 메모리는 엄청 커지는데, 메모리는 물리적으로 추가로 만들어 낼 수 가 없으므로 더 중요한 문제가 된다.

 

  2) Uniform-Cost Search 

    : 가장 얕은 노드를 expanding 하는 대신에, uniform-cost search에서는 가장 적은 path cost g(n)을 갖는 node n 을 expanding 한다. 이것은 g에 의해 정렬되는 priority queue에 frontier를 저장하여 수행된다.   

  ( * frontier : 아직 탐색하지 않은 노드들의 집합 )

   - goal test는 노드를 처음에 생성할 때가 아니라 expansion을 위해 선택할 때 활용된다. 먼저 만들어진 goal node는 아마도 suboptimal한 path일 가능성이 높기 때문에, frontier에 있는 노드 중 더 나은 path를 찾으면 test가 돌아간다.  

 

   - Performance of Uniform-Cost Search

    : 만약 cost가 0인 action의 무한개의 sequence가 있는 path가 있다면 Uniform-cost Search는 무한 루프에 갇히게 된다. 따라서 completeness는 모든 단계에서의 cost가 양의 상수 ε를 초과할 경우에만 보장된다. 

 

  또한 uniform-cost search는 항상 optimal 하다. 우리가 observe한 node에 대해 우리는 항상 그 node에 대한 optimal path를 찾을 수 있다. 그러므로 step costs가 음수가 아니라면, node가 더해질 수록 path는 절대 짧아질 수 없다. 따라서 첫번째로 선택된 goal node가 반드시 optimal solution이다. 

 

    - Time complexity, Space complexity 둘 다

: BFS와 마찬가지로 memory requirements가 execution time보다 더 큰 문제

 

  3) Depth-first Search (깊이 우선 탐색) - LIFO

   : search tree의 현재 frontier에서 더 깊은 노드를 먼저 expand

- Performance of Depth-First Search

    : 유한한 state spaces에서의 graph-search version은 complete하지만, tree-search version은 무한루프 때문에 complete하지 않다. DFS는 추가적인 memory cost가 없이 수정할 수 있어서, 현재 states가 root부터 current node까지의 path위에 있었는지 없었는지를 확인할 수 있다. 즉, 왔던 노드인지 확인이 가능하다. 이렇게 하면 무한 루프를 피할 수는 있지만, 여전히 rebundant path를 가는 것은 막을 수 없다. (rebundant path란, 서로 다른 경로지만 시작점과 끝점은 서로 같은 경로. a->c->d와 a->b->e->d처럼) 즉, 같은 경로를 무한히 반복하는 것은 막을 수 있어도, 같은 경로는 아니지만 시작점 a에서 끝점 b를 가는 경우가 매우 많을 때, 이 경로들을 모두 가는 것을 막을 수는 없다는 것! 또한, infinite state spaces에서는 두 버전 다 complete 하지 못하다. 

  또한 cost와 관계없이 가장 먼저 찾은 것을 return하므로 nonoptimal하다. 

(보통 cycle이 있는게 graph, 없는게 tree인데 무슨 말이지..했더니 교재의 저자가 tree에 check가 없으면 계속 들어갈 수 있다고 정의를 했다나 뭐라나 말이냐 방구냐 누가 나 좀 이해시켜줘)

 

    - Time complexity : O(b^m)

      : Depth-first tree search는 tree에 있는 모든 O(b^m)개의 노드를 생성해낸다. 이것은 state space의 크기보다 훠어얼씬 더 커질 수 있다. 

( State Space  : initial state에서부터 어떤 action squence를 통해 도달할 수 있는 모든 states들의 집합 )

    - Space complexity : O(b*m) 

(m = max depth)

  * Backtracking Search 

  - 보통 dfs는 recursive function으로 수행하는 것이 일반적이다.

  - 이 때 backtraking search를 활용하면 메모리 사용을 줄일 수 있다. Backtracking에서는 기존에 모든 자식 node가 생성되었던 것과는 달리, 나머지는 기억만 해두고 오직 하나의 자손만이 생성된다. 그래서 기존에 memory 사용이 O(bm)이었던 것과는 달리 O(m)으로 줄어들게 된다. 

  - backtracking을 활용하면 또 다른 memory-saving(time-saving) trick이 용이해진다. 현재 state의 description을 처음에 복사하는 것이 아니라, 직접 변경하여 자손 노드를 생성하는 방법이다. 이를 통해 필요한 memory가 오직 한 state의 description과 O(m)의 action으로 줄어든다. 이것이 가능하려면, 다음 노드를 생성하기 위해 go back, 돌아갈 때 각 modification을 원래대로 되돌릴 수 있어야 한다. 

 

  4) Depth-Limited Search

    : infinite state spaces에서의 dfs failure는 depth limit l을 둔 depth-first search를 통해 해결할 수 있다. 이것은 depth l에 있는 노드까지만 탐색하고 돌아온다. 그 이상은 더 이상 내려가지 않는다. 

 - Depth-limited search에는 두 가지 종류의 failure가 있다. 하나는 solution이 존재하지 않는 standard failure value고, 다른 하나는 solution이 depth limit 안에 존재하지 않는 cutoff value 이다. 

  - depth-limited search는 complete하지도, optimal 하지도 않다.

  - Time complexity : O(b^l)

  - Space complexity : O(bl)

 

 

  5) Iterative Deepening Search 

    : best depth limit을 찾는 방법. depth limited search 에서 goal을 찾을 때까지 depth limit을 0부터 1씩 증가시켜 나가는 것

 - Iterative deepening 방법은 depth-first의 장점과 breadth-first search의 장점을 결합시켜 놓음

 - dfs처럼 메모리 사용량이 크지 않고, breadth-first처럼 branching factor가 finite하면 complete하다. 

 

  - Time complexity : O(b^d)

  - Space complexity : O(bd)

 

  * Breadth-first and Iterative Deepening Hybrid

  - 보통 iterative deepening은 search space가 크고 solution의 깊이를 알 수 없을 경우, uninformed search(=blind search) 의 방법이 선호된다. ]

  - 만약 repetition에 대해 걱정이 된다면, bfs를 가용한 메모리까지 사용하고, 그 다음부터 iterative deepening을 frontier의 모든 노드에 대해 수행시키는 hybrid한 방법을 사용할 수 있다. 

 

 * Iterative Lengthening Search

  Iterative deepening search는 각 반복마다 새로운 노드들의 레이어 전체를 탐색한 후 다음 레이어로 나아간다는 점에서 bfs와 유사하다. uniform-cost search의 memory requirements를 피하면서도 알고리즘의 optimality 함을 유지한다는 점에서 굉장히 의미있다! depth limit을 늘려나가는 대신에, path-cost limit을 증가시키는 아이디어가 사용되었는데, 만약 path cost가 current limit을 초과하는 노드를 생성했을 경우에 그것은 그 즉시 삭제된다. 매 새로운 반복마다, 앞선 반복에서 삭제된 노드들 중에 가장 작은 path node를 limit로 설정해준다. 그 결과를 얻어내는 알고리즘이 바로 iterative lengthening search이다. 아쉽게도 iterative lengthening은 uniform-cost search에 비해서 상당한 오버해드를 발생시킨다. 

 

 6) Bidirectional Search

    : 하나는 initial state에서 부터 forward 하게, 하나는 goal에서 부터 backward하게 두 개의 search를 동시에 수행한다. (두 개의 search가 가운데에서 만나기를 예상한다)  -> goal state를 아는 경우 사용 가능

     

 위 motivation은 기존 b^d보다 더 값이 작다. 

 

  - bidirectional search는 goal test가 두 search의 frontier들이 교차(intersect)했는지 안했는지를 확인하는 방식으로 대체되어 수행된다. 

 - 두 search가 모두 breadth-first라고 하더라도, 이러한 first such solution은 optimal하지 않을 수 있다. 이러한 차이를 없애기 위해서는 몇가지의 추가적인 검색이 필요하다.

 - time complexity in both direction : O(b^(d/2)) -> 절반임

 - space complexity :  O(b^(d/2)) -> 두가지 검색 중 하나를 iterative deepening으로 수행하면 절반정도 줄일 수 있지만, intersection check를 위해 frontiers의 적어도 하나는 메모리에 보관하고 있어야 한다. 이 space requirement가 bidirectional search의 가장 대표적인 약점이다. 

 

 

7) Comparison