4개의 댓글이 있습니다.

• 
  hyunhwan

  우선 백트래킹 \in$\in$ 조합탐색이라고 보시는게 맞을 것 같습니다.

  조합탐색(combinatorial search)는 문제에 대한 가능한 해법을 헤아리는 것을 뜻하는 것입니다. 백트래킹 역시 가능한 해법 중에 가장 적합한 것을 찾기 위한 방법이기 때문에 조합탐색에 포함된다고 볼 수 있습니다. 다만, 백트래킹의 경우에는 가능한 경우를 찾거나, 현 상태에서 더이상 탐색을 하더라도 답을 찾지 못하는 경우로 간주될 경우 퇴각(back-track)을 하는 탐색법을 뜻합니다.

  자세한 내용은 다음의 링크를 한번 참고해보시는 것이 좋을 것 같습니다.

  • https://en.wikipedia.org/wiki/Combinatorial_search
  • https://en.wikipedia.org/wiki/Backtracking

  
  9년 전 link

• 
  Laplace

  그렇다면 가지치기나 휴리스틱을 사용하는 경우가 백트래킹을 수행하는 하나의 예가 될 수 있는건가요?

  
  9년 전 link

• 
  JongMan

  조합 탐색은 꼭 백트래킹으로 구현할 필요가 없겠죠? TSP 문제를 next_permutation으로 O(n!)을 전부 탐색하게 만들어도 조합 탐색 알고리즘입니다.

  백트래킹은 실제로는 최적화 문제가 아니라 제약 충족 문제에 국한된다는 인상이 좀 있는데요 (실제로도 그런 것 같고) 그러니 특정 조합 탐색 문제를 푸는 특정 알고리즘의 형태를 지칭한다.. 라고 생각하시면 될 것 같네요.

  
  9년 전 link

• 
  Laplace

  두분 다 답변 정말 감사합니다. ^^

  
  9년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.