탐색

알파고가 수를 읽은 방법 : 딥러닝과 "탐색 기법"

탐색

• 탐색 문제의 구성요소들을 이해한다
• 탐색 알고리즘의 동작원리를 설명할 수 있다.
• 여러가지 탐색 기법에 대해 설명할 수 있다.
• 탐색 알고리즘을 길찾기 문제에 응용해본다.

상태, 상태공간, 연산자

탐색 : 시작 상태에서 목표 상태까지의 경로를 찾는 과정

• 탐색은 인공지능적 문제 해결에서 주요한 수단
• 인간의 지적 문제해결 방식중의 하나
• 현재 많이 사용되고 있는 탐색은 길찾기, 최단 경로 찾기 등이 있다.

탐색문제 : 다음과 같이 graph로 표현

[N,A,S,G]

• N : nodes(states)
• A : arcs(operations), 연산자 : 다음 상태를 생성하는 동작
• S : start state
• G : goal state

 

상태공간 : 상태들이 모여 있는 공간

 

예시 : 8-puzzle 문제

	1	3
5	7	9
2	4	8

초기 상태

1	2	3
4	5	6
7	8

goal

 

operator : {move blank}

state space가 크고 경우의 수가 커서 탐색트리로 연산한다.

탐색트리

• 상태 = 노드( node)
• 초기 상태 = 루트 노드
• 연산자 = links or edges

기본적인 탐색 기법

1. 탐색 알고리즘
   1. 맹목적 탐색
      1. 깊이 우선 탐색
      2. 너비 우선 탐색
      3. 깊이 우선 탐색과 너비 우선 탐색
      4. 균일 비용 탐색
   2. 경험적인 탐색 경험적인 탐색 방법
      1. 탐욕적인 탐색 : Greedy 탐색
      2. A* 탐색 A* 알고리즘

깊이 우선 탐색과 너비 우선 탐색

• 두 탐색 방법 모두 정보를 이용하지 않음.
• 8-puzzle에서의 예시
  •  
• OPEN과 CLOSED 리스트
  • 탐색 알고리즘에서는 중복된 상태를 막기 위하여 다음과 같은 2개의 리스트를 사용한다.
  • OPEN리스트 : 확장은 되었으나 아직 탐색하지 않은 상태들이 들어있는 리스트
  • CLOSED 리스트 : 탐색이 끝난 상태들이 들어있는 리스트
• 깊이 우선 탐색(DFS)
  • 알고리즘
    • 스택 FILO(first in last out)

depth_first_search()
open<-[시작노드]
close <-[]
while open !=[]do
	X<-open 리스트의 첫 번째 요소
	if x== goal then return SUCCESS
	else
		X의 자식 노드를 생성
		X를 closed 리스트에 추가
		X를 자식 노드가 이미 open이나 closed에 있다면 버림
		남은 자식 노드들은 open의 처음에 추가(스택처럼 사용
return FAIL

• 너비 우선 탐색(BFS)
  • 알고리즘

depth_first_search()
open<-[시작노드]
close <-[]
while open !=[]do
	X<-open 리스트의 첫 번째 요소
	if x== goal then return SUCCESS
	else
		X의 자식 노드를 생성
		X를 closed 리스트에 추가
		X를 자식 노드가 이미 open이나 closed에 있다면 버림
		남은 자식 노드들은 open의 맨 뒤에 추가(큐처럼 사용
return FAIL

 

경험적인 탐색 방법

• 탐색 알고리즘의 문제점 : 정보나 지식을 전혀 이용하지 않음
  • → Informed search 필요
  • DFS → open list 사이즈가 작다. 운이 좋으면 빨리 찾기 가능하다. 동일한 값 중 긴 것을 찾는 방식에 유리하다.
  • BFS → open list가 크다 stack overflow가 커진다. 최적의 해를 찾는 편이며 시간이 길게 걸리는 편이다.
• 문제 영역에 대한 정보나 지식을 사용할 수 있다면 탐색 작업은 효율적이 될 것임
• Imformed search 혹은 경험적 탐색 방법(heuristic search method)라고 함
• 이 때 사용되는 정보를 휴리스틱 정보(heuristic information)라고 함
  • 8-puzzle에서의 휴리스틱 예
    • i) h(n) = 현재 제 위치에 있지 않는 타일의 개수
    • ii) h(n) = 각 타일의 목표 위치까지의 거리
• EX) A* 알고리즘

 

언덕 등반 기법 (Hill-climbing)

• 자식 노드중, 평가 함수의 값이 좋은 노드를 먼저 처리하는데 현재 값보다 나쁘면 전진하지 않음
  • 평가 함수로 h1(n)을 사용
  • 정보가 많을 수록 탐색 트리가 날씬하다.
  • O(BFS) 정보를 이용하지 않는다 ≤ h1 ≤ h2 ≤ h* 의 추정치를 따라야한다. 즉 실제 값보다 추정치가 늘 작거나 같아야 한다.
• 알고리즘
  • 1. 먼저 현재 위치를 기준으로 해서, 각 방향의 높이를 판단한다.(노드의 확장)
  • 2. 만일 모든 위치가 현 위치보다 낮다면 그 곳을 정상이라고 판단한다.(목표확인)
  • 3. 현 위치가 정상이 아니라면 확인된 위치 중 가장 좋은 곳으로 이동한다.(자식노드선택)
• 지역 최소 문제(local minima problem)의 문제가 발행한다. 봉착할 수 있다는 뜻

A* 알고리즘

제시한 정보를 이용해서 움직이겠다.

• A* 알고리즘은 평가 함수의 값을 다음과 같은 수식으로 정의
  • f(n)=g(n)+h(n)
  • g(n)=시작노드에서 현재 노드까지의 비용 → 알려진 값
  • h(n)=현재 노드에서 목표 노드까지의 거리(<h*(n)) → 추정값
• 과소 평가(underestimated)된 h(n)을 사용하면 반드시 최적 경로를 찾는다.
• 알고리즘

AStrar_search()

open <- [시작노드]
close <- []
while open != [] do
	x<-open리스트에서 가장 평가 함수의 값이 좋은 노드 (평가 기준이 생략)
	if X == goal then return SUCCESS
	else 
		X의 자식 노드를 생성
		X를 closed 리스트에 추가
		if X의 자식 노드가 open 이나 closed에 있지 않으면
			자식 노드의 평가 함수 값 f(n)=g(n)+h(n)을 계산
					-> 자식이 겹치면 추가 했던 과거와 달리 histroy가 다르면 다른 노드로 판단된다.
			자식 노드들을 open에 추가
		else
			비용 비교 후 replace 해야한다.
				-> 비록 closed에 있어도 다시 해줘야한다.
return FAIL

LAB

1. A* 시뮬레이션

2.경로 찾기 시뮬레이션

 

자세한 사항 : 노션 링크 참조

https://tame-neptune-1a0.notion.site/02-3fe5df03a21348b99f811ae58ed9f67b