탐욕법(Greedy) - swkim0128/PARA GitHub Wiki

type: Algorithm archive: false

탐욕 기법

탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법

최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제이다.

일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.

여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.

일단, 한번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 분제들에 적용된다.

Knapsack

Knapsack 문제의 정형적 정의

S = { item1, item2, ..., itemn }, 물건들의 집합

wi : itemi의 무게, Pi = itemi의 값

W : 배낭이 수용 가능한 총 무게

문제 정의

$\sum_{item_i \in A}W_i \leq W$ 를 만족하면서 $\sum_{item_i \in A}P_i$ 가 최대가 되도록 $A \subseteq S$가 되는 A를 결정하는 문제

Knapsack 문제 유형

0-1 Knapsack

배낭에 물건을 통째로 담아야 하는 문제

물건을 쪼갤 수 없는 경우

Fractional Knapsack

물건을 부분적으로 담는 것이 허용되는 문제

물건을 쪼갤 수 있는 경우

0-1 Knapsack에 대한 완전 검색 방법

완전 검색으로 물건들의 집합 S에 대한 모든 부분집합을 구한다.

부분집합의 총 무게가 W를 초과하는 집합들은 버리고, 나머지 집합에서 총 값이 가장 큰 집합을 선택할 수 있다.

물건의 개수가 증가하면 시간 복잡도가 지수적으로 증가한다.

Fractional Knapsack 문제

물건의 일부를 잘라서 담을 수 있다.

활동 선택(Activity-selection problem) 문제

시작시간과 종료시간 ($s_i, f_i$)이 있는 n개의 활동들의 집합 $A = {A_1, A_2, ..., A_n}, 1 \leq i \leq n$에서 서로 겹치지 않는 (non-overlapping) 최대갯수의 활동들의 집합 S를 구하는 문제

양립 가능한 활동들의 크기가 최대가 되는 $S_{0, n+1}$의 부분집합을 선택하는 문제

종료 시간 순으로 활동들을 정렬한다.

$S_{0, n + 1}$는 $a_0$의 종료 시간부터 $a_{n+1}$의 시작시간 사이에 포함된 활동들

$S_{0, n+1} = {a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9, a_10} = S$

탐욕 기법의 적용

$S_{i, j}$를 풀기 위해

  1. 종료 시간이 가장 빠른 $a_m$선택
  2. $S_{i, j} = {a_m} \cup S_{m,j}$의 해집합

$S_{0, 11}$에 대해, $a_1$ 선택하고, $S_{1, 11}$을 푼다.

$S_{1, 11}$에 대해, $a_4$ 선택하고, $S_{4, 11}$을 푼다.

$S_{4, 11}$에 대해, $a_8$ 선택하고, $S_{8, 11}$을 푼다.

탐욕 기법을 적용한 반복 알고리즘

A: 활동들의 집합, S: 선택된 활동(회의)들 집합
Si: 시작시간, fi: 종료시간, 1 <= i <= n

Sort A by finish time
S <- {A1}
j <- 1
FOR i in 2 -> n
	IF fj <= si
		S <- S ∪ {Ai}
		j <- i

종료 시간이 빠른 순서로 활동들을 정렬한다.

첫 번째 활동(A1)을 선택한다.

선택한 활동(A1)의 종료시간보다 빠른 시작 시간을 가지는 활동을 모두 제거한다.

남은 활동들에 대해 앞의 과정을 반복한다.

탐욕 알고리즘의 필수 요소

탐욕적 선택 속성(greedy choice property)

탐욕적 선택은 최적해로 갈 수 있음을 보여라.

→ 즉, 탐욕적 서낵은 항상 안전하다.

최적 부분 구조(optimal substructure property)

최적화 문제를 정형화 하라.

→ 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.

[원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해]임을 증명하라.

⚠️ **GitHub.com Fallback** ⚠️