반응형 분기한정1 알고리즘 분기한정(Branch and Bound) ●분기한정(Branch and Bound) - 백트래킹과는 달리, 분기와 한정을 정해서 해를 구하는 기법이다. 백트래킹을 구현할 때 경우의 수가 너무 많아 모든 경우를 다 해보기 어려울 때, 사용하면 좋다. 가지치기하는 기준이 되는 값이 바운드 값이다. 너비우선탐색을 사용한다. ●너비우선탐색(BFS, Breadth First Search) - 반복문과 큐를 이용하여 구현한다. 경로가 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다. DFS 보다 많은 자료를 처리할 경우에 적합한다. ●큐(queue) - 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조이다. ●BFS기법 - 시작점과 연결된 모든 정점을 방문한다. - 시작점과 연결된.. 2012. 4. 9. 이전 1 다음 반응형