What are the 3 fundamental techniques?
- The Greedy Method
- Divide and Conquer
- Dynamic Programming
Describe the Greedy Method?
- a problem solving strategy used in optimisation problems
- involves making locally optimal choices at each step in the hope these choices lead to a globally optimal solution
- so at every decision point, it selects the best available option without considering overall future consquences
Why might we not use a greedy method approach?
- because this doesn’t guarantee the optimal solution
How does the greedy method decide what is the best/optimal local decision to make?
- it uses a given criteria to decide what the best choice to make is
Give examples of problems solved by the greedy method
- Fractional knapsack problem
- interval scheduling
- task scheduling
- minimum spanning trees
- shortest paths (Dijkstra’s algorithm)
- change making (smallest number of coins)
- maximum spacing of k-clustering
What is the fractional Knapsack Problem?
Have a set S of n items, each item has a positive benefit bi and weight wi
- goal is to find the maximum benefit subset that does not exceed total weight W
- we can take arbitrary fraction xi of each item where each fraction is 0 <= xi <= wi
- the sum of all the fractions must be <= max W
What is the objective function for solving the fractional knapsack problem?
- the total benefit of items taken is determined by the sum of each item whose fraction xi/wi of it’s benefit to the solution
What is the general method for solving the FKP?
- Compute the value index for each item = vi = bi/wi
- select items to pack into the knapsack by choosing from highest value index to lowest
- once we reach the max weight W, we stop
What is the greedy element in the greedy method’s solution for the FKP?
- that in each iteration locally we’re choosing the next item to pack and our greedy criteria is to take the item with the highest value index
What amount do we add to the total benefit after an item is packed?
- We add the value index multiplied by xi (we don’t add bi to the benefit)
- for example if item 3 has vi = 3/2 and we add item 3’s full wi of 2, we add 3/2 * 2 = 3 to the total benefit
What is the {0,1} knapsack problem?
Similar to the Fractional knapsack problem, however only a whole item’s weight can be packed into the knapsack
- so an item can only get packed or not rather than a fraction of it
- optimal solution isn’t always found with the greedy method
- can be solved by dynamic programming
What is interval scheduling?
- have a set T of n tasks and a single machine that can process these tasks
- goal is to select a subset of tasks to maximise the number of tasks we can schedule
- the tasks cannot overlap (conflict)
- ni is the start time and nf is the finish time
- two tasks are non-conflicting if fi<=fj or fj<=fi
How do we use a greedy algorithm to solve the interval scheduling problem?
- we order tasks by completion/finish time, so we put them in order of finishes first to finishes last.
- we then take the task that finishes first and add it to the schedule, we then remove any task that conflicts with this added task
- we then repeat doing this until there are no tasks left.
What data structure can we use to implement the solution of a greedy algorithm for both the fractional knapsack problem and the interval scheduling problem
- We can use a heap data structure for the implementation of these problems
- root holds highest value index in FKP
- root holds smallest finish time in ISP
What is clustering?
- when we tr to group together a collection of n objects based on the idea of distance
- we have n objects: O1, O2, …On and a distance function that compares how far a pair of objects are.
- this distance function has 3 axioms (properties)
1. d(Oi,Oi) = 0 - distance between identical objects = 0
2. d(Oi, Oj) > 0 for all i != j - distance between different objects must be positive
3. d(Oi,Oj) = (Oj, Oi) - distance between a and b is the same as distance between b and a - We want to group objects into k (non empty) clusters C1,…Cn where k «_space;n (much less than)
What is the maximum spacing clustering problem?
Given a set of clusters C1, … Ck, where the maximum spacing is defined as the minimum distance between two objects in two different clusters, we want to find a clustering so that the minimum inter cluster distance is as large as possible.
What type of problem is the maximum spacing clustering problem?
- it’s an optimisation problem as we’re trying to find the maximum of something - so this can be solved by the Greedy method
How do we solve the maximum spacing clustering problem
- build a graph where the objects O1,…On are nodes of the graph
- the connected components of the graph we build will be clusters, we aim to bring objects that are similar close together into the same cluster, so they don’t end up in different clusters (hence making max spacing small)
- Take the two closest objects and add an edge between them and repeatedly keep doing this
- continue considering distances between pairs in increasing orders
- we don’t put an edge between items in the same cluster
- adding an edge corresponds to merging two clusters into 1.
What are the steps for solving the maximum spacing clustering problem?
- put all n objects into their own cluster, so we have n clusters to start off with
- then calculate the distance between every pair of objects
- take the pair of objects with the smallest distance and merge them into one cluster to leave you with n-1 clusters
- recalculate the distances between each object (the objects in the same cluster know have a distance of ∞ so they won’t be remerged)
- repeat step 3 and 4 until there are k clusters left
- calculate the distances between all the pairs of objects in different clusters and find the minimum
- return the minimum as this is the maximum spacing clustering distance
