Sir's On Greedy Algorithm

Greedy algorithms A greedy algorithm always makes the choice that looks best at the moment. Problem: Giving change to a customer with the smallest number of coins. Assumptions: enough 1,5, 10, and 25 cent pieces. Example: 72:25,25,10,10,1,1. Denote the values of coins by c1, c2, . . . , cn, the change m. Therefore, we want to min

X

xi,

X

cixi = m, xi ∈ N ,

where N is the set of natural numbers. Assume c1 > c2 . . . cn, the greedy algorithm finds x1 = bm/c1c, then compute the remaining change needs to pay, m1 = m − c1x1, x2 = bm1/c2c,. . . If cn/cn−1, . . . , c2/c1, then the greedy algorithm gives the optimal solution. Jiming Peng, AdvOL, CAS, McMaster

1

Dijkstra’s STP algorithm Input: A directed graph G = (V, E) and a matrix L ∈ IRn×n, where L[i, j] ≥ 0, 1 ≤ i, j ≤ n denotes the length of ei,j . Output: A 1 × n array d, where d[j] denotes the shortest distance from v1 to vj .

Dijkstra’s Algorithm(L[n, n], d[2 : n]) Input:

L[n, n], the distance matrix;

Output: d, an array of size n. begin C := {v2, . . . , vn}; for j := 1 to n do; d[j] := L[1, j]; while C is not empty do; v := arg min d[v]; C := C − {v}; for each w ∈ C do ; d[w] := min(d[w], d[v]+L[v, w]); Return d. end Jiming Peng, AdvOL, CAS, McMaster

2

Comments on STP Algorithm The correctness of the algorithm can be proved by mathematical induction. Complexity O(n2). If we use the heap structure and know the number e of edges, then the complexity O((n + e) log n) is attainable. Exercise:

V2

10

20

V5

15 4

V1

V4

1

30

15

4

V6 V3

10

Questions: How to use Dijkstra’s algorithm to find the shortest path from vi to vj ?

Jiming Peng, AdvOL, CAS, McMaster

3

Scheduling Problem: A single server has n customers to serve. The service time ti required by each customer i is known in advance. Goal: min T =

n X

(time in the system for all customers).

i=1

Example: t1 = 5, t2 = 10, t3 = 3. In total, we have six cases: 123, 132, 213, 231,312,321. The optimal solution is 3-1-2. Suppose that i1, i2, . . . im have already be chosen, and we want to add the customer j. The increase in T will be ti1 + ti2 + . . . + tim + tj . Observation: To minimize the increase we need only to minimize tj !

Jiming Peng, AdvOL, CAS, McMaster

4

Scheduling A greedy algorithm: At each step add to the end of the schedule the customer requiring the least service among all customers not yet chosen (check this for our simple example!). The proof of the algorithm’s correctness: Let (i1, . . . in) be an optimal order, and (j1, . . . jn) be the order chosen by the greedy algorithm, one can show these two orders are essentially equivalent.

Jiming Peng, AdvOL, CAS, McMaster

5

Scheduling with deadlines Problem: Given a set of jobs {1, . . . , n} to execute that each takes one unit time. At any instant t = 1, . . ., we can execute exactly one job. Job i, 1 ≤ i ≤ n earns us a profit gi if and only if it is executed before its deadline di. Goal: Maximize the profit with a feasible schedule. A greedy algorithm: Iteratively constructing the schedule by adding at each step the job with the highest profit gi among those not yet considered provided that resulting set of jobs remains feasible. Definition: A set of jobs is Feasible if there exists one (feasible) sequence that allows all jobs in the set to meet their respective deadlines.

Jiming Peng, AdvOL, CAS, McMaster

6

Finding a feasible schedule How to determine if a set is feasible without trying all possible sequences? Suppose a set J is feasible, we can arrange it in a way such that the corresponding deadlines is ordered according to the increasing values, say j1, . . . , jk such that dj1 ≤ . . . ≤ djk . Example: A scheduling problem ai

1

2

3

4

5

6

7

di

4

2

4

3

1

4

6

wi

70

60

50

40

30

20

10

The final solution is a2 → a4 → a1 → a3 → a7.

Jiming Peng, AdvOL, CAS, McMaster

7

Proof of Correctness The correctness of the algorithm: suppose that the greedy method chooses the set I and the optimal set is J with J 6= I. We consider only two feasible sequences. Suppose that the job a is scheduled in SI and the corresponding position of SJ is a gap. Then J ∪{a} is feasible with more profit. This is impossible. similarly one can see that if b is scheduled in Sj , then the corresponding position of SI must be scheduled as well. Suppose there are two jobs a and b with a 6∈ J, b 6∈ I at the same position of SI and SJ . The case ga > gb is impossible since otherwise J − {b} ∪ {a} is feasible and more profitable than the optimal J. If gb > ga, then J − {a} ∪ {b} is feasible and the greedy algorithm would have chosen b before a. Therefore only the case ga = gb remains. This shows the greedy algorithm works well.

Jiming Peng, AdvOL, CAS, McMaster

8

Travelling Salesman Problem An counterexample Problem: One is given costs between a certain number of cities or towns. The travelling salesman wants to leave one of these towns, to visit each other town exactly once, and to arrive back at the starting point with the minimal cost. The cycle is called Hamilton cycle. A greedy algorithm for TSP Input:

A cost matrix C over the set V ;

Output: A cycle traverses each vertices. begin set G = ({1, . . . , n}, ∅); set i := 1; V := V − {1}; For k = 1 to n − 1; Choose j be some vertex in V minimizing cost c(i, j); V = V − {j}; Add the edge (i, j) to G; i := j; Add the edge (i,1) to G. end The greedy heuristic does not guarantee optimal solution, instead it might give the worst solution.

Jiming Peng, AdvOL, CAS, McMaster

9

A TSP Example V1

10

20

12

14

15

V2

V4 V3 10

TSP EXAMPLE

1--2--3--4--1: 54 1--3--2--4--1: 61 1--3--4--2--1: 47 Jiming Peng, AdvOL, CAS, McMaster

10

Minimum cost spanning tree Problem: A MST is a tree that consists of all vertices of graph and has the least total cost. Applicable in a commercial network. The greedy algorithm builds the tree step by step. Starting with a graph includes only vertices. At each step one add the minimal cost edge not already in the graph whose inclusion still yields trees (no cycle in the graph). Ties can be arbitrary. Repeat this process n − 1 times until a single tree appears. Observation: The edge with minimal cost should be in the MCST. Otherwise by adding it, we get a cycle, and we can replace one edge by the edge with minimal cost, then we get another spanning tree with less cost. This is a contradiction!

Jiming Peng, AdvOL, CAS, McMaster

11

Design of The Algorithm Induction Hypothesis: We know how to find the MCST for connected graph with < n edges. Can we use the observed fact to reduce the graph to a smaller one? No, since removing one edge might change the graph into two independent graphs, and affect the choice of other edges as well. A stronger hypothesis: Given a graph G = (V, E), we know how to find a subgraph T with k edges such that T is a subtree of MCST of G.

Jiming Peng, AdvOL, CAS, McMaster

12

Algorithm for MCST If T is known. We consider how to add more edges to T . Since T is a part of MCST, there must one edge in MCST that connect T to a vertex not in T . Let Ek be the set of edges connecting T to vertices not in T . We claim that the edge e = (u, w) in Ek with minimal cost must be in MCST. Suppose to the converse that the claim is not true. Obviously MCST contains a path from u to w. Because (u, w) 6∈ M CST , there exists at least one edge (x, y) that connects T to a vertex not in T . The cost of this edge is higher than that of (u, w). Now we can replace it by (u, w), we get a spanning tree with less cost, a contradiction! Question: Is the least cost edge linked to any vertex in MCST?

Jiming Peng, AdvOL, CAS, McMaster

13

Algorithm MCST Input: G Output: MCST Begin T := Ø; for all v do v.mark := f alse, v.cost := ∞; Select the least cost edge (vi, vj ); vi.mark := true; for all edges (vi, vk ) do vj .edge := (vi, vj ), vj .cost := cost(vi, vj ); While there exists an unmarked vertex Do Select the least cost unmarked vertex vk ; If vk .cost = ∞, then stop (G is not connected) else vk .mark = true, add vk .edge to T; for all edges (vk , vj ) do If vj .mark = f alse then if cost(vk , vj ) < vj .cost then vj .edge := (vk , vj ), vj .cost := cost(vk , vj ) End

Jiming Peng, AdvOL, CAS, McMaster

14

Example: Finding MCST:1 a

10

i

4

g

2

6

5

7

3

f

8

h b

5

9

c

a

d

11

10

i

4

6

3

e

14

g

3

7

5

6

2 f

8

h b

5

9

c

a

d

11

10

i

4

6

3

e

14

g

3

5

7

6

2 f

8

h b

5

9

c

11

Jiming Peng, AdvOL, CAS, McMaster

d

14

6

3

e

15

Example: Finding MCST:2 a

10

i

4

g

2

6

5

7

3

f

8

h b

5

9

c

a

d

11

10

i

4

6

3

e

14

g

3

7

5

6

2 f

8

h b

5

9

c

a

d

11

10

i

4

6

3

e

14

g

3

5

7

6

2 f

8

h b

5

9

c

11

Jiming Peng, AdvOL, CAS, McMaster

d

14

6

3

e

16

Final MCST a

10

i

4

g

2

6

5

7

3

f

8

h b

5

9

c

a

10

i

4

d

11

6

3

14

e

g

3

5

7

6

2 f

8

h b

5

9

c

11

Final MCST

d

14

6

3

e