Dynamic Programming vs Greedy Algorithms

From My Wiki
Jump to: navigation, search

What is an algorithm? An algorithm is a step by step method of achieving an end result. Different algorithms can achieve the same result in difference ways and taking into account different costs (eg time vs space).

In some cases an optimal solution is required. This is an optimization problem. In this case we don't care about getting just any result, we want the best result. An optimization problem is a problem where we have a goal to achieve but we also want to achieve the goal at a minimum cost. Greedy Algorithms and Dynamic Programming Algorithms can be used to find these.

Greedy Algorithms

Greedy Algorithm aims to get the best result by picking seemingly best choice at each stage. It makes a locally optimum choice with the hope of finding a global optimum. With a greedy algorithm we never consider look into the future to pick the next best step. we just see what we see right now and make the best choice. And we never go back in time to make a different choice - we never reconsider our choices once we've made them. Because of this greedy algorithms can be considered "short sighted" and "non-recoverable".

They are best for simple problems. Note that because of this, greedy algorithms can fail to find the best result.

Basic greedy algorithm example - change making

C = [25, 15, 1] # ordered list of coin values
n = 30 # goal

print n
print

i = 0
while n != 0:
	if n-C[i] >=0:
		n = n-C[i] # take (n-C[i]) largest amount you can at each step (greedy)
		print "%s - %s"%(n, C[i])
	elif i<len(C)-1: # if you can't take this, means to go smaller piece
		i = i+1
	else:
		print "no sol"
		break

You want to make 30 cents in change, and you have amounts of 25, 15 and 1 cent pieces in whic you make this with. You want to use the least amount of coins. A greedy algorithm would take the largest amount you can at each step. So for the first step you would take a 25 cent piece. This leaves 4 cents remaning to make up. This is made up with 5 counts of 1 cent pieces. In total 6 coins are used.

30

5 - 25
4 - 1
3 - 1
2 - 1
1 - 1
0 - 1

A more complicated example

Trying to solve this: http://community.topcoder.com/stat?c=problem_statement&pm=2977&rd=5880

"Find the maximum number of disjoint time intervals that can be chosen such that each interval is of duration 1 second or less and contains button presses from at least 3 different judges. Two intervals are disjoint if every time within one interval is strictly less than every time in the other. We give the boxer credit for one punch during each interval."

How this solves it is that is starts from the minimum value and grows that interval until it hits 1000 milisecs or encounters hits from 3 judges. Then in tries to shrink this interval in a way that the previous property still remains true (hits from 3 different judges).

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Collections;

public class boxing {
	public static void main(String args[]) {


		int[] a = new int[]{    1, 2, 3, 4, 5, 6 };
		int[] b = new int[]{    1, 2, 3, 4, 5, 6, 7 };
		int[] c = new int[]{    1, 2, 3, 4, 5, 6 };
		int[] d = new int[]{ 0, 1, 2 };
		int[] e = new int[]{    1, 2, 3, 4, 5, 6, 7, 8 };
	System.out.println("**");
		maxCredit(a, b, c, d, e);

		a = new int[]{100,200,300,1200,6000};
		b = new int[]{};
		c = new int[]{900,902,1200,4000,5000,6001};
		d = new int[]{0,2000,6002};
		e = new int[]{1,2,3,4,5,6,7,8};

	System.out.println("**");
		maxCredit(a, b, c, d, e);

		a = new int[]{5000,6500};
		b = new int[]{6000};
		c = new int[]{6500};
		d = new int[]{6000};
		e = new int[]{0,5800,6000};

	System.out.println("**");
		maxCredit(a, b, c, d, e);
	}

	public static int maxCredit(int[] a, int[] b, int[] c, int[] d, int[] e) {
		//grow
		//find smallest
		smallest(a, b, c, d, e);  //need to know when three different arrays used, then remove from back.
		return 0;
	}

	public static int smallest(int[] a, int[] b, int[] c, int[] d, int[] e) {
		Comparator<element> comparator = new elementc();
		PriorityQueue<element> queue = new PriorityQueue<element>(5, comparator);
		ArrayList<element> feed = new ArrayList<element>();

		try{ queue.add(new element("a", a, a[0], 0)); }catch(Exception f){}
		try{ queue.add(new element("b", b, b[0], 0)); }catch(Exception f){}
		try{ queue.add(new element("c", c, c[0], 0)); }catch(Exception f){}
		try{ queue.add(new element("d", d, d[0], 0)); }catch(Exception f){}
		try{ queue.add(new element("e", e, e[0], 0)); }catch(Exception f){}

		for (int i = 0; i < a.length + b.length + c.length + d.length + e.length; i++) {
			element x = queue.remove();
			feed.add(x);
			x.index++;
			if (x.index < x.all.length) {
				queue.add(new element(x.judge, x.all, x.all[x.index], x.index));
			}
		}
		process(feed);
		return 0;
	}

	public static void process(ArrayList<element> feed) {
		System.out.println(feed);
		ArrayList<element> uniq = new ArrayList<element>();
		ArrayList<String> dupes = new ArrayList<String>();

		ArrayList<element> split = new ArrayList<element>();
		int startValue = -1;
		int endValue = -1;
		for (element e : feed) {
			//System.out.println("Grabbed new element "+ e + " startValue="+startValue);
			if(e.value>startValue && e.value - startValue < 999 ) {
				//System.out.println("added to split array");
				split.add(e);

				for ( element f : uniq) {
					if(e.value == f.value) {
						if(dupes.indexOf(f.judge)<0) {
							dupes.add(f.judge);
						}
						if(dupes.indexOf(e.judge)<0) {
							dupes.add(e.judge);
						}
						if(dupes.size()==3){
							//System.out.println("dupes"+dupes);
							dupes = new ArrayList<String>();
							//System.out.println("dupes cleared");

							//System.out.println("contents of split1:"+split);
							clean(split);
							split = new ArrayList<element>();
							//System.out.println("split cleared");

							startValue = e.value;

							//System.out.println("startValue reset to"+startValue);
							break;
						}
					}
				}
				uniq.add(e);
			}
			else if(e.value - startValue >= 999) {
				//System.out.println("Difference was too great:"+(e.value-startValue));

				endValue = (startValue + 1001 + 500) / 1000 * 1000; //round nearest sec
				//System.out.println("Lets end this split: endValue="+endValue);
				split.add(new element("x",null,endValue,0));

				startValue += 1000;
				//System.out.println("Lets take previous starting value and add 1000 to it: startValue="+startValue);

				if(split.size()!=2) {
					//System.out.println("split2"+split);
					clean(split);
					split = new ArrayList<element>();
					//System.out.println("emptied split2 and started new with: "+(endValue+1));
					split.add(new element("x",null,endValue+1,0));
				}else{
					//System.out.println("split3"+split);
					//System.out.println("is empty. no actual elements in here");
					split = new ArrayList<element>();
					split.add(new element("x",null,endValue,0));
					//System.out.println("emptied split3 and started new with: "+(endValue));
					endValue = startValue+1000;
					//System.out.println("endValue set to: "+endValue);
				}
				startValue = endValue-1;
				//System.out.println("startValue set to: "+startValue);

			}
		}
		//System.out.println("split3"+split);
		clean(split);
		//System.out.println("end value"+endValue);
	}

	public static void clean(ArrayList<element> split) {
		//System.out.println("Cleaning..."+split);

//needs contain 3 diff judges.
		//elim from front unnec

		if(split.size()>3) {

				while(true){split.remove(0);
				ArrayList<String> dupes = new ArrayList<String>();
				for (element q:split){

					if(dupes.indexOf(q.judge)<0) {
						dupes.add(q.judge);
					}

				}

				if(dupes.size()>=3) {
					//System.out.println("OK!");
					//System.out.println(split);
					break;
				}
				}
		}
		if (split.size()==3) {
			ArrayList<String> dupes = new ArrayList<String>();
			for (element q:split){

					if(dupes.indexOf(q.judge)<0) {
						dupes.add(q.judge);
					}

				}
				if(dupes.contains("x")){
					//System.out.println("ok!");
				}
				else if(dupes.size()!=3) {
					//System.out.println("Not OK!");
				//	System.out.println(split);
					return;

				}
		}
		System.out.println("Done!"+split.get(0).value+"-"+split.get(split.size()-1).value);
	}
}

class element {
	public String judge;
	public int[] all;
	public int value;
	public int index;

	public element(String judge, int[] all, int value, int index) {
		this.judge = judge;
		this.all = all;
		this.value = value;
		this.index = index;
	}
	public String toString() {
		return ""+judge+") "+value;
	}

	public boolean equals(element e){
		return this.value == e.value;
	}

}

class elementc implements Comparator<element> {
	public int compare(element x, element y) {
		if (x.value < y.value) {
			return -1;
		}
		if (x.value > y.value) {
			return 1;
		}
		return 0;
	}
}

Dijkstra's algorithm

Let's take another look at Dijkstra's Algorithm.

We use Dijkstra's Algorithm because we want the shortest path from the start node to the end node. If we didn't want an optimal path we could just use dfs or bfs. This would get a path, but not necessarily the best path.

Why is Dijkstra's Algorithm considered a greedy algorithm? Because to find the shortest path it picks the nearest unvisited node at each iteration. And once visited, its distance will never be updated.

We don't do is consider every possible path to a node, some nodes may go unexplored. Sometimes the solution may not even be optimal. So this is not considered dynamic programming. However they both do share the commonality of optimal substructure. We use this property to print the path when finished.

			while previous[smallest]:
				path.append(smallest)
				print "%s:%s"%(smallest,previous[smallest])
				smallest = previous[smallest]
			path.append(smallest)
			return path 

We know that A - B - C - D is an optimal route from A to D. Then A - B - C is an optimal route from A to C.

This is not unlike the printing change in the dynamic programming example below.

External Links

https://en.wikipedia.org/wiki/Greedy_algorithms http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg

Dynamic Programming

Unlike greedy, dynamic programming is exhaustive and guaranteed to find an optimal solution. Dynamic programming is great when it comes to problems that have optimal substructure and overlapping subproblems. Overlapping subproblems is when a problem can be broken down into other problems, and whose solutions can be used to help solve each other. For example, the nth Fibonacci number F(n) can be found by first calculating F(n-1) and F(n-2). And subsequently, F(n-1) can be calcuated from F(n-2) and F(n-3). We can see here that F(n-2) is used twice. Which means that if we solved it once, we can store this solution somewhere which means we wouldn't need to recalcuated it next time we need to use it. This storing of a solution is to a sub problem is called "memoization" and it can help reduce number of calculations needed. This is a smart form of recursion. Divide and conquer algorithms (merge-sort, quick-sort, etc) also uses recursion except the parts can never overlap. They must be distinct (which lets them be solved in parallel).

Optimal substructure actually applies to both greedy and dynamic programming. "A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems." In other words, if there is a most optimal route from A to E and it involves C. Then the route from A to C and C to E are the most optimal ones.


If we know that the best way to make X in change is to first make (X-a) in change and then add coin Y we can store value Y at location (X-a) then use this series of pairs to find the best way to make X in change.

We start by making all values from 0 to the goal state.


We consider every possible option and incremently get a better and better result. DP can reconsider its steps unlike DA. Meaning DP can take what looks like an intial bad step, but can come out with an even better solution than DA.

The coin changing examples on this page illustrate this. Greedy takes a 25 piece first to end with a solution involving 5 coins. Dynamic takes a 15 piece first to end with a solution involving 2 coins.

https://en.wikipedia.org/wiki/Dynamic_programming.

Basic dynamic programming example - change making

# based on http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf

import sys

d = [1, 15, 25] # ordered array of denom values
n = 30 # goal amount
C = {} # count
S = {} # first coin # because of optimal subprob property,
# this can be used to go back through from goal to start
# to get best route (comb)

print n
print
C[0] = 0

for p in range(1, n+1):
	min = sys.maxsize # large number (inf)
	coin = 0 # temp

	for i in range(0, len(d)): # 0 indexing
		if d[i] <= p:
			if 1 + C[p-d[i]] < min:
				min = 1 + C[p-d[i]]
				coin = i
	C[p] = min
	S[p] = coin

#make change
while n > 0:
	print d[S[n]]
	n = n-d[S[n]]

Result

30

15
15

This is what values of C and S look like

C = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10, 11: 11, 12: 12, 13: 13, 14: 14, 15: 1, 16: 2, 17: 3, 18: 4, 19: 5, 20: 6, 21: 7, 22: 8, 23: 9, 24: 10, 25: 1, 26: 2, 27: 3, 28: 4, 29: 5, 30: 2}

S = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0, 11: 0, 12: 0, 13: 0, 14: 0, 15: 1, 16: 0, 17: 0, 18: 0, 19: 0, 20: 0, 21: 0, 22: 0, 23: 0, 24: 0, 25: 2, 26: 0, 27: 0, 28: 0, 29: 0, 30: 1}

So in C, 6:6 means that the value 6 can optimally be made using 6 coins.

C keeps track of the number of coins used to make the value. This is useful because the most optimal solution uses the minimal number of coins.

in S, 6:0 means that 0th coin (d[0] = 1) was the final coin used to make the value 6. So to make 6 optimally we first need to make 5 (=6-1).

S keeps track of the last coin used to make the value.

Floyd–Warshall Algorithm

Floyd–Warshall algorithm

It computes all the possible shortest paths from each vertex to another. It starts of by considering pairs of vertices which are connected to each other through an edge. Then it increase number of edges. When increasing edges, it will run in to previously calculated (memoized) values. ie The distance of A - B is given. This distance will then be used to calculated of A - B - C and in in turn A - B - C - D. Then it turns out that the best way to go from A to D is actually by doing A - B - E - D.

The following is the fundamental of Floyd-Warshall. Compare these loops and if-statements to the ones used in change making code above.

for k in self.adj:
	for i in self.adj:
		for j in self.adj:
			if self.muh_matrix[i][k] + self.muh_matrix[k][j] < self.muh_matrix[i][j]:
				self.muh_matrix[i][j] = self.muh_matrix[i][k]+self.muh_matrix[k][j]

i and j represent all the pairs in the graph. 

k represents a node in between i and j which can be used to define a path. 

self.muh_matrix[x][y] may be a value of an edge (x, y are adjacent)
self.muh_matrix[x][y] may be calculated from paths x - z and z - y
self.muh_matrix[x][y] may be used to calcuate path x - a

Thus dynamic programming.

In addition to Floyd-Warshall, both Bellman ford and also Insertion sort are examples of dynamic programming ??? And Dijkstra's algorithm may be an example of dynamic programming: http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/

External Links

https://en.wikipedia.org/wiki/Dynamic_programming http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

TL;DR

Greedy: top down, quick and dirty
Dynamic: bottom up, exhaustive, more complex, guarantee optimal (?),