제14강 해 탐색 알고리즘 (분기한정, 0/1배낭 문제, 외판원문제)

8.2 분기한정 알고리즘

 

8.2.1 분기한정 branch-and-bound  기법의 원리

최적화 문제에 대한 상태 공간 트리에서 해를 찾아 다닐 때,

노드마다 한정값을 계산하여 이 값이 조건을 벗어나는 노드는 무시하고,

다음 번 탐색 대상 노드는 매 시점마다 가장 좋은 한정값을 갖는 노드로 선택

- 한정값 -> 상한, 하한, 또는 둘다

 

>전체적인 처리 과정

(과정1)루트 노드를 집합에 추가 

(과정2)집합에서 가장 좋은 한정값을 갖는 노드를 현위치 노드로 지정 

(과정3)현위치 노드의 한정값이 중간 최적해보다 더 나은 해를 가질 수 없다면 
         중간 최적해를 최적해로 출력한 후 종료 

(과정4)현위치 노드가 중간 최적해보다 더 좋은 경우 중간 최적해를 현위치 노드로 변경

(과정5)현위치 노드(리프 노드가 아니라면)의 각 자식 노드에 대해 한정값을 계산한 후,

         중간 최적해보다 더 나은 해를 가질 수 있는 것만 집합에 추가

(과정6)집합이 비어 있지 않으면 (과정2)로 가서 반복

 

 

8.2.2 0/1 배낭 문제

(1) 개념과 원리

최대가 되는 물체의 이익의 합을 구하는 문제

 - Ssum → 현재까지 선택한 물체의 무게의 합

 - Psum → 현재까지 선택한 물체의 이익의 합 

 - Fsum → " 각 노드의 한정값 "

    → 현재 남은 용량에 앞으로 고려할 물체를 쪼개어 넣을 수 있을 때 배낭의 최대 이익 

    - 남은 물체를 쪼개지 않고 넣었을 때 배낭의 최대 이익의 상한

 

> 중간 최적해 Max를 업데이트하기 위한 조건

  -  노드의 Ssum <=Mand현재까지 찾는 해 Max<Psum

> 중간 최적해 Max보다 더 나은 해를 가질 수 있는 조건 

  -  노드의 Ssum <=M and Fsum >Max

     - Fsum <=Max→ 해당 노드를 탐색하더라도 더 좋은 해는 존재하지 않으므로 더 이상의 탐색은 불필요

 

(3) 성능 분석 -> O(2^n)

- 레벨 i인 노드의 Fsum 계산 → O(n-i)시간

- 레벨 i의 최대 노드의 개수 → 2^i

>>>> 지수시간을 갖는다

 

(4) 특징 

- 되추적 알고리즘보다 탐색하는 노드의 수를 줄여줄 수 있다. 

   - 항상 최선의 노드를 우선적으로 탐색하므로 빠르게 최적해에 다가가고, 

      그에 따라 새로운 노드가 집합에 추가되는 조건도 까다로워서 탐색 대상 노드 수를 많이 줄일 수 있다.

 

 

 

 

8.2.3 외판원 문제

 

(1) 개념과 원리

여러 도시가 주어지고 도시 사이를 이동할 때 필요한 비용이 주어진 경우,최소의 비용으로 모든 도시를 한 번씩만 방문하고 처음 도시로 돌아오는 방법을 찾는 문제

- 모든 도시 사이에 직접 이동이 가능하다고 가정

-  G=( V,E ) ,| V| = n, |E| = n(n-1)/2로 주어지는 외판원 문제의 해 

> 외판원 문제의 상태 공간 트리

-  레벨 i → 정점 A로부터 i개의 간선으로 서로 다른 정점 ( i+1 )개를 연결한 경로

-  외판원 문제의 해 → 레벨 n-1에서 형성된 경로의 마지막 정점에서 정점 A로의 간선만 추가 

   : 최적해 → 가능한 모든 해 중에서 간선의 가중치의 합이 가장 작은 것

- 실제 상태 공간 트리에서는 레벨 n-2까지만 고려하면 됨

   :  레벨 n-2인 노드는 자식 노드가 하나밖에 없으므로

 

> 각 노드의 한정값 Msum 

 - 레벨 0인 노드의 한정값 

  → 각 정점마다 연결된 간선들 중

   가중치의 최솟값을 골라 모두 더한 값 

 - 이 값은 최적해보다 클 수 없다. 

 

- 레벨 k인 노드의 한정값 

→ k개의 정점에서 출발하는 결정된 간선의 가중치의 합 + 나머지 n-k개의 정점에 대해 

각 정점에서 연결된 간선들 가중치의 최솟값의 합 

 

1. 레벨 k에서 선택되어 추가된 k+1번째 정점은 

이에 연결된 간선 중 레벨 0부터 레벨 k-1까지 

결정된 k개의 정점과 연결된 간선을 제외한 후 간선들 가중치의 최솟값을 구하고,

  2. 나머지 n-k-1개의 정점은 이에 연결된 간선 중 레벨 1부터 레벨 k까지 

결정된 k개의 정점과 연결된 간선을 제외한 후 최솟값을 구한다.

 

> 중간 최적해 Min을 업데이트하기 위한 조건

 -  레벨 n-2인 노드의 Msum <현재까지 찾은 해 Min

 

> 중간 최적해 Min보다 더 나은 해를 가질 수 있는 조건 

 - 노드의 Msum <Min(레벨 n-2가 아니어도 무방) 

   :  Msum >=Min→ 해당 노드를 탐색하더라도 더 좋은 해는 존재하지 않으므로 더 이상의 탐색은 불필요

 

(3) 성능분석 -> O(2^n)

-  각 노드에서 처리 시간 → Msum 계산 O(n)

- 탐색하는 노드의 수(최악의 경우)→ O(2^n)