Optimality Conditions




Yüklə 67.17 Kb.
tarix08.04.2016
ölçüsü67.17 Kb.
OR 215 Spring 1998

Network Flows M. Hartmann

MINIMUM COST SPANNING TREE PROBLEM II


Optimality Conditions


Prim’s Algorithm

Sensitivity Analysis



OPTIMALITY CONDITIONS

Theorem. (Cut optimality theorem) A spanning tree T* is a minimum spanning tree if and only if it satisfies the following cut optimality condition:


  • For every tree arc (i,j) T*, cij ckl for every arc (k,l) contained in the cut formed by deleting arc (i,j) from T*.



Theorem. (Path optimality theorem) A spanning tree T* is a minimum spanning tree if and only if it satisfies the following path optimality condition:


  • For every non-tree arc (k,l) of G, cij ckl for every arc (i,j) contained in the path of T* connecting nodes k and l.



Recall: The path optimality condition leads to Kruskal’s greedy algorithm.

Theorem. Let F be a subset of arcs of some minimum cost spanning tree. Let P be the set of nodes of some component of F. Let (i,j) be a minimum cost arc in the cut (P,N\P). Then F+(i,j) is a subset of arcs of some minimum cost spanning tree.
Proof: Suppose that F is a subset of the minimum cost tree T*. If (i,j) T*, there is nothing to prove. So suppose that (i,j) T*. Adding (i,j) to T* creates a cycle C, and C has at least on arc (k,l)  (i,j) in (P,N\P). (Why?) By assumption, cij  ckl. Also, T* satisfies the cut optimality conditions, so cij  ckl. It follows that cij = ckl, and that

T*+(i,j)\ (k,l) is also a minimum cost spanning tree.






  • How can we take advantage of this property?

PRIM’S ALGORITHM

Prim's algorithm grows a spanning subtree rooted at node 1, which is a subset of arcs of some minimum cost span-ning tree.



To identify the arc (i,j), Prim’s algorithm maintains labels d(j) for each node j not yet added to the spanning tree:

d(j) = minimum cost of an arc (i,j) with i P

Prim’s algorithm also keeps track of which node i P has cij = d(j) by setting pred(j) := i.



algorithm PRIM;

begin

P := {1} ; T := N \ {1}; F := ;

d(1) := 0 and pred(1) := ;

d(j) := c1j and pred(j) := 1 for all (1,j) A ,

and d(j) :=  otherwise;

while P  N do

begin

{ node selection, also called FINDMIN }

let i T be a node with d(i) = min { d(j) : j T };

P := P  { i }; T := T \ { i }; add (i,pred(i)) to F;

{ cost update }

for each (i,j) A(i) do

if d(j) > cij then d(j) := cij and pred(j) := i;

end;

end


  • Where have we seen this algorithm before?


algorithm DIJKSTRA;

begin

P := {1} ; T := N \ {1};

d(1) := 0 and pred(1) := ;

d(j) := c1j and pred(j) := 1 for all (1,j)  A ,

and d(j) :=  otherwise;

while P  N do

begin

{ node selection, also called FINDMIN }

select a node i  T with d(i) = min { d(j) : j  T };

P := P  { i }; T := T \ { i };

{ distance update }

for each (i,j)  A(i) do

if d(j) > d(i) + cij then

d(j) := d(i) + cij and pred(j) := i ;



end;

end


RUNNING TIME




Naïve Implementation:

Prim’s algorithm can be implemented using heaps.

Recall that the standard heap implementation has the following running times per operation:
FIND-MIN: O(1)

DECREASE-KEY: O(log n)

DELETE-MIN: O(log n)

INSERT: O(log n)



Heap Implementation:

Note: Prim’s algorithm can also be implemented using Fibonacci heaps in O(m+n log n) time.

EXAMPLE

The set F of arcs is "grown" starting from node 1:




1 2 3 4 5



d( )

0

35

40







1 2 3 4 5

d( )

0

35

25

10





1 2 3 4 5



d( )

0

35

20

10

30



1 2 3 4 5

d( )

0

35

20

10

15







35

20

25

10

30

15

40

1 2 3 4 5

d( )

0

35

20

10

15


SENSITIVITY ANALYSIS


Suppose that T* is a minimum cost spanning tree. For any arc (i,j)  A, the cost interval of (i,j) is the range of values of cij for which T* continues to be a minimum cost spanning tree.





  • How can we find the cost interval of an arc (i,j)  T*?





  • How can we find the cost interval of an arc (i,j)  T*?



COMPREHENSIVE SENSITIVITY ANALYSIS


  • How much time does it take to find the cost intervals for every arc (i,j)  T*?


max-cost arc in path from i to j






1

2

3

4

5

1
















2
















3
















4
















5
















In the homework, you will show that all of these values can be computed in O(n2) time.



  • How much time does it take to find the cost intervals for every arc (i,j)  T*?







SUMMARY





  1. The minimum cost spanning tree (MST) problem is an important problem in its own right.




  1. The MST problem is also an important sub-problem.




  1. The greedy algorithm works.




  1. Other very efficient algorithms.




  1. Sensitivity analysis can be performed efficiently.


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə