BFS (Breadth-First Search)

1. Breadth First Search (너비우선검색)

뿌리마디를 먼저 검색한 후 수준 1에 있는 모든 마디를 검색한다. (왼쪽에서 오른쪽으로)

다음에 수준 2에 있는 모든 마디를 검색한다. (왼쪽에서 오른쪽으로)

Queue(큐)를 사용한다.

      

2. Branch and Bound (분기한정법)

tree를 가로 지르는 특별한 방법을 제한하지 않는다.

최적화 문제에만 사용된다.

- 진행절차

  ㄱ. 한 노드에서 bound(경계)를 계산하여 노드가 유망한 지 판단한다.

  ㄴ. bound는 노드를 넘어 확장하여 얻을 수 있는 솔루션 값이다.

  ㄷ. 그 bound가 지금까지 발견된 최상의 솔루션보다 낫지 않다면, 노드는 유망하지 않다. 그렇지 않으면 유망하다.

3. Breath First Search 예

Traveling Salesperson Problem

세일즈맨의 집이 위치하고 있는 도시에서 출발하여 다른 도시들을 각각 한번씩만 방문하고, 

다시 집으로 돌아오는 가장 짧은 일주여행경로를 결정하는 문제이다.

일주여행경로(Hamiltonian circuits)는 한 정점을 출발하여 다른 모든 정점을 한번씩만 거쳐서

다시 그 정점으로 돌아오는 경로이다.

여러 개의 일주여행경로 중에서 길이가 최소가 되는 경로를 찾는 것이 Traveling Salesperson Problem이다.

            

 ** Bound

 :  [1 ... k]의 여행경로를 가진 노드의 한계치 

   A = V - [1 ... k]라 가정할 때,

     (1) 경로 [1...k]의 길이 

  + (2) 로부터 A에 속한 정점으로 가는 이음선 길이 중 최소치

  + (3) 로부터 에 속한 정점으로 가는 이음선 길이 중 최소치