[인공지능] Search

1. Search

• 문제 해결
  • 어떤 문제에 답을 찾기 위함이다. -> 어떤 행동을 취해야 하는가? 에 대한 논의
  • 예시
    • 길찾기
    • 게임
    • 논리 구조

1.1 State Space (상태 공간)

• 어떤 문제의 상태와 행동을 Graph로 표현.
  • 서로 다른 문제 상황을 Vertices로 나타낸다.
    • 일반적으로 시작 상태를 S, 목표 상태를 G로 정의한다.
  • 행동을 취하고 적용하는 것을 Edges로 나타낸다.
• 일반적으로 다음과 같은 표기법을 사용한다.
  • N - Nodes(states)
  • A - Arcs(actions)
  • S - Start state
  • G - Goal state
• 상태와 이 상태 사이의 행동, 시작과 목표를 정해야 한다.

1.1.1 상태 공간을 사용하는 예

• 8-puzzle
  

• Inference
  

• Route finding
  

1.1.2 State Space Search

• 시작 상태 S에서부터 목표 상태 G까지의 경로를 구하는 것
  

• 탐색 알고리즘
  시작 상태만 갖고 가능한 다음 상태를 탐색하며 목표 상태에 도달한다.

  • G를 찾을 때 까지의 일반적인 트리 탐색법
  1. S에서 시작
  2. 현재 상태가 G인지 확인한다.
  3. 다음 상태로 갈 수 있는 행동을 취한다.
  4. 다음 상태를 선택한다.
  5. 2번으로 회귀

1.2 Depth-First Search, DFS (깊이 우선 탐색)

• 가능하다면 가장 깊은 곳 까지 탐색한다.
  DFS를 수행하는 수도코드
  

• 예시
  
  위 상태에 대해 (Open에 들어가는 노드는 Stack 구조)

1. X=0 open = {A}, closed = {}
2. X=A open = {B,C,D}, closed = {A}
3. X=B open = {E,F,C,D}, closed = {A,B}
4. X=E open = {F,C,D}, closed = {A,B,E} ->더 이상 탐색이 불가능해 부모 노드로 회귀
5. X=F open = {G,C,D}, closed = {A,B,E,F}
6. G

A->B->E->F->G의 경로로 G까지 도달,
여기서,
부모 노드가 무엇인지를 기반으로 역추적한다면
G<-F<-B<-A

1.3 Breadth-First Search, BFS (넓이 우선 탐색)

• 각 계층마다 해당 계층의 노드를 모두 탐색하고 넘어간다.
  BFS를 수행하는 수도코드
  

• 예시
  1.2에서 제시한상황과 같은 상황에 대해 (Open에 들어가는 노드는 Queue 구조)

1. X=0 open = {A}, closed = {}
2. X=A open = {B,C,D}, closed = {A}
3. X=B open = {C,D,E,F}, closed = {A,B}
4. X=C open = {D,E,F,G}, closed = {A,B,C} ->G로 갈 수 있지만 BFS이므로 D부터 탐색
5. X=D open = {E,F,G}, closed = {A,B,C,D}
6. X=E open = {F,G}, closed = {A,B,C,D,E}
7. X=F open = {G}, closed = {A,B,C,D,E,F}
8. G

A->B->C->D->E->F->G의 경로로 G까지 도달,
여기서,
부모 노드가 무엇인지를 기반으로 역추적한다면
G<-C-<-A

화살표 하나가 동등한 가치를 가진다면
주어진 상황에 대해서는 BFS가 더 효율적이라고 할 수 있다.

1.4 Solution path

• 부모 노드의 정보와 State를 함께 저장한다.
  • State = ((State name), (Parent state), (Evaluation) ... )
• 1.2과 1.3에서 부모 노드가 무엇인지를 기반으로 역추적이 해당 방식이다.

1.5 DFS VS BFS

b를 하나의 상태에서 몇개의 상태로 전이가 가능한지를 나타내고,
d를 탐색 깊이라고 한다면 DFS와 BFS는 다음과 같은 복잡도를 가지게 된다.

여기서 Optimal은 최단 경로를 찾을 수 있는가를 나타낸다.

1.6 Iterative Deepeming Search, IDS

DFS를 기반으로 탐색을 진행하되 깊이의 한계, 즉 각 탐색 단계에서 Depth limit의 한계를 정하고 이를 1씩 늘려가며 진행한다.

IDS 방식의 경우

• 시간 복잡도 = O(b*d)
• 공간 복잡도 = O(b*d)
• 최단 경로 탐색 : 가능

따라서 해당 방법이 DFS와 BFS의 단점을 보완하고 장점만 취할 수 있는 탐색 방법이다.

--9/7 인공지능, Dongguk Univ. C.S.E