ch 4. 탐욕적 접근법 (greedy approach)

• 다이나믹 프로그래밍의 단점 --> 인스턴스를 더 작은 인스턴스로 쪼개어 재귀적으로 무제 해결
• 최적화 문제를 푸는데 적합. 최적화 원칙이 적용되는지를 점검해보기만 하면 됨
• 그러나 때로는 불필요하게 복잡. 0-1 Knapsack 해결 가능.
  
  
• ★ 탐욕적 접근법: 해당 단계에서 최적의 해를 구함 (locally optimal) 
• 결정해야 하는 단계마다 최적의 해를 구하여, 최종적으로도 해답에 도달하고자 함
• 허나, 반드시 local에서의 최적의 해가 global 에서의 최적의 해라고 보장할 수 없음
  (항상 최적의 해답인지 검증이 필요함)
• 최적화 문제를 푸는데 적합. 알고리즘이 존재할 경우 효율적. 
• 알고리즘이 최적인지 증명해야함. Knapsack 문제는 풀지만, 0-1 Knapsack 문제는 풀 수 없음.

• 탐욕적 접근법의 알고리즘 설계 절차
• 1단계: selection procedure (선정 과정)
• 현재 상태에서 가장 좋은 해답을 모아 solution set에 포함
• 2단계: feasibility check (적정성 점검)
• 새롭게 얻은 solution set이 적절한지 확인
• 3단계: solution check (해답 점검)
• 새로 얻은 solution set이 최적의 해인지 결정
  

• spanning tree (신장 트리)
  
• 
• 방향이 없는 그래프 G에서 순환 경로를 제거하면서 '연결된 부분그래프'가 되도록 엣지들을 제거해 나감
• 즉, 그래프 G에서 G에 속한 모든 노드를 다 포함하면서서 트리가 되는 '연결된 부분그래프'

• minimum spanning tree (최소 비용 신장 트리)
  
• 
• 최소의 가중치를 가진 부분 그래프는 반드시 트리가 되어야 함.
• 트리가 아니라면 cycle이 존재하고, cycle이 존재하는 한 더 작은 비용의 신장트리가 존재할 것.
• observation : 모든 신장트리가 최소 비용 신장트리가 되는 것은 아님
• 최소 비용 신장 트리 적용 예) 도로 건설, 통신, 배관
  
  
• brute-force 접근 :  모든 신장트리를 고려하여 그 중에서 최소 비용을 고름 (복잡도가 높음)
• greedy 접근 :
  
  
  
  

• Prim's Algorithm
  
  
  
  
  
• 그래프 그림에서 prim 알고리즘 적용 예
  
  
  
  
  
• 알고리즘 내 자료구조 
• W[i][j] 인접행렬 표현 방법
  
• nearest[1..n] : Y에 속한 정점 중 v(i)에서 가장 가까운 정점의 인덱스
• distance[1..n] : v(i)와 nearest[i]를 잇는 이음선의 가중치
  
  
• prim 알고리즘 구현 예시
  
  
• *theorem) prim 알고리즘은 항상 MST(Minimum spanning tree)를 만들어낸다.

• Kruskal Algorithm
• 의사코드 수준에서의 kruskal 알고리즘
  
  
  
• kruskal 알고리즘에서 MST를 만들기 위한 단계
  
  (1) edge를 weight를 기준으로 오름차순으로 정렬한다.
  (2) 서로소 집합을 생성한다
  
  
  
  (3) edge를 정렬한 순서대로 하나씩 선택한다. edge (v1, v2)를 선택
  (4) edge (v3, v5)를 선택 및 추가
  (5) edge (v1, v3)를 선택 및 추가
  
  (6) edge (v2, v3)를 선택하였으나 이미 v2와 v3은 '연결된 부분그래프'에 속해있음. 해당 edge를 추가할 필요가 없음
  (7) edge(v3, v4)를 선택 및 추가. 이로서 그래프 G 내의 모든 노드가 연결된 부분그래프가 완성되었음. 이후 edge들 (v4,v5) 및 (v2, v4)는 추가할 필요 없음.
  
  
• Kruskal algorithm을 구현하는 코드에서 사용하는 자료구조
  
  
  
• Kruskal 알고리즘 코드 예제
  
  
  
  
  
• Dijkstra 알고리즘
• 가중치가 있는 방향성 그래프에서,
  한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 문제
• 시작점 : v1
• 알고리즘
  
  
  
• 알고리즘 도식화
  
  
  
  
  
  
• dijkstra 알고리즘 자료구조
• touch[i] : edge (v, vi)가 그래프 Y 내에 존재한 노드로만 구성된 v에서 vi까지의 최소 거리를 구성할 때 마지막으로 추가된 경우, 해당 v의 인덱스.
• length[i] : 그래프 Y 내에 존재하는 노드로만 구성된 v1에서 vi까지의 현재 최소 거리 길이.
   
• dijkstra 알고리즘 구현 예시
  
• 
  
  
  
• The Knapsack Problem (배낭채우기 문제)
• 아이템이 n개가 주어지고, 각 아이템에 따른 무게와 가치가 다를 때,
  배낭에 넣을 수 있는 최대 무게를 만족하면서 가치를 최대치가 되도록 결정하는 문제
  
  
• brute-force/greedy approach
• n개의 물건에 대해 모든 부분 집합을 전부 고려함
• 하지만, 크기가 n인 집합의 부분 집합의 수는 2^n개임
• why?
• 
  
  
  
• 0-1 knapsack problem with brute-force/greedy approach
  
• 접근법 1 :가장 비싼 물건부터 우선적으로 채움.
• 최적의 해를 구하기 어려움.
• 접근법 2: 무게 당 가치가 가장 높은 물건부터 우선적으로 채움
• 역시나 최적의 해를 구하기 어려움.
• The fractional knapsack problem 
• 물건 일부분을 잘라서 담을 수 있다 --> greedy OK (optimal!)
  
  
• 0-1 knapsack problem with dynamic programming approach
• 아이템의 인덱스 : i (i>0), 아이템의 무게: w(w>0)라 할 때, 
  전체 무게를 w가 넘지 않도록 i번째까지의 항목으로 얻어진 최고의 이익(optimal profit)을 P[i][w]라고 할 때, 다음과 같은 식으로 정리 할 수 있음
  
  
  
  
• P[i-1][w] : i 번째 항목을 포함시키지 않은 경우의 최고 이익
• p(i) + P[i-1][w-w(i)] : i 번째 항목을 포함시키는 경우의 최고 이익
  
  
• 최대이익 P[n][W] 를 구하려면?
• P[0..n][0..W]의 2차원 배열을 만든 후, 각 항을 계산하여 넣음.
  (P[0][w] = 0, P[i][0]=0으로 놓고 계산.)
  
  
• 아래 식으로 표현 가능
  
• 즉, (n-1) 번째 행에서는 P[n-1[W]와 P[n-1][W-w(n)]항만필요.
  
• 이런 식으루 n=1 이나 w<=0일 때까지 계속 해나가면 됨.