[ Algorithm ] 05. Greedy Algorithm

38A·2023년 4월 14일

알고리즘 분석

목록 보기

5/14

A design strategy for some(every x) optimization problems.
Make the choice that looks best at the moment.
➡️ local optimum
Not always lead to a globally optimum solutions.
But come up with the global optimum in many cases.

Activity Selection Problem

Ex_ Get your money’s worth at amusement park
➡️ goal: ride as many rides as possible
We want to schedule several activities that require exclusive use of a common resource, with a goal of selecting a maximum-size set of mutually compatible activities(서로 사이좋게 지낼 수 있는)
An activity a $_i$ is represented [s $_i$ ,f $_i$ ), where s $_i$ is a start time and f $_i$ is a finish time.
a $_i$ and a $_j$ are compatible if [s $_i$ ,f $_i$ ) and [s $_j$ ,f $_j$ ) do not overlap
Assume that the classes are sorted according to increasing finish times; f $_1$ < f $_2$ < ... < f $_n$ .

The Structure of an Optimal Schedule

the subset S $_{i,j}$ begin after activity a $_i$ finishes and end before activity a $_j$ starts
Assume that activity a $_k$ is part of an optimal schedule of the classes in S $_{i,j}$
Then i < k < j, and the optimal schedule consists of a maximal subset of S $_{i,k}$ , {a $_k$ }, and a maximal subset of S $_{k,j}$
➡️ Optimal substructure? Yes.

Theorem

a $_m$ be the activity in S $_{ij}$ with the earliest finish time. Then,
1. a $_m$ is used in some maximum-size subset of mutually compatible activities of S $_{ij}$
2. S $_{im}$ = $\phi$ , so that choosing a $_m$ leaves S $_{mj}$ as the only nonempty subproblem.

Dynamic Programming vs. Greedy

Number of subproblems
- Dynamic programming : Two subproblems are used in an optimal solution and there are
(j-1) – (i+1) + 1 = j – i – 1 choices when solving the subproblem S $_{i,j}$
- Greedy : Only one subproblem is used in an optimal solution and when solving the subproblems S $_{i,j}$ , we need consider only one choice

An activity-selection problem:greedy algorithm

A Variation(변형) of the Problem

Instead of maximizing the number of classes we want to schedule,
we want to maximize the total time the classroom is in use.
DP approach still remains unchanged.
But greedy choices can't solve :
– Choose the class that starts earliest/latest
- Choose the class that finishes earliest/latest
- Choose the longest class
➡️ 어떤걸 하더라도 풀 수 x

⭐️ Greedy choice property

– An optimal solution can be obtained by making choices that seem best at the time, without considering their implications for solutions to subproblems.

Huffman Codes : Text Encoding

Widely used
Very effective technique for compressing data
An optimal prefix code
Goal: develop a code that represents a given text as compactly(간결하게) as possible
A standard encoding is ASCII, which represents every character using 7 bits:➡️ Require 133bits = 17bytes
Of course, this is wasteful because we can encode 12 characters in 4( $2^4$ = 16 > 12) bits:➡️ Require 76bits = 10bytes
An even better code(variable length) is given by the following encoding:➡️ Require 65bits = 9bytes

Prefix code

No codeword is a prefix of some other codeword
prefix: Ex_10110, 1011 is 4th prefix
The optimal data compression by a prefix code
Easy to decode
Non-prefix codes are ambiguous(모호한, 2가지 이상 해석가능한)
If code is ambiguous, then it is not prefix code. Thus, if it is prefix code, it is unambiguous

Decoding / encoding tree : Fixed-length code

Decoding / encoding tree : Variable-length code

Cost of encoding a file

T: tree corresponding to the coding scheme c in the alphabet C
f(c): the frequency of c in the file
d $_T$ (c): the depth of c’s leaf in the tree
B(T): the number of bits required to encode a file

Huffman's Algorithm

Huffman-Code(C) {
	n = len(C) // cn
	Q = C // O(lg n)
    for i = 1 to n-1 // cn 
		do allocate a new node z
        	left[z] = Extract-Min(Q) // O(lg n)
            right[z] = Extract-Min(Q) // O(lg n)
            f[z] = f[left[z]] + f[right[z]] // c
            Insert(Q, z) // O(lg n)
	return Extract-Min(Q)
}

➡️ Running time: O(n lg n) : lg n을 n번 반복

Ex_➡️ Coding scheme 잘보기!

Exercise in class

1. Coin exchange by greedy, counter example

➡️ Denomanation of coins = { 1, 10, 25 }, change = 30

2. Coin exchange by DP

Recurrsive equation
V : change
num[V] :min number of coins for change V
coins[1...m] : denomanation of each coin from to m➡️ O(nm)

3. Activity selection problem

Show counter example
The greedy approach of selecting the activity of least duration from among those that are compatible with previously selected activities.➡️ will pick a $_2$ , but the solution is a $_1$ , a $_3$