인공지능개론 | Uninformed Search

⚠ Before reading the post ⚠

본 포스팅은 컴퓨터 공학 계열 전공자 대학교 4학년에서 대학원생 기준으로 작성하였습니다.
기본적인 자료구조나 알고리즘 내용은 생략하였습니다.

Uninformed Search | 정보 없는 검색 전략

검색 알고리즘에서는 path에 대한 정보 제공 여부에 따라 두 가지로 나뉜다.

• 목표까지 Agent가 얼마 남았는지 추정이 가능한 Informed search(정보가 있는 검색 전략)
• 아닌 경우에는 Uninformed Search(정보 없는 검색 전략)

인공지능에 들어가기 앞서 인공지능 자체가 방대한 데이터셋 속에서 해를 찾는 문제를 해결하는 데 있어서 가장 기본적인 것이 알고리즘에서부터 시작하기 때문에 이 중에서 목표에 다다르는 검색 전략부터 다루지 않나 생각된다.

인공지능개론 강의에서 다뤘던 기본적인 term들을 아래와 같다.

• Agent: 현 문제에서 탐색하는 actor라고 생각하면 쉽다. Agent가 매 노드가 확장될 때마다 goal state에 다다르는지 확인하며 다다를시에는 종료가 된다.
• State: 상태, 상태 환경은 state space. 초기 상태는 initial state, 목표 상태는 goal state
• Action: Agent가 상태(state)에서 행할 수 있는 여러가지 동작들.
• Path: goal까지 찾아가는 경로, 보통 알고리즘의 목표는 적은 시간, 메모리공간 ,즉 최소 비용으로 이상적인 해를 도출하는 것이 목표이다.

이번 포스팅에서 다룰 탐색 공간은 모두 tree-based*
알고리즘들을 들어가기 전에 알고리즘들의 평가 척도는 아래와 같다.

• Completeness: "유한한 시간과 공간 내 항상 결과가 보장이 되는 것인가?"
• Time and space complexity:
  • b: 탐색 트리에서 branch factor들
  • d: 최소 비용 solution에서 tree 깊이
  • m: 상태 공간에서 최대 깊이
• Optimality: "최소 비용" solution인가? → d가 보장이되면 보통 optimal하다고 보면 된다.

Breadth First Search | 너비 우선 탐색

너비 우선 탐색은 각 방분하게 될 후보 노드들을 FIFO 구조의 Queue에 임시로 저장하게 된다. 이 때 already-expanded, 즉 이미 방문한 노드들은 추가되지 않는다.
기본적인 구조는 생략하고, 균일 트리를 가정하고 알고리즘 평가는 아래와 같다.

• Time and Space Complexity

각 노드들은 b개의 노드들이 탐색시 생성되는데, 전체 공간을 모두 더해 계산을 하게되면, 위와 같은 복잡도가 나오게 된다. exponential 하다는 점에서 메모리 요구량과 실행 시간이 큰 문제점을 지니고 있다.

• Completness & Optimality: YES

Depth First Search | 깊이 우선 탐색

깊이 우선 탐색은 BFS와 다르게 방문한 노드들을 LIFO 구조의 Stack에 넣음으로써 후퇴시, stack에 담긴 정보를 토대로 후퇴거나 전진하게 된다. 마찬가지로 기본적인 구조는 생략하고 알고리즘 평가는 아래와 같다.

• Completeness & Optimality: NO

보통 max depth m은 d 내에 존재하면 해당 알고리즘은 항상 completeness한 모습을 보여주나 DFS 같은 경우 한 경로만 계속 탐색할 경우 특정 경우 bounded하지 못한 문제를 만날 시 무한 루프에 빠질 수 있다. (m > d) 그럼에도 불구하고 BFS보다 DFS을 사용하는 이유는 아래와 같은 이유로 사용한다.

• Time and Space Complexity

• Time Complexity: $O(b^m)$ → BFS와 동일하다. DFS로 탐색할 시 max depth까지 탐색.
• Space Complexity: $O(bm)$ → 해당 branch factor 모두 저장할 필요가 없으며, max depth까지만 필요하므로, exponential한 BFS의 메모리 사용과 달리 DFS에서는 linear한 메모리 공간 사용을 볼 수 있다.

Iterative Deepening Search | 깊이 제한 검색

위에서 살펴본 DFS의 무한 루프를 해결하기 위해 boundary를 지정해 DFS와 비슷한 메커니즘으로 탐색한다. iteration 별 깊이 boundary를 부여한다.

• Completeness & Optimality: YES

Goal이 유한한 깊이 내 존재 시 유한 시간 내 찾는 것이 가능하므로 이전 방법과 다르게 기약없는 알고리즘이 아닌, optimality 와 completeness 조건이 모두 충족한 탐색 방법이다.

• Time and Space complexity
  max depth가 d. least solution이 보장이 된다.

  • Time Complexity: $O(b^d)=b+b+b^2+...b+b^2+...+b^d$ → BFS에 비해 redundant한 계산량이 꽤나 있는 편이다. BFS의 $\frac{b}{b-1}$ 배 정도. 따라서 uniform한 형태일 경우 BFS보다 IDS가 더 유리하다.
  • Space Complexity: $O(bd)$

해의 유무에 따라서 depth가 d인지 m인지 나뉘게 되는 것이 포인트.

Uniform Cost Search | 균일 비용 검색

너비 우선 탐색과 거의 동일하며 비용이 다른 edge들을 가정한다. 다익스트라 알고리즘과 동일하다.
노드 확상시 edge를 담는 임시 storage에서는 우선순위를 부여해야하므로 Heap을 사용하게 된다. 모든 edge 비용이 동일하면 BFS와 거의 비슷하게 작동한다.

그림에서 (a)는 문제이 상태 공간이고, (b)는 진행 상황, 이 때 ABC 는 heap에 담기게 된다.

• Completeness & Optimality: YES → 애초에 Heap을 사용함으로써 최소 비용을 지속적으로 찾아내기 때문에 optimal하다.

• Time and Space Complexity 아래 표 참고, 모든 동작 비용이 동일할 때 BFS와 동일하다. step cost에서 epsilon > 0 조건이 보장된다면 무한 경로에 빠질 일은 결코 없다. f상

Wrap up & Conclusion

아래 표는 본 포스팅에서 다룬 알고리즘의 정리표.

여기서 Depth-Limited에 대해 다루지는 않았지만, depth는 제한되고 goal이 외부에 있는 경우라고 이해하면 된다.
어느 알고리즘이 엄청 뛰어나다고 특정할 수 없지만, 문제 상황별 상이하므로 적재적소 최선의 알고리즘을 선택하는 것이 가장 좋은 알고리즘이다.