알고리즘 분기한정(Branch and Bound)

 

●분기한정(Branch and Bound)

- 백트래킹과는 달리, 분기와 한정을 정해서 해를 구하는 기법이다. 백트래킹을 구현할 때 경우의 수가 너무 많아 모든 경우를 다 해보기 어려울 때, 사용하면 좋다. 가지치기하는 기준이 되는 값이 바운드 값이다. 너비우선탐색을 사용한다.

 

●너비우선탐색(BFS, Breadth First Search)

- 반복문과 큐를 이용하여 구현한다. 경로가 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다. DFS 보다 많은 자료를 처리할 경우에 적합한다.

 

●큐(queue)

-  먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조이다.

 

●BFS기법

- 시작점과 연결된 모든 정점을 방문한다.

- 시작점과 연결된 모든 정점을 방문 후 시작점과 연결된 가장 가가운 정점을 방문한다.

- 방문한 정점과 연결도니 모든 정점 중 방문하지 않은 정점을 모두 방문한다.

- 위 과정을 계속 반복한다.

- 모든 정점을 모두 방문하면 탐색을 종료한다.