분기한정법이란? 분기한정 설계전략은 상태공간트리를 사용해 문제를 푼다는 사실이 되추적과 매우 비슷하다. 차이점으로 분기한정법은 (1) 트리 횡단방법에 구애받지 않고, (2) 최적화 문제를 푸는데만 쓰인다. 분기한정 알고리즘은 어떤 마디가 유망한지를 결정하기 위해서 그 마디에서 수(한계값)를 계산한다. 이 수는 그 마디 아래로 확장해 구할 수 있는 해답의 한계(bound)를 나타낸다. 그 한계값이 그때까지 찾은 최고 해답값보다 더 좋지 않으면 그 마디는 유망하지 않다. 최적값은 문제에 따라서 최대값이 될 수도 있고, 최소값이 될 수도 있으므로 여기서 "좋다"란 문제에 따라서 더 작다는 의미도 되고 더 크다는 의미도 된다. https://kimmessi.tistory.com/74?category=871925..