[인공지능] 2. 탐색

1. 탐색

탐색(Search)의 정의

컴퓨터가 문제를 해결하기 위하여 스스로 해답에 이르는 경로를 찾아가는 과정

Ex: 알파고는 어떻게 수를 읽었을까? ->"탐색"을 통해, 1. 가능한 수를 탐색하여 최적인 수를 선택 2. 딥러닝을 이용해서 가장 가능성 있는 수를 추려냄(가능한 수가 너무 많아서)

 

상태, 상태공간, 연산자

초기상태(Initial state): 문제해결을 시작하는 상태

목표 상태(Goal state): 목표가 되는 상태

상태 공간(state space): 문제를 해결하는 과정에서 여러가지 상태(state)가 나타나게 되며, 이러한 상태들이 모여 있는 공간

연산자(operator or action): 다음 상태를 생성(즉, 상태 변경)

탐색(search): 상태 공간에서 초기 상태에서 목표 상태까지의 경로를 찾는 것

 

 

2. 상태 공간의 예

8-puzzle

타일을 적절히 움직여서 목표 상태에 도달하는 게임

연산자는 blank의 위치 변경이 될 것이다

 

연산자: 빈탄을 상하좌우로 움직이는 것

따라서 UP, LEFT, DOWN, RIGHT

 

하노이 탑(Tower of Hanoi)

원판은 한 번에 하나씩만 옮겨야 하고, 작은 원판 위에 큰 원판을 올릴 수 없음

8-queen Problem

8 x 8 체스판에 서로를 위협하지 않도록 8개의 퀸을 배치하는 문제
▪ 퀸은 같은 행, 같은 열, 대각선 방향으로 공격 가능
▪ 따라서 서로 다른 퀸이 같은 행, 열 또는 대각선을 공유하지 않도록 배치하는 것이 필요 

▪ 상태? 연산자?

 

 

가정: 각각의 퀸을 정해진 열에서만 움직이게 한다.

*서로 공격할 수 없는 방식으로 하나의 퀸을 1열에, 그리고 다른 퀸을 2열에 배치

*이런식으로 k번째 단계에서 퀸을 k열에 놓고 이전에 배치한 k-1개의 퀸을 공격하지 않는지 확인

 

3. 탐색 트리

탐색 트리

초기 상태에서 연산자를 적용하면 아래와 같은 트리 구조가 생성되면, 이를 탐색 트리(Search Tree)라고 함

-노드(node):=상태(state)에 해당

-루트 노드(root node): 초기 상태

-에지(edge): 연산자

탐색 트리에서는 모든 노드가 미리 생성되어 있지 않다 (즉 동적으로 생성된다)

-현재 상태에서 연산자를 적용할 때마다 새로운 상태 노드가 생성됨

   -확장(expand): 어떤 노드에 연산자를 적용하여 새로운 상태 노드를 생성하는 것

      -아직 확장되지 않은 노드: 열려있다(open)

      -확장이 끝난 노드: 닫혀있다(close)

 

4. 기본적인 탐색 기법

탐색 기법

Blind search (or Uninformed search): 목표 노드에 대한 정보를 이용하지않고 기계적인 순서로 노드를 확장하는 방법. 소모적 탐색

Heuristic search (or Informed search): 목표 노드에 대한 경험적인 정보(즉, heuristic)를 사용하는 방법. 효율적인 탐색 가능

 

5. 맹목적 탐색 #1: 깊이 우선 탐색(DFS)

DFS(Depth-First Search)

깊이 우선 탐색(depth-first search)은 탐색 트리 상에서, 해가 존재할 가능성이 존재하는 한, 앞으로 계속 전진하여 탐색하는 방법

-만일 더 이상 진행할 경로가 없을 시, 이전 상태 중 다른 경로로 갈 수 있는 위치로 복귀하여 탐색을 진행

* 인공 지능에서는 탐색 공간에 노드들이 미리 만들어져 있는 것은 아님. 탐색이 진행되면서 노드들이 동적으로 생성됨

 

OPEN/CLOSED List

탐색에서의 데이터 구조

1. OPEN List: 확장이 되어 상태가 생성되었으나 아직 탐색하지 않은 상태 노드 리스트

2. CLOSED List: 탐색이 끝난 상태노드 리스트

DFS Algorithm

x는 각 단계 open list의 첫번째 node가 되는것이여~

 

6. 맹목적 탐색 #2: 너비 우선 탐색(BFS)

BFS

루트 노드의 모든 자식 노드들을 먼저 탐색한 후에 해가 발견되지 않으면 한 레벨 내려가서 동일한 방법으로 탐색을 계속하는 방법이다.

BFS Algorithm

8. 경험적 탐색 방법

Heuristic Search

Blind search (DFS, BFS)를 사용하는 경우 시작 노드에서 목표 노드까지의 경로를 찾기 위해서는 상당히 많은 시간이 소모될 수 있음 

경험적인 탐색 (Heuristic search) 방법:
▪ 문제 영역에 대한 정보나 지식을 사용할 수 있다면 탐색 작업을 훨씬 빠르게 할 수 있다. 이것을 경험적 탐색 방법(heuristic search method) 또는 휴리스틱 탐색 방법이라 함
▪ 이때 사용되는 정보를 휴리스틱 정보(heuristic information)

Ex: Heuristic info in 8-puzzle

평가 함수(Evaluation function): 현재 상태를 입력 받아서 휴리스틱 값을 계산하여 반환하는 함수

9. 언덕 등반 기법(Hill-Climbing)

Hill-Climbing Search

언덕 등반 기법: 평가 함수의 값이 좋은 노드를 먼저 처리하는 방법

예: 평가 함수= 제 위치에 있지 않은 타일의 개수 사용(값이 작을수록 좋은 노드)

문제점
1.휴리스틱 값이 다 똑같다면 어떻게 이동하는가?
2. 현재보다 휴리스틱 값이 작지 않은 case가 발생한다면 ?

현재 상태에서 휴리스틱 함수 값이 가장 좋은 노드를 선택한다. 

▪ 이것은 등산할 때 무조건 현재의 위치보다 높은 위치로만 이동하는 것과 유사함. 일반적으로는 현재의 위치보다 높은 위치로 이동하면 산의 정상에 도달할 수 있다.

Hill-Climbing Algorithm

1. 먼저 현재 위치를 기준으로 해서, 각 방향의 높이를 판단한다 (노드의 확장) 

2. 만일 모든 위치가 현 위치보다 낮다면 그 곳을 정상이라고 판단한다(목표 상태인지를 체크) 

3. 현 위치가 정상이 아니라면 확인된 위치 중 가장 높은 곳으로 이동한다(후계 노드의 선택)

*순수한 언덕 등반 기법에서는 open과 closed리스트를 사용하지 않음

Local Minima Problem

순수한 언덕 등반 기법은 오직 h(n) 값만을 사용한다 (open 리스트나 closed 리스트도 사용하지 않는다

만약 평가함수 h(n) 값을 낮추는 방향으로 진행한다고 가정할 때,
▪ 이 방법에서는 생성된 자식 노드의 평가함수 값이 부모 노드보다 더 높거나 같은 경우가 나올 수 있다. 이때는 평가 함수 값을 낮추는 방향으로 진행하는 것이 불가능함 => 지역 최소 문제(local minima problem)라고 한다.

10. 최고 우선 탐색

Best-First Search

Hill-climbing 기법을 약간 개선한 방법
평가함수도 활용하지만 open/closed 리스트도 함께 사용
Blind search와의 차이
▪ Open 리스트에서 다음에 처리할 노드를 선택할 때 기계적인 순서가 아니라 가장 유망한 노드를 선택
▪ 즉, open 리스트에 속한 노드 중 평가 함수의 값이 가장 좋은 노드를 먼저 처리
Hill-climbing과 비교
▪ Hill-climbing 알고리즘에서는 생성된 자식 노드들을 저장하지 않아서 한번 선택되지 않으면 다시는 고려되지 않는다 

▪ 반면에 best-first search에서는 open 리스트를 사용하기 때문에 현재 선택되지 못한 노드들도 다음에 선택될 가능성 있다

 

11. A* 알고리즘

A* Algorithm

Best-first search와 유사

• 다만 평가 함수의 값을 다음과 같은 수식으로 정의한다.
       f(n) = g(n) + h(n) 
      ▪ h(n): 현재 노드에서 목표 노드까지 차이
      ▪ g(n): 시작 노드에서 현재 노드까지의 경로 비용
  최소 비용 경로를 return