Skip to content

Latest commit

 

History

History
203 lines (181 loc) · 10.6 KB

chap02.md

File metadata and controls

203 lines (181 loc) · 10.6 KB

CHAP 02

  • 탐색 != 탐방

    • 탐색: 목표치를 찾으면 탐색을 종료함
    • 탐방: 방문할 수 있는 노드는 모두 방문하고 종료함

  • 알파고는 딥러닝, 탐색 기법 통해 수를 읽음. (몬테카를로 트리 탐색)

상태(state), 상태공간(state space), 연산자

  • 탐색(search)는 상태공간에서 시작상태에서 목표상태까지의 경로를 찾는 것
  • 상태공간 (state space): 상태들이 모여 있는 공간
  • 연산자: 다음 상태를 생성하는 것
  • 초기상태: 처음에 주어진 상태
  • 목표상태: 말그대로 목표상태임
  • ex> 8-puzzle에서의 연산자
    • 빈칸이 움직인다고 생각 -> 4개의 연산자 (아니면 32개의 연산자가 생겨버림..)

경로 찾기 문제 예시

  • 트리가 아님! (왜? : 경로들이 유일하지 않음. A에서 C로 가는 경로가 유일하지 않음 등..)
  • 상태?
    • 초기 상태: A
    • 목표 상태: F
    • List로 표현 가능 : 초기상태 (A) 에서 목표상태 (A...F)
  • 연산자?
    • 가능한 경로 중 하나의 경로를 선택하는 것

N-queen 문제

  • 8-queen 문제는 8x8 체스판에 두 개의 퀸이 서로를 위협하지 않도록 8개의 퀸을 배치하는 문제
  • 상태?
  • 연산자?
    • place_i 연산자는 새로운 퀸을 i번째 행에 배치한다.
    • 연산자 집합 O = { place_i | 1<=i<=8 }

탐색 트리

  • 상태 = 노드 (node)
  • 초기 상태 = 루트 노드
  • 연산자 = 간선(edge)
    • 연산자 적용하기 전까지는 탐색 트리는 미리 만들어져 있지 않음.
  • ex> 출발 도시에서 목표 도시까지의 경로 탐색
    • 확장이 끝난 노드 (닫혀있는 노드, 방문한 노드)
    • 열려 있는 노드 (생성되었지만 아직 확장되지는 않은 노드, 아직 방문x 노드): 선택할 수 있는 노드들.

기본적인 탐색 기법

  • ppt 19 그림을 참고
  • 맹목적인 탐색(Blind search method): 목표 노드에 대한 정보를 이용하지 않고 기계적인 순서로 노드를 확장하는 방법. 매우 소모적인 탐색.
    • 깊이 우선 탐색 (DFS)
    • 너비 우선 탐색 (BFS)
    • 균일 비용 탐색
  • 경험적인 탐색(heuristic search method): 목표 노드에 대한 경험적인(heuristic) 정보를 사용하는 방법. -> 효율적인 탐색이 가능!
    • 탐욕적인 탐색 (greedy)
    • A* 탐색

탐색 성능 측정

  • 완결성(completeness): 문제에 해답이 있다면, 반드시 해답을 찾을 수 있는지
  • 최적성(optimality): 가장 비용이 낮은 해답을 찾을 수 있는지 여부
  • 시간 복잡도(time complexity): 해답을 찾는데 걸리는 시간
  • 공간 복잡도(space complexity): 탐색을 수행하는 데 필요한 메모리의 양
    • b: 탐색 트리의 최대 분기 계수
    • d: 목표 노드의 깊이 depth
    • m: 트리의 최대 깊이

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

  • 탐색 트리 상에서, 해가 존재할 가능성이 존재하는 한, 앞으로 계속 전진하여 탐색하는 방법
  • ex>8-puzzle
    • 0이면 빈칸으로 간주. 빈칸이 움직인다고 봄.
    • 방문한 노드들: closed list에 저장
  • 의사코드 
    function DFS(root)
    open <- [root]
    closed <- [] //빈 리스트
    while open != [] do 
        X <- open 리스트의 첫번째 요소 
        if X == goal then return SUCCESS
        else 
            X의 자식 노드를 생성
            X를 closed 리스트에 추가 
            X의 자식 노드가 이미 open이나 closed에 있다면 버린다
            남은 자식 노드들은 open의 처음에 추가한다 (스택처럼 사용)
    return FAIL
  • ex> ppt 26 참고

OPEN 리스트와 CLOSED 리스트

  • 탐색에서 중복된 상태 막기 위해 2개 리스트 사용
    1. OPEN 리스트(frontier): 확장은 되었으나 아직 탐색하지 않은 상태들이 들어있는 리스트, 다음 번에 선택(탐색)할 수 있는 노드들
    2. CLOSED 리스트(reached 리스트): 탐색이 끝난 상태들이 들어있는 리스트

DFS 분석

  • 완결성?: 무한 상태 공간에서는 DFS는 무한 경로를 따라 끝없이 내려갈 수 있음. -> 무한 상태 공간에서는 완결적이지 X
  • 시간 복잡도?: O(b^m)
    • b는 분기 계수.
    • **m(트리 최대 깊이)**이 **d(정답의 깊이)**보다 아주 크다면 시간이 많이 걸림. (그렇지 않은 경우 bfs보다도 빠를 수 있음.)
  • 공간 복잡도? : O(bm)
    • open list의 노드들이 b개씩 m개. 선형적으로 늘어나고 있음 -> 선형 복잡도만을 가짐.
    • 탐색 트리에서 한 줄 단위로 탐색하므로 모든 노드들을 저장하고 있을 필요 x -> bfs에 비해 장점
  • 최적성? : 가장 경로가 짧은 최적의 해답은 발견 x. 가장 **왼쪽(leftmost)**에 있는 해답만을 발견함.

BFS(너비 우선 탐색; Breadth-First Search)

  • 루트 노드의 모든 자식 노드들을 탐색한 후에 해가 발견되지 않으면 한 레벨 내려가 동일한 방법으로 탐색 계속하는 방법
  • 의사코드 
    function BFS(root)
    open <- [root]
    closed <- [closed]
    if X == goal then return SUCCESS
    else 
        X의 자식 노드를 생성
        X를 closed 리스트에 추가 
        X의 자식 노드가 이미 open이나 closed에 있다면 버림
        나머지 자식 노드들은 open의 끝에 추가 (큐처럼 사용)
    return FAIL
  • ex> ppt 31 참고

BFS 분석

  • 완결성?: 분기 계수 b가 유한하다면 너비 우선 탐색은 반드시 해답을 발견할 수 있음
  • 시간복잡도, 공간복잡도: O(b^d)
    • 노드들이 메모리 상에 있어야 하므로 시간 복잡도와 공간 복잡도는 모두 지수 복잡도가 됨.
    • 가장 가까운 정답 발견 가능, 그러나.. 간단한 문제가 아니라면 천문학적인 시간과 메모리 공간이 필요됨

깊이 제한 탐색(Deep-Limited Search)

  • DFS의 단점을 보완하여 깊이를 제한하는 방법.
    • DFS는 메모리 소모도 작고 빠르게 답을 찾아줄 수 있으나 한번 잘못된 경로로 빠지면 나오지 못할 수 있음
  • 기본적인건 dfs와 같으나, 끝까지 깊이 들어가지 않고 어떤 한계를 정해서 그 깊이 이상은 탐색하지 않고 **백트랙킹**하는 것
  • IDDFS(Iterative Deepening DFS)
    • 한계 깊이를 1,2,3,4 ... 차례대로 늘려가며 깊이 제한 탐색을 진행. 목표를 찾을 때까지 제한 깊이를 늘려가며 탐색
    • 의사 코드 
      function IDDFS(root)
    for depth from 0 to inf do
        found, remaining <- DFS(root, depth)
        if found != null then
            return found
        else if not remaining then
            return NULL
    • 장점:
      • 깊이 우선 탐색의 공간 효율성과 너비 우선 탐색의 완전성 결합.
      • 해답이 존재하는 경우, 가장 적은 비용을 갖는 경로 찾음
      • 여러번 동일한 노드를 방문하기 때문에 낭비처럼 보일 수도 있으나.. 탐색 트리에서는 대부분의 노드가 하위 수준에 있으므로 비용이 생각보다 많이 들지 않음
      • 알고리즘의 응답성 향상 : 초기 반복에서는 적은 수의 노드를 사용하기 때문에 매우 빠르게 실행됨. 알고리즘은 초기 결과를 빠르게 제공 가능 => 프로그램이 지금까지 완료한 탐색에서 찾은, 최고의 결과로 언제든지 작업 수행 가능

경험적인 탐색 방법 (heuristic search method)

  • 문제 영역에 대한 정보나 지식 사용하여 탐색 작업을 빠르게 하는 것
  • 휴리스틱 정보(heuristic information): 이때 사용되는 정보
  • 8 puzzle에서 휴리스틱
    • 현재 제 위치에 있는 타일의 개수(h1(N)), 각 타일의 목표 위치까지의 거리(h2(N)) 정보 사용됨

언덕 등반(Hill Climb) 기법

  • 평가 함수(h(N))의 값이 좋은 노드 먼저 처리
    • 제 위치에 있지 않은 타일의 개수 사용 (함수 값이 더 작은걸 선택하여 탐색해나감- 0이 되면 가장 좋은거)
      • h(n) 평가함수 역수를 취하면 올라가는 형태 (함수 값이 큰걸 선택해야하는 것). 여기에서는 내려가는 방식이 되도록 평가함수를 만들었음.
  • 의사 코드 
    function HILL_CLIMBING(root)
    current <- root
    loop do
        현재 노드의 자식노드들을 생성
        neighbor <- 평가함수 값이 가장 높은 자식 노드 
        # 만약 모든 위치의 값보다 현재 위치의 값이 크다면 현재 위치가 정상
        if VALUE(neighbor)<=VALUE(current) then
            return current
        # 현위치가 정상이 아니라면 확인된 위치 중 가장 높은 곳으로 이동
        current <- neighbor
  • 변수가 몇개 있느냐에따라 평가함수가 달라짐. (ex. 제 위치와의 거리..등)
  • 찾아야하는 것: global maxima(or minima)
  • 언덕 등반 기법과 descendant gradient 바꾼것
  • 언덕 등반 기법 알고리즘
    • neighbor: 평가 함수값이 가장 높은 자식 노드
    • open, closed 리스트를 사용하지 x (굳이 노드를 다시 방문할 일이 없다. 더 좋은게 있으면 나머지를 버리고 계속 내려가기 때문)

지역 최소 문제

  • 지역 최소 문제(local minima problem): 평가함수 값이 부모 노드보다 더 높거나 같은 경우
  • 순수한 언덕 등반 기법은 오직 h(n)만 사용. (open,closed 리스트 사용x)
  • 해결방법: 몇 칸 더 가보기

A* 알고리즘

  • 평가함수 f(n)=g(n)+h(n)
    • h(n): 현재 노드~목표 노드까지의 거리
    • g(n): 시작노드~현재 노드까지의 비용
  • 더 좋은 것을 선택하기 때문에 open 리스트 필요
  • 의사코드 
    AStar_Search()

open<-[시작노드]
closed<-[]
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)을 계산. 자식노드들을 open에 추가
return FAIL