분단탐색법

소개글

2021-2학기 A+받은 레포트입니다. 직접 작성하였습니다.

분단탐색법에 대한 내용과 알고리즘의 타당성에 대한 생각을 정리한 글입니다.

목차

1. 분단탐색법(Brnach and Bound)
2. 알고리즘의 타당성에 대한 생각

본문내용

최적화 문제에서 구하려는 것이 선택들의 모음일 때, 선택의 분기 중에 나쁜 선택을 미리 제거하여 시간 성능을 높인다. 모든 후보해를 체계적으로 늘어놓고 최적화할 수치의 상한(Upper bound)과 하한(Lower bound)을 추정하고, 가망이 없다는 판정(non-Promising)이 나온 해를 제거해 나간다. 상한, 하한을 벗어나는 값들을 제거해 나가며 계산의 양을 점차 줄인다. 분단탐색법은 볼록(Convex) 설계문제에 대해 수렴성이 보장되고 다른 최적화 기법에 비해 강건해 널리 이용되고 있는 기법이다. 탐색을 회피할 수 있는 이유는 회피 영역을 탐색하기 이전의 시점에서 회피 영역의 해들이 결코 최적해를 갖지 않는다는 사실을 알 수 있기 때문이다. 분단탐색법의 효율성(알고리즘의 성능)은 초기 한계 설정값이나 해공간 탐색방법 등에 영향을 받고, 가장 중요하게는 해공간을 제거하는데 사용한 한정함수의 영향을 크게 받는다.

참고 자료

[알고리즘, C++] 분기한정법 (Branch and Bound)[웹사이트]. (2021.11.24.). URL: https://buganddog.tistory.com/m/8
Branch and Bound Algorithm[웹사이트]. (2021.11.24.). URL: https://www.baeldung.com/cs/branch-and-bound
이종학, & 박상근. (2010). 분기한정법 기반의 새로운 전역최적화법: Hot Spot Strategy. 한국 CDE 학회 학술발표회 논문집, 659-665.