11. 조합 탐색

11.1 도입

  • 동적 계획법, 분할 정복 등의 디자인 패러다임은 유용하지만, 모든 문제에 적용할 수는 없다

  • 결국 우리는 시작점인 완전 탐색으로 돌아와 다시 시작할 필요성도 있다

  • 완전 탐색은 대개 답을 만드는 과정을 여러 개의 선택으로 나눈 뒤, 재귀 호출을 이용해 각각의 선택지를 채워가는 형태로 구현됨.

    • 이때 부분 답과 완성된 답의 집합을 탐색 공간(search space) 라고 한다

  • 완전 탐색은 문제의 규모가 조금이라도 클 경우 사용하기 어려운 단점이 있다.

  • 완전 탐색을 포함해, 이렇게 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘을 이 책에서는 조합 탐색(combinatorial search) 라고 한다.

  • 조합 탐색은 많은 최적화 방법이 있지만, 모두 기본적으로 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 탐색할 답의 수를 줄이는 것을 목표로 함

  • 조합 탐색 최적화는 시공간, 입력 형태 등 모두 고려해야 하고, 깊은 식견이 요구됨, 딱히 정답이 없음

  • 조합 탐색 최적화는 크게 두 가지로 분류한다.

    1. 가지치기(pruning): 탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라냄
      • 지금가지 찾아낸 최적해 보다 부분해가 이미 더 나빠졌다면, 현재 상태를 탐색하지 않고 종료
    2. 탐색의 순서 바꾸기, 탐색 시작 전에 탐욕법을 이용해 적당히 좋은 답 찾기, 휴리스틱(경험에 의거한 어림짐작) 을 이용한 가지치기
      • 완전 탐색의 경우 답을 어떤 순서로 찾던 상관 없지만, 가지치기와 함께 사용할 경우, 더 일찍 탐색이 중단 됨으로 탐색의 효율이 높아짐

11.2 조합 탐색 기법들

  • 간단한 휴리스틱을 이용한 가지치기

    • 조합 탐색에서 방문하는 상태의 수는 탐색의 깊이가 깊어질수록 증가, 따라서 ’이 부분에서는 최적해가 나올 수 없다’ 를 빨리 알아내는 것이 유리하다.

  • 메모이제이션

11.3, 11.4 게임판 덮기 2, BOARDCOVER2, 난이도: 하

  • 최적화 문제에서 낙관적인 휴리스틱들은 문제를 과소평가 하는 대신, 과대평가 한다.
  • 휴리스틱 함수를 만드는 쉬운 방법은 블록을 통째로 내려놓아야 한다는 제약을 없애서, 블록들을 한 칸씩 쪼개서 놓을 수 있도록 문제를 변형
    • 우리가 놓을 수 있는 블록의 수: (남은 빈 칸의 수 / 블록의 크기)
    • 이것은 우리가 실제 놓을 수 있는 블록의 수 이상이기에 우리가 얻을 수 있는 답의 상한이 된다.
    • 각 경우에 계산된 상한이 현재 찾은 최적해 이하라면 탐색을 수행할 필요 없다. => 가지치기 수행

Reference