# 학습 내용 정리/알고리즘분석(Python)
[알고리즘분석] 5. 분기한정법
분기한정법은 이전 되추적 기법에서 사용했던 상태공간트리와 유망한지 여부를 사용합니다. 되추적은 특정 답을 뽑아내기 위한 방법이었다면, 분기한정법은 최적의 해를 구하는 문제에 사용할 수 있는 방법입니다. 위 사진은 최소화 분기한정법의 대표 사진입니다. 만약 저 팻말이 최소 트래킹 코스 거리를 나타낸다면 (실제 거리 >= 팻말 표시) A를 트래킹했을 때 거리가 200 미만이라면 B를 트래킹 할 필요 없겠죠? 또한 A와 B의 하한이 지금처럼 나와있다면, 당연히 A를 먼저 트래킹하는 것이 유리하겠죠? 생각보다 어렵지 않습니다. 정말요 ^^ 그렇다면 바로 분기한정법에 대해 알아보러 가시죠! 목차 0. 배낭채우기 분기한정법은 영어로 branch and bound입니다. 가지랑 영역? 정도로 해석할 수 있겠네요. 모..
2021. 6. 11. 17:19
최근댓글