Greedy Overview
Question
- Starting at vertex 100, apply a greedy search using the heuristic:
"choose the largest adjacent vertex, stop if all are smaller" to
find the maximum 3-bit value on the upper-right
figure. Follows path <100, 110, 111>
- Did a locally optimal choice lead to a globally optimal solution?
Yes.
- Try your method on the figure below starting at
vertex 001. Follows path <001, 101>
- Did a locally optimal choice lead to a globally optimal solution?
No.
- Does this problem have the greedy-choice
property (a globally optimal solution can be arrived at by making
locally optimal (greedy) choice)? No.
Example: Huffman codes for optimal data compression
For example,
consider the following sentence:
dead beef cafe deeded dad. dad faced a faded cab. dad acceded. dad be bad.
Frequencies for the 77 characters are:
| a |
b |
c |
d |
e |
f |
|
. |
| 12 |
4 |
5 |
19 |
12 |
4 |
17 |
4 |
Question - Which characters should we encode in the fewest bits? The characters occurring most frequently should be encoded with the fewest number of bits.
Constructing a Huffman code
Question: In above Figure (b), why are codes for a=0 and
f=1100? a is left. f is right, right, left, left.
Question: Where's the greed? Always extract two lowest
frequency values from a character frequency min-heap, place (minimum)
remaining at lower (longer code) levels of code tree.