2019-11-28 목요일

알고리즘

종만북

조합탐색

• 완전탐색이 기본 뼈대. 이 후, 여러 최적화 기법으로 답을 찾는다.
• 핵심은 가지치기
  1. 현재까지의 최선의 답을 이용해 가지치기
  2. 휴리스틱 함수를 이용하여 가지치기
     • 남은 경로로 답을 구성했을 때, 최선의 답의 후보가 될 수 있는지?
       - 비관적, 낙관적 휴리스틱
       - MST
  3. 탐욕법으로 탐색시작
     • 좋은 답이 빨리 나올 수록 가지치기가 더 효율적
  4. 현재까지의 경로를 가지치기
     • 현재까지 지나온 경로에 간단한 조작을 했을 때, 더 좋은 값이 나오면 탐색 중단
  5. 마지막단계 메모이제이션
     • 조합탐색은 크기가 커서 DP를 활용못할 때 사용
       • 마지막 단계에서 메모이제이션을 하면 효율이 극대화
       • 단, 가지치기로 인해 메모이제이션이 하기가 힘드므로 DP함수를 따로 구현하고, 일정한 값부터는 DP함수로 탐색을 구현
       • 보통 메모이제이션되는 값이 작을 것이므로 map을 활용한 캐시도 고려할만 하다.