Examples
- Shortest path - Minimize Time, Distance; constraint drive under speed limit, avoid toll roads
- Traveling Sales Person (TSP) - Required to fly to a set of cities and return to origin. Find flights that minimize total fare.
- Bin Packing - What items to put in the bin and in what order (shipping domain)
- Sequence Alignment - Align DNA/RNA sequence
- Knapsack Problem - Backpacking, what items will fit in the backpack while maximizing the value of items in the pack
Optimization Problem
- A function to maximize or minimize
- A set of constraints to adhere to
The common theme among all these problems is that we have some function to minimize or maximize subject to some constraint. For example, in case of the shortest path problem we may wish to minimize the distance, or travel time subject to constraints such as not taking any toll roads.
Discrete vs. Non-Discrete Knapsack problems
In a non-discrete knapsack problem, the items are arbitrarily divisible into smaller quantities (for example, gold dust). In discrete, also called 0,1 knapsack problems, the items are not divisible into arbitrary quantities (for example, gold bricks).
Greedy Algorithm
In a greedy algorithm, we pick the most valuable item first. Greedy algorithm does not always yield the best solution but most of the time it does. In other words, locally optimal descisions (first pick, second pick,...) does not necessarily result in a globally optimal solution.
Brute force
In brute force algorithm, we conduct a exhaustive enumeration and valuation of all possibilities to come up with the best solution.
∑i=1n PiXi
∑i=1n PiXi
where Xi is a vector of zeros and ones denoting whether an item is picked or not and Pi is the price or value of the item.
∑i=1n WiXi <= C
where C is the maximum weight (constraint) and Wi is the weight of an item.
Given 8 items, possible selections are as follows.
Pi to P8
00000000
00000001
00000011
..
11111111
Number of possible combinations are 28= 256
Therefore, to solve this sort of problem with brute force will require an exponential algorithm!
∑i=1n WiXi <= C
where C is the maximum weight (constraint) and Wi is the weight of an item.
Given 8 items, possible selections are as follows.
Pi to P8
00000000
00000001
00000011
..
11111111
Number of possible combinations are 28= 256
Therefore, to solve this sort of problem with brute force will require an exponential algorithm!
Dynamic Programming
- Careful brute force
- Divide problem into sub-problems; solve sub-problems; use results of sub-problems to solve the bigger problem; there must be overlapping sub-problems and optimal sub-structures
- Sub-problems must be acyclic (otherwise stuck in endless loop)
- Recursion + memoization + guessing (best guesses)
Solving Optimization Problems
There are preexisting dynamic programming algorithms. Map new problem to an old problem that has been solved and use a proven algorithm.
