• 분기한정 알고리즘은 되추적 알고리즘을 개선한 것
• 설계 전략
  • 상태공간트리를 사용하여 문제를 푼다는 사실이 되추적과 매우 비슷함
  • 차이점: 트리 횡단방법에 구애받지 않음, 최적화문제를 푸는데 만 쓰임
  • 어떤 마디가 유망한지를 결정하기 위해서 그 마디에서 수를 계산함
    • 이 수는 그 마디 아래로 확장하여 구할 수 있는 해답 값의 한계를 나타냄
    • 그 한계값이 그때까지 찾은 최고 해답 값보다 더 좋지 않으면 그 마디는 유망하지 않다, 그렇지 않으면 그 마디는 유망함

최적값은 문제에 따라 최대값이 될 수도 있고, 최소값이 될 수도 있기에 여기서 “좋다”라는 문제에 따라서 더 작다는 의미도 되고 더 크다는 의미도 됨.

되추적 알고리즘의 경우와 마찬가지로 분기한정 알고리즘은 최악의 경우 보통 지수시간임. 그러나 큰 사례에서 매우 효율적일 수가 많음

되추적 알고리즘은 분기한정을 사용하여 얻을 수 있는 장점을 제대로 살리지 못함

• 어떤 마디가 유망한지를 결정하기 위해 한계값을 사용하는 것 외에도 유망한 마디들의 한계값을 비교하여 그 중에서 가장 좋은 한계값을 가진 마디의 자식마디를 방문함
• → 이렇게 하면 미리 정한 순서대로 마디를 방법론적으로 방문하는 것보다 더 빨리 최적해에 도달할 수 있음
• → 이 방법을 분기한정 가지치리 최고우선 검색이라고 함
• → 분기한정 가지치지 너비우선검색이라고하는 또 다른 하나의 방법론적인 접근법을 간단히 수정하여 구현할 수 있음

따라서 비록 깊이우선검색에 비해서 이점은 없지만 너비우선검색으로 0-1배낭 채우기 문제를 풀어봄. 이렇게 하면 최고우선검색을 더 쉽게 설명할 수 잇고, 이를 이용하여 0-1배낭 채우기 문제를 품.

너비우선검색을 복슴.

• 트리의 경우 너비우선검색은 뿌리마디를 먼저 방문하고, 다음에 수준 1의 마디를 모두 방문, 다음에 수준 2의 마디를 모두 방문, … 왼쪽에서 오른쪽으로 진행하는 경우 트리의 너비우선검색을 함

→ 마디들은 방문하는 순서대로 번호가 매겨짐

깊이우선검색과 달리 너비우선검색을 하는 재귀 알고리즘은 작성하기 어려움… 그러나 대기열을 사용하여 아래 알고리즘과 같은 방시긍로 구현할 수 있음

• enqueue 라는 프로시저로 대기열의 뒤에 아이템을 붙여 넣고