OPTIMAL BINARY SEARCH TREES (Contd..) :1 OPTIMAL BINARY SEARCH TREES (Contd..) The expected cost of the tree is P(K)+COST(L)+COST(R)+W(0,k-1)+W(k,n)…….....(3)
If T is optimal then (3) must be minimum over all binary search trees containing a1,…ak-1 and E0,E1,…..,Ek-1
Similarly cost(R) must be minimum.
Let C(i,j) represent the cost of the tree Tij (containing nodes ai+1,……aj and Ei,…..,Ej).
Then cost(l) = C(0,k-1) and cost(R) =C(k,n) substituting for cost(l) and cost(R) in (3),
OPTIMAL BINARY SEARCH TREES (Contd..) :2 OPTIMAL BINARY SEARCH TREES (Contd..) The expected cost of the search tree is
P(k)+C(0,k-1)+C(k,n)+W(0,k-1)+W(k,n)…..(4) is minimum if k is chosen such that (4) is minimum cost of the BST with nodes a1,a2,…..,an and E0,….,En
C(0,n)=min{C(0,k-1)+C(k,n)+P(k)+W(0,k-1)+W(k,n)}…..(5)
1<=k=n
substitute i instead of 0 and j instead of n in (5)
C(I, j) = min { C(I, k-1)+ C (k, j)+ P (k) + W(I, k-1) + W (k, j)}
= min {C(i,k-1)+C(k,j)+W(i,j)}…………..(6)
i
OPTIMAL BINARY SEARCH TREES (Contd..) :3 OPTIMAL BINARY SEARCH TREES (Contd..) Equation (6) may be solved for C(0,n) by first computing C(i,j) such that j-i=1 (C(i,i)=0 and W(i,i)=Q(i),0=i=n)
We can compute all C(i,j) such that j-i = 2, then all C(i,j) with j-i=3 etc.
If during these computations, the root R(i,j) of each tree Tij is recorded, then OBST may be constructed.
Optimal Binary Search Trees – Example :4 Optimal Binary Search Trees – Example Example: Let n = 4 and (a1,a2,a3,a4) = (do, if, read, while)
Let P(1:4)=(3,3,1,1) and Q(0:4)=(2,3,1,1,1) .
P’s and Q’s have been multiplied by 16 for convenience.
Initially ,W(i,j) = Q(i), C(i,i) = 0, R(i,i) = 0 , 0=i=4
J j-1
W(i,j) =Q(i) +? Q(l) +P(l) =P(j) +Q(j) +Q(i) + ? Q(l) +P(l)
l=i+1 l=i+1 ….…(7)
= P(j) +Q(j) +W(i,j-1)
Optimal Binary Search Trees – Example (contd..) :5 Optimal Binary Search Trees – Example (contd..) C(i,j) = min{C(i,k-1)+C(k,j)} +W(i,j)……….…(8)
i
Optimal Binary Search Trees – Example (contd..) :6 Optimal Binary Search Trees – Example (contd..) W(1,2) =P(2) +Q(2) +W(1,1) =P(2) +Q(2) +Q(1) =3+1+3 =7
C(1,2) =W(1,2) +min{C(1,1) +C(2,2)}=7 +min{0,0)=7
R(1,2) =2
W(2,3) =P(3) +Q(3) +W(2,2) =3 k = 2
C(2,3) =W(2,3) +min{C(2,2)+C(3,3)} =3 k = 3
R(2,3) =3
W(3,4) =P(4) +Q(4) +W(3,3) =1+1+Q(3) =3
C(3,4) =W(3,4) +min{C(3,3) +C(4,4)} =3 k = 4
R(3,4) =4
Optimal Binary Search Trees – Example (contd..) :7 Optimal Binary Search Trees – Example (contd..) Knowing W(i,i+1), and C(i,i+1) 0=i<4 , we are computing W(i,i+2) ,C(i,i+2) R(i,i+2) 0=i<3
This process may be repeated until W(0,4) ,C(0,4) and R(0,4) are obtained
Using R(i,j) let us see how to construct an OBST.
C(o,4)=32 is the minimum cost of BST for
{ a1, a2, a3, a4}.
do, if, read, while
Optimal Binary Search Trees – Example (contd..) :8 Optimal Binary Search Trees – Example (contd..) The root of tree T04 is a2
?R(0,4)=2
The left sub-tree of T04 is T01 and right sub-tree is T24.
R (0, 1) =1 a1 is the root of T01,
R (2, 4) =3
? a3 is root of T24,
T01 has T00 and T11 as sub-trees , T24 has T22 and T34
For T00,T11 and T22 the root is 0, T24 it is 4.
Optimal Binary Search Trees – Example (contd..) :9 Optimal Binary Search Trees – Example (contd..) a2={if}
if
do Read
while
OBST
Optimal Binary Search Trees – Example (contd..) :10 Optimal Binary Search Trees – Example (contd..) We can verify that the cost of OBST
= ?P (i) level (ai)+?Q(i) (level(Ei)-1)
1=i=n 0=i=n
= 2×3+1×3+2×1+3×1+2×2+2×3+2×1+3×1+3 ×1
= 6+3+2+3+4+6+2+3+3 = 32
COMPLEXITY OF THE PROCEDURE FOR CONSTRUCTING OBST :11 COMPLEXITY OF THE PROCEDURE FOR CONSTRUCTING OBST C(i,j)=min{C(i,k-1)+C(k,i)}+w(i,j)
i
COMPLEXITY OF THE PROCEDURE FOR CONSTRUCTING OBST (Contd..) :12 COMPLEXITY OF THE PROCEDURE FOR CONSTRUCTING OBST (Contd..) The total time to evaluate all the C (i,j)s and R(i,j)s is
?(nm-m2) = n?m-?m2 = n (m)(m+1)/2
– m (m+1)(2m+1)/6 = 0(n3)
1=m=n
COMPLEXITY OF THE PROCEDURE FOR CONSTRUCTING OBST (Contd..) :13 COMPLEXITY OF THE PROCEDURE FOR CONSTRUCTING OBST (Contd..) The complexity can be reduced to 0(n2) using D.E.Knuth’s result which limits the search to the range
R(i,j-1)=k=R(i+1,j), instead of min{C(i,k-1)+C(k,i)}+w(i,j)
1
ALGORITHM FOR OBST :14 ALGORITHM FOR OBST PROCEDURE OBST (P,Q,n)
// Given n distinct identifiers a1
ALGORITHM FOR OBST (Contd..) :15 ALGORITHM FOR OBST (Contd..) for i?0 to n-1 do
(w (i,i), R(i,i),C(i,i) )? (Q (i), 0, 0)
(w (i,i+1), R(i,i+1),C(i,i+1)?
Q(i)+Q(i+1)+P(i+1), i+1, Q(i)+Q(i+1)+P(i+1)
// optimal trees with one node //
repeat
(w(n,n),R(n,n),C(n,n) ) ? (Q (n), 0, 0)
for m?2 to n do // find optimal //
for i?0 to n-m do // trees with m //
j?i+m // nodes //
ALGORITHM FOR OBST (Contd..) :16 ALGORITHM FOR OBST (Contd..) w(i,j)?w(i,j-1)+P(j)+Q(j)
k?a value l in the range
R (i,j-1)=l=R(i+1,j) that
Minimizes{C (i, l-1) +C (l,j)}
C(i,j)=w(i,j)+C(i,k-1)+C(k,j)
R (i,j)?k
Repeat
Repeat
End OBST
0/1 KNAPSACK PROBLEM :17 0/1 KNAPSACK PROBLEM The solution of 0/1 knapsack problem is a sequence of decisions on x1,…, xn and the total profit; x1,…..,xn may be 0 or 1.
Let fj(X) be the value of are optimal solution to KNAP (1, j, X).
Since the principle of optimality holds
fn (M) = max {fn-1(M) (Corresponding to xn=0),
fn-1(M-wn) +pn} (corresponding to xn=1)
0/1 KNAPSACK PROBLEM (Contd..) :18 0/1 KNAPSACK PROBLEM (Contd..) In general
fi(X)=max{fi-1(X), fc-1(X-wi)+pi}….(1)
(1) may be solved by beginning with f0(X)=0 for all X and fi(X)= -8 for X<0 ,f1,…,fn may be solved successively.
EXAMPLE:-
Let n=3, (w1,w2,w3) = (2,3,4);
(P1,P2,P3) = (1,2,3), M= 6
0/1 KNAPSACK PROBLEM (Contd..) :19 0/1 KNAPSACK PROBLEM (Contd..) SOLUTION:
f0(X) = 0 ?X, fi(X) = -8 if X<0
f0 (6) = 0
f1(6) = max{f0(6), f0(6-2)+1} = max {0,1} = 1
f2(6) = max{f1(6), f1(6-3)+2} = max{1,f1(3)+2}
f1(3) = max{f0(3), f0(3-2)+1} = max{0,1}=1
f2(6) = max {1, 3} =3
f3(6) = max{f2(6), f2(6-4)+5}=max{3, f2(2)+5}
f2(2) = max{f1(2), f1(2-3)+2}=max{1, f1(-1)+2} = 1
(as f1 (-1) = -8)
? f3(6)=max{3,f2(2)+5}=max{3,6}=6
0/1 KNAPSACK PROBLEM (Contd..) :20 0/1 KNAPSACK PROBLEM (Contd..) Similarly we can compute f1 (1) = 0, f2 (1) = 0, f1 (2) =1 and f2 (3) =2
Each fi is completely specified by the pairs (Pj,Wj) where Wj is a value of X at which fi takes a jump Pj=fi(Wj) and (P0,W0)=(0,0) is introduced .
As we always choose maximum profit, if Wj
0/1 KNAPSACK PROBLEM (Contd..) :21 0/1 KNAPSACK PROBLEM (Contd..) Also fi(X)=fi(Wi) for all X such that Wj=XWr .
(fj(X) is the value of an optimal solution to KNAP(1,j,X)
(For such X’s as 2.5, 3.5, we do not have the profit, so we assign the previous profit.)
Let us define the sets Si-1, Si1 and Si as follows.
Also fi(X)=fi(Wi) for all X such that Wj=XWr .
(For such X’s as 2.5, 3.5, we do know the profit, so we assign the previous profit.)
0/1 KNAPSACK PROBLEM (Contd..) :22 0/1 KNAPSACK PROBLEM (Contd..) Let us define the sets Si-1, Si1 and Si as follows.
Si-1 is the set of all pairs (p, w) for fi-1 including (0, 0).
Si1= {(p, w)/ (P-pi, W-wi) ?Si-1}
(This is the set of pairs for fi(X) =fi-1(X-wi) + pi)
Si is obtained by merging together Si-1 and Si1. (This corresponds to maximum of fi-1(X) and fi-1(X-wi)+pi.
0/1 KNAPSACK PROBLEM (Contd..) :23 0/1 KNAPSACK PROBLEM (Contd..) If one of Si-1 and Si1 has pair (pj,wj) and the other has a pair (pk,wk) and pj=pk while wj=wk then the pair (pj,wj) is discarded.
This is known as dominance rule or purging rule (pk,wk) dominates (pj,wj).
For example
S0 contains tuples when x1 = 0. ?p1 = 0 ; w1 = 0 ?S0={0,0}
S11 contains tuples when x1 =1 ?p1 = 1; w1 = 2 ?S11={(1,2)}
S1 contains tuples when x1 = 0 and x1 = 1 ?S1 = {(0,0), (1,2)}
0/1 knapsack problem example :24 0/1 knapsack problem example n = 3, (w1, w2, w3) = (2,3,4), (p1,p2,p3)= (1,2,5) and M=6.
S0 = {0, 0}; S11 is obtained by adding (p1, w1)=(1, 2) to (0, 0) Thus S11 = {(1,2)} ; S1 is obtained by combining S0 and S1
Hence S1 = {(0, 0), (1, 2)}; S21= {(2, 3), (3, 5)} adding
(2, 3) to elements of S1
S2 ={(0,0),(1,2), (2,3),(3,5)}; S31={(5,4),(6,6),(7,7),(8,9)}
S3 ={(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9)}
The pair (3,5) ahs eliminated from S3 as 34. (Using purging rule (3,5) is discarded.
0/1 knapsack problem example (contd..) :25 0/1 knapsack problem example (contd..) computation of xi’s is as follows:
Consider the Last value in Sn. Let it be (P, W).
So, we need to determine x1,x2,x3,….,xn such that ?pixi= P and ?wixi=W check if (p,w) is also in Sn-1 .
1=i=n 1=i=n
If (p, w) ?Sn-1then set xn= 0 otherwise xn=1 (p, w) has come from (P-Pn, W-Wn).
Now check (P-Pn, W-Wn) ?Sn-1also belongs to Sn-2 or not
If it is xn-1= 0 otherwise xn-1= 1.
The process is repeated.
0/1 knapsack problem example (contd..) :26 0/1 knapsack problem example (contd..) Let us apply this procedure to the example M = 6.
The last tuple in S3 is (6, 6) (6,6) ?S2 so x3=1.
(6,6) came from 6-P3, 6-W3=(1,2) (1,2) ?S2 and (1,2) is also in S1 so set x2=0.
(1, 2) ?S0 so x1= 1.
Hence an optimal solution is (x1,x2,x3) = (1,0,1) .
Informal Knapsack Algorithm :27 Informal Knapsack Algorithm Procedure DKP (P,W,n,M)
S0= {0, 0)}
For i?1 to n do
Si1? {(P1, W1)/P1- pi,W1-wi ?Si-1 and W1=M}
// Si1 is constructed by adding (pi,wi) to tuples in Si-1 //
Si? MERGE-PURGE (Si-1, Si1)
repeat
(PX, WX)? Last tuple in Sn-1
Informal Knapsack Algorithm (Contd..) :28 Informal Knapsack Algorithm (Contd..) (PY, WY)? (P1+Pn, W1+Wn) where W1 is the largest integer W in any tuple in Sn-1 such that W+Wn=M
// compute xn// // As PX is in Sn-1 and //
// PY is in Sn, PX>PY //
if PX>PY then xn? 0 else xn? 1 // means we need not
end if
// choose PY, so Xn?0 //
// compute similarly xn-1…x1 //
end DKP
INFORMAL KNAPSACK ALGORITHM (Contd..) :29 INFORMAL KNAPSACK ALGORITHM (Contd..) In implementation P, W are treated as one-dimensional arrays.
Pointers F(i) i= 0,1,…,n with F(i) pointing to the first element in Si 0=i=n and F(n) pointing to one more than the last element in Sn-1 are used
Detailed knapsack algorithm :30 Detailed knapsack algorithm Procedure DKNAP(p,w,n,M,m)
Real p(n), w(n), p(m), w(m), pp, ww, M
Integer F(0:n), l, h, u, i, j, p, next // p(n), w(n) are //
F(0)? 1; P(1)? W(1)? 0 // S0 // // given arrays //
l? h? 1 // start and end of S0 // // p(m), w(m) are //
// computed pair //
F(1)? next? 2 // next free spot in P and W //
4 for i? 1 to n do
Detailed knapsack algorithm (Contd..) :31 Detailed knapsack algorithm (Contd..) k? l // k is the temporary index for tuples in Si-1 //
6 u? largest k such that l=k=h and W(k)+ Wi=M
// this is to remove tuples like(7,7), (8,9) in S3 in the example //
// k is 2 in S2 //
// so, k points to the next tuple in Si-1 that has to be merged //
// into Si // // pairs for which Wj+Wi >M are not generated//
7 for j? l to u do // generate Si1 and merge //
Detailed knapsack algorithm (Contd..) :32 Detailed knapsack algorithm (Contd..) 8 (pp, ww)? (P(j)+pi, W(j)+wi)
// next element in Si //
9 while k=h and W(k) = ww do
P(next)? P(k); W(next)?W(k)
next? next+1; k?k+1
12 repeat
13 if k=h and W(k)= ww then pp? max(pp, P(k));
14 k?k+1;
15 endif
Detailed knapsack algorithm (Contd..) :33 Detailed knapsack algorithm (Contd..) 16 if pp>P(next-1) then (P(next),W(next))?(pp,ww);
17 next?next+1
18 endif
19 while k=h and P(k)=P(next-1) do
//use purging rule //
20 k?k+1
repeat 21
repeat 22
Detailed knapsack algorithm (Contd..) :34 Detailed knapsack algorithm (Contd..) // merge m remaining terms from Si-1 //
23 while k=h do
24 (P(next), W(next)? P(k), W(k))
25 next?next+1; k?k+1
26 repeat
// initialize for Si-1 //
27 l?h+1; h?next-1; F(i+1)? next
28 repeat
29 call PARTS // parts implements lines 8-9 //
30 end DKNAP // of DKP i.e. computations of xi s//
Detailed knapsack algorithm (Contd..) :35 Detailed knapsack algorithm (Contd..) Example:
n=3, M=6, (w1,w2,w3) = (2,3,4), (p1,p2,p3)= (1,2,5)
S0= {0,0}; S11= {(1,2)} S1={(0,0), (1,2)}; S21= {(2,3), (3,5)}
S2= {(0,0), (1,2), (2,3), (3,5)}; S31={ (5,4), (6,6), (7,7), (8,9)}
S3= {(0,0), (1,2), (2,3), (5,4), (6,6), (7,7), (8,9)
Detailed knapsack algorithm (Contd..) :36 Detailed knapsack algorithm (Contd..) Let us see how S3 is generated using the procedure DKNAP
1 2 3 4 5 6 7 8 9 10 11 12
P 0 0 1 0 1 2 3 0 1 2 5 6
W 0 0 2 0 2 3 5 0 2 3 4 6? ? ? ?
F(0) F(1) F(2) F(3)
l?4 h?7 F(2+1)= F(3)?Next= 8 (line 27)
k?l = 4
Detailed knapsack algorithm (Contd..) :37 Detailed knapsack algorithm (Contd..) u?largest k such that 4=k=7 and W(k)+w3=6
such k is 5 because w3= 4 and 4+2=6
4+3= 7>6 and 4+5= 9>6
Now S31 is generated and merged with S2 in lines 7-22,
The addresses of sitting of set Si are stored in the array F(I) F(0) ? 1 m3ans F(0) is pointing to 1st pair or address of first pair is p.
Detailed knapsack algorithm (Contd..) :38 Detailed knapsack algorithm (Contd..) for j?4 to 5 do (Line 7) 4 5 6 7
(pp,ww)?P(4)+p3, W(4)+w3= (5,4) (P,W) (0,0) (1,2) (2,3) (3,5)
(p3, w3)= (5,4)
In lines 9-12 with k=4,5,6
P(8) = 0, W(8) = 0; (P(9), W(9)) = (1,2); (P(10), W(10)) = (2,3)
(P(11), W(11)) = (2,3) are generated, while is exited with k = 7
as W(7) = 5> ww = 4 and next?11
Detailed knapsack algorithm (Contd..) :39 Detailed knapsack algorithm (Contd..) Line 13 is not true for any k as W(k) ? ww = 4
In lines 16-18 (5,4) = (pp, ww) is included in S3 ,
as pp= 5> P(next-1)= P(10)=2 i.e. profit gained till now.
?(P(11), W(11)) = (5,4) and next?12
In lines 19-21 P(7) = 3=P(11) = 5 so (3,5) is not included.
Hence k is incremented to 8 // W(k) = ww but P(k)<=pp //
Detailed knapsack algorithm (Contd..) :40 Detailed knapsack algorithm (Contd..) Similarly with j?5 (pp,ww)?(P(5)+p3, W(5)+w3) = (6,6)
And in lines 16-18 (P(12), W(12)) = (6,6)is included in S3
Lines 23-25 for W(k) = ww and P(k) = pp case, which in this example are not entered as k is 8 for j?5 and where k is 7 for j? -4 p(k)=pp.
Detailed knapsack algorithm (Contd..) :41 Detailed knapsack algorithm (Contd..) Thus S3 is {(0,0), (1,2), (2,3), (5,4), (6,6)}
Which is {(P(8), W(8)), (P(9),W(9)), (P(10), W(10)), (P(11),W(11)), (P(12), W(12))}.
F(3) = 8 is pointing to the start of this array i.e. (P(8), W(8)).
THE TRAVELING SALESPERSON PROBLEM :42 THE TRAVELING SALESPERSON PROBLEM 0/1 Knapsack problem is a subset selection problem. Given n objects there are 2n different subsets of objects.
The solution is one of there 2n subsets.
In permutation problems like Traveling Salesperson Problem(TSP) there are n! different permutations of n objects. (n!>2n).
THE TRAVELING SALESPERSON PROBLEM (Contd..) :43 THE TRAVELING SALESPERSON PROBLEM (Contd..) TSP problem is as follows:
Let G = (V,E) be directed graph with edge costs Cij. Cij>0 for all i and j and Cij = +8 if ?E.
Let |V|=n and assume n>1.
A tour of G is a directed cycle that includes every vertex in V.
The cost of a tour is the sum of the cost of the edges on the tour.
The TSP problem is to find a tour of minimum cost.
THE TRAVELING SALESPERSON PROBLEM (Contd..) :44 THE TRAVELING SALESPERSON PROBLEM (Contd..) Applications of TSP:-
A postal van is to pick up mail from mail boxes located at n different sites. The route taken by a postal van is a tour and the problem is to find a tour of minimum length.
A minimum cost tour of a robot arm used to tighten the nuts on some piece of machinery on an assembly line will minimize the time needed for the arm to complete its task.
TSP AND THE PRINCIPLE OF OPTIMALITY :45 TSP AND THE PRINCIPLE OF OPTIMALITY Assume a tour to be a simple path that starts and ends at vertex 1.
Every tour consists of an edge for some k ? V-{1} and a path from vertex k to vertex 1.
The path from vertex k to vertex 1 goes through each vertex in V-{1,k} exactly once.
If the tour is optimal, then the path from k to 1 must be a shortest k to 1 path going through all vertices in V-{1,k}.
Hence the principle of optimality holds.
TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) :46 TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) Let g(i,S) be the length of a shortest path starting at vertex I, going through all vertex in S and terminating at vertex 1.
g(1, V-{1}) is the length of an optimal salesperson tour.
Form the principle of optimality, it follows that
g(1, V-{1})= min{C1k+g(k,V-{1,k})} ……(1)
2=k=n (forward approach)
TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) :47 TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) In general, for i?S,
g(I,S)= min{Cij+g(j, S-{j})}………..(2)
j?s
(1) may be solved for g(1, V-{1}) if we know g(k, V-{1,k}) for all choices of k.
There values are obtained from (2)
g(i,Ø) = Ci1 1=i=n.
g(i,Ø) is the length of the shortest path starting at i going through no vertex and ending at 1.
TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) :48 TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) Using equation (1), We obtain g(i,S) for all S of size 1, then for all S of size 2 etc.
For all |S|
TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) :49 TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) Let us solve the problem using dynamic programming approach.
As g(i,Ø) = Ci1 1=i=n
g(2,Ø) = C21= 5; g(3,Ø) = C31= 6; g(4,Ø) = C41 = 8
we know that
g(i,S) = min{Cij+g(j, S-{j})}
j ?S
for |S|=1
g(2,{3}) = C23+g(3,Ø) = 9+6 = 15
g(2,{4}) = C24+g(4,Ø) = 10+8 = 18
g(3,{2}) = C32+g(2,Ø) = 13+5 = 18
g(4,{2}) = C42+g(2,Ø) = 8+5 = 13
g(4,{3}) = C43+g(3,Ø) = 9+6 = 15
TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) :50 TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) Next, we compute g (i,S) with | S | = 2 i ? 1, 1 ? S, i ? S
g (2, {3,4}) = min { C23 + g (3,{4}), C24 + g (4, {3})
= min { 9+20, 10+15 } = min { 29,25} = 25
g (3, {2,4}) = min { C32 + g (2,{4}), C34 + g (4, {2})
= min { 13+18, 12+13 } = min { 31,25} = 25
g (4, {2,3}) = min { C42 + g (2,{3}), C43 + g (3, {2})
= min { 8+15, 9+18 } = min { 23, 27} = 23
TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) :51 TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) We compute g (i,S) with | S | = 3
g (1, {2, 3, 4}) = min { C12 + g (2,{3,4}), C13 + g (3, {2,4})
, C14 + g (4, {2,3})
= min { 10 + 25, 15 + 25, 20+23 }
= min { 35, 40, 43 } = 35
Thus An optimal tour of the graph has length 35.
TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) :52 TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) The tour of this length may be constructed if we retain the value of j that minimizes each g(i,S) for
| S | = 3 and | S | = 2 and | S | = 1.
Let J (i,S) be the minimal tour.
J (1, {2,3,4}) = 2 as C12 + g(2,{3,4}) = 35 is the minimum.
TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) :53 TSP AND THE PRINCIPLE OF OPTIMALITY (Contd..) The remaining tour may be obtained from g(2, {3,4}).
? J (2, { 3, 4} ) = 4
J (4, { 3} ) = 3
? The optimal tour starts at 1 goes through the vertices 2, 4, 3 respectively and ends at 1.
i.e. 1,2,4,3, 1
Complexity of TSP = ?(n22n)
Space needed = ?(n2n)