#2-1 - 탐색과 최적화

오늘 배울 것.
상태공간과 탐색, 맹목적 탐색, 휴리스틱 탐색

1. 상태 공간과 탐색

탐색

• 문제의 해가 될 수 있는 것들의 집합을 공간으로 간주하고
• 문제에 대한 최적의 해를 찾기 위해 공간을 체계적으로 찾아보는 것

해

• 초기상태에서 목표상태로의 경로

탐색 문제 예시)

• 식인종 강건너기 문제
• 8-퍼즐 문제
• 틱-택-토

상태

• 특정 시점에 문제의 세계가 처해있는 모습

세계

• 문제에 포함된 대상들과 이들의 상황을 포괄적으로 지칭

상태 공간

• 문제 해결과정에서 초기 상태로부터 도달할 수 있는 모든 상태들의 집합
• 문제의 해가 될 가능성이 있는 모든 상태들의 집합
• 초기상태
  • 문제가 주어진 시점의 시작상태
• 목표상태
  • 문제에서 원하는 최종상태

상태공간 그래프

• 상태공간에서 각 행동에 따른 상태의 변화를 나타낸 그래프
  • 노드 : 상태
  • 엣지 : 행동
• 일반적인 문제는 상태공간이 매우 큼
  • 미리 상태 공간 그래프 만들기 어려움
  • 탐색과정에서 그래프 생성

2. 맹목적 탐색

정해진 순서에 따라 상태공간 그래프를 점진적으로 생성해 가면서 탐색하는 방법

깊이 우선 탐색(DFS)

• 초기 노드에서 시작하여 깊이 방향으로 탐색
• 목표노드에 도달하면 종료
• 더 이상 진행할 수 없으면, 백트랙킹(다시 뒤로)
• 방문한 노드는 재방문 X
• 8-퍼즐 문제의 DFS
  • 루트 노드에서 현재노드까지 경로 하나만 유지
    

너비 우선 탐색(BFS)

• 초기 노드에서 시작해 모든 자식노드를 확장

• 목표 노드가 없으면 단말노드에서 다시 자식 노드 확장

• 메모리 관전에서 부담됨 -> 메모리를 안지우고 계속 확장하기 때문

• 8-퍼즐 문제의 BFS

  • 전체트리를 메모리에서 관리
    

반복적 깊이심화 탐색

깊이 한계가 있는 깊이 우선 탐색(DFS)을 반복적 적용

양방향 탐색

초기 노드와 목적 노드에서 동시에 너비 우선 탐색 진행

• 중간에 만나도록 해서 초기 노드에서 목표 노드로의 최단 경로를 찾는 방법

맹목적 탐색 방법 비교

• 깊이 우선 탐색
  • 메모리 공간 사용 효율적
  • 최단 경로 해의 탐색 보장 불가
• 너비 우선 탐색
  • 메모리 공간 사용 비효율
  • 최단 경로 해의 탐색 보장
• 반복적 깊이심화 탐색
  • 메모리 공간 사용 비효율적
  • 최단 경로 해의 탐색 보장
  • 맹목적 탐색 적용 시 우선 고려 대상
  • 비효율성
    • 실제 비용이 크게 늘지 않음
    • 너비 우선 탐색 대비 11% 정도 추가 노드 생성

3. 정보이용 탐색

휴리스틱 탐색

시간이나 정보가 불충분하거나, 굳이 합리적인 판단을 할 필요가 없는 상황에서 신속하게 어림짐작 하는 것
예시)

• 최단경로 문제

현재 위치에서 목적지까지의 직선거리

• 8-퍼즐 문제

제자리에 있지 않을 타일의 개수

언덕 오르기 방법

• 현재 노드에서 휴리스틱 평가값이 가장 좋은 이웃 노드 하나를 확장해 가는 탐색 방법
• 국소 최적해에 빠질 가능성
• 지역탐색, 휴리스틱 탐색이라고도 부름

최상 우선 탐색

• 확장 중인 노드들 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색
• 남은 거리를 정확히 알 수 없음 -> 휴리스틱 사용

빔 탐색

• 휴리스틱에 의한 평가값이 우수한 일정 개수의 확장 가능한 노드만을 메모리에 관리하면서 최상 우선 탐색을 적용

A* 알고리즘

추정한 전체 비용 f^(n)을 최소로 하는 노드를 확장하는 방법

• f(n) : 노드 n을 경유하는 전체 비용
  • g(n) : 현재 노드 n까지 이미 투입된 비용
  • h(n) : 목표 노드까지의 남은 비용
  • f(n) = g(n) + h(n)
• h(n) : 남은 비용의 정확한 예측 불가
  • h^(n) : h(n)에 대응하는 휴리스틱 함수
• f^(n) : 노드 n 을 경유하는 추정 전체 비용
  • f^(n) = g(n) + h^(n)