8-9 | Greedy algorithms Flashcards
Greedy algorithm definition
Greedy algorithm:
A way of solving a problem by making locally optimal choice with the hope of finding a global optimum
make decisions based on information available at hand without worrying about the effect of these decisions in the future.
Types of computational problems
Decision problem
Optimization problem
Counting problem
Greedy algorithm: typical use
Typically used to solve optimization problems
Optimization problem definition
asks for finding the best possible solution among a set
of all possible solutions to a problem.
Example of optimization problem
Change-making problem
Let the coins we have available are of value:
…
Devise an algorithm for paying a given amount of units using the smallest number of coins, if there is unlimited supply for each type of coin.
Change making optimization problem
Greedy solution strategy?
Does it find the optimal solution?
Starting with nothing, at every stage we add to the coins already chosen a coin of largest value available that does not take us over the amount to be paid
why greedy?
At every step chooses the largest coin it can (locally optimal)
without worrying this will us to the best solution in the long run
Greedy algorithm does not find an optimal solution! (may depend on available coins)
Greedy algorithms: general characteristics?
Set of candidates
Solution function
Feasibility function
Selection function
Objective function
Greedy algorithms
Set of candidates ?
examples
An object / entity which is a part of a problem instance
Two disjoint subsets are accumulated
candidates that have been considered and chosen
candidates that have been considered and rejected
example
- Coins that are available for making a change
- Edges in a graph from which one is to find a shortest path
Greedy algorithms
Solution function?
examples
checks whether or not a particular set of candidates constitutes a solution
without worrying if the solution is optimal
example
does the selected coins match the amount to be paid?
does the selected edges give a path from between two specified nodes?
Greedy algorithms
Feasibility function?
examples
checks whether or not a set of candidates can be completed to a solution by adding other candidates
here, too, we do not worry about optimality
it is important to know whether or not a given set of candidates allows to build a solution, irrespective of optimality
(to show that the feasibility space is not empty)
Greedy algorithms
Selection function?
examples
indicates which of the remaining candidates which have neither been selected nor rejected is the most promising
Greedy algorithms
Objective function?
examples
gives the value of the solution found
Example
- the number of coins used
- the length of a path
whatever value we aim to optimize
How do greedy algorithms work?
How do greedy algorithms work?
Initially, set of chosen candidates is empty
At each step
* consider adding the best remaining untried candidate (choice guided by the selection function)
* if the enlarged set is not feasible (guided by the feasibility function) reject the candidate we are currently considering
* otherwise, the candidate remains in the set of chosen candidates, where it stays from now on
* Each time we enlarge the set of candidates we check if it is a solution (guided by the solution function)
When the greedy algorithm works correctly, the first found solution is optimal
Can greedy algorithms backtrack?
There is no turning back in a greedy algorithm
Once a candidate is included in a solution, it stays there for good!
Once a candidate is excluded from a solution, it is never considered again!
General greedy algorithm
function greedy(𝐶)
𝐶 is the set of candidates
𝑆 ← ∅ # we construct the solution in 𝑆
while 𝐶 ≠ ∅ and not solution(𝑆) do
𝑥 ← select(𝐶)
if feasible(𝑆 ∪ {𝑥}) then
𝑆 ← 𝑆 ∪ {𝑥}
if solution(𝑆) then # why check this here?
return 𝑆
else
return there are no solutions
Selection function
The key to a greedy algorithm is its selection function
Selection function is related to the objective function
Example
* objective – maximizing profit
selection – remaining item of largest value
* objective – minimizing cost
selection – cheapest remaining candidate
Sometimes, more than one selection function – care is needed in choosing the one which ensures correctness
Change-making optimization problem
Set of candidates?
coins eg 100, 25, 10, 5, 1
Change-making optimization problem
Solution function?
checks that the coins we have so far give the exact amount to be paid
Change-making optimization problem
Feasibility function?
a set of coins in feasible if its total value does not exceed the
amount to be paid
Change-making optimization problem
Selection function?
chooses the highest-valued coin from those remaining in the set of candidates
Change-making optimization problem
Objective function?
the number of coins in the solution 2
Change-making optimization problem
Greedy algorithm pseudocode?
function makeChange(n)
𝐶 = {candidate coins}
𝑆 ← ∅ # 𝑆 contains the solution
𝑠 ← 0 # 𝑠 is the sum of items in 𝑆
while 𝑠 ≠ 𝑛 do
𝑥 ← largest item in 𝐶 such that 𝑥 + 𝑠 ≤ 𝑛
if there is no such item
return no solution found
𝑆 ← 𝑆 ∪ {a coin of value 𝑥}
𝑠 ← 𝑠 + 𝑥
return 𝑆
Subgraphs
Definition?
A subgraph of a given graph 𝐺 is the graph 𝐻, such that
𝑉(𝐻) ⊆ 𝑉(𝐺) and
𝐸(𝐻) ⊆ 𝐸(𝐺)
Subgraphs
Types?
A vertex-induced subgraph of 𝐺 contains
* a subset of vertices of 𝐺
* all the edges that connect them in 𝐺
An edge-induced subgraph of 𝐺 contains
* a subset of edges of 𝐺
* all the vertices that are their end points in 𝐺
In graphs, what is a clique?
graph in which all nodes are mutually connected