ALGORITHM/Branch-and-Bound1 Branch-and-Bound 수업 필기 2. Branch-and-Bound(분기한정법): '최적의 경우'를 찾는 알고리즘으로써, '최소한 이정도는 되어야 답이 될 가능성이 있다'라는 범위(bound)를 정해두고 범위를 벗어나는 값들은 가지치기(Branch)해가며 결과값을 추적한다. branch-and-bound 알고리즘의 원리 - 각 노드를 검색할 때 마다, 그 노드가 promising한지의 여부를 결정하기 위해서 한계값(bound)을 계산한다.- 그 bound는 그 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계를 나타낸다.- 따라서 만약 그 bound가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어서 검색을 계속할 필요가 없으므로, 그 노드는 non-promising 할 수 있다. 3. O.. 2018. 12. 17. Prev. 1 Next.