482
Chapter10 AlgorithmDesignTechniques
M
1
=(A
1,2
A
2,2
)(B
2,1
+B
2,2
)
M
2
=(A
1,1
+A
2,2
)(B
1,1
+B
2,2
)
M
3
=(A
1,1
A
2,1
)(B
1,1
+B
1,2
)
M
4
=(A
1,1
+A
1,2
)B
2,2
M
5
=A
1,1
(B
1,2
B
2,2
)
M
6
=A
2,2
(B
2,1
B
1,1
)
M
7
=(A
2,1
+A
2,2
)B
1,1
Oncethemultiplicationsareperformed,thefinalanswercanbeobtainedwitheight
moreadditions.
C
1,1
=M
1
+M
2
M
4
+M
6
C
1,2
=M
4
+M
5
C
2,1
=M
6
+M
7
C
2,2
=M
2
M
3
+M
5
M
7
Itisstraightforwardtoverifythatthistrickyorderingproducesthedesiredvalues.The
runningtimenowsatisfiestherecurrence
T(N)=7T(N/2)+O(N
2
)
ThesolutionofthisrecurrenceisT(N)=O(Nlog
2
7)=O(N2.81).
Asusual,therearedetailstoconsider,suchasthecasewhenNisnotapowerof2,
butthesearebasicallyminornuisances.Strassen’salgorithmisworsethanthestraightfor-
wardalgorithmuntilNisfairlylarge.Itdoesnotgeneralizeforthecasewherethematrices
aresparse(containmanyzeroentries),anditdoesnoteasilyparallelize.Whenrunwith
floating-pointentries,itislessstablenumericallythantheclassicalgorithm.Thus,until
recentlyithadonlylimitedapplicability.Nevertheless,ithasalwaysrepresentedanimpor-
tanttheoreticalmilestoneandcertainlyshowsthatincomputerscience,asinmanyother
fields,eventhoughaproblemseemstohaveanintrinsiccomplexity,nothingiscertain
untilproven.
10.3 DynamicProgramming
Intheprevioussection,wesawthataproblemthatcanbemathematicallyexpressedrecur-
sivelycanalsobeexpressedasarecursivealgorithm,inmanycasesyieldingasignificant
performanceimprovementoveramorenaïveexhaustivesearch.
Anyrecursivemathematicalformulacouldbedirectlytranslatedtoarecursivealgo-
rithm, butthe underlying g reality is that often the compiler willnot dojustice tothe
recursivealgorithm,andaninefficientprogramresults.Whenwesuspectthatthisislikely
tobethecase,wemustprovidealittlemorehelptothecompiler,byrewritingtherecursive
algorithmasanonrecursivealgorithmthatsystematicallyrecordstheanswerstothesub-
problemsinatable.Onetechniquethatmakesuseofthisapproachisknownasdynamic
programming.
Table from pdf to powerpoint - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
export pdf into powerpoint; pdf to powerpoint converter
Table from pdf to powerpoint - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
how to convert pdf file to powerpoint presentation; convert pdf to editable ppt
10.3 DynamicProgramming
483
10.3.1 UsingaTableInsteadofRecursion
InChapter2,wesawthatthenaturalrecursiveprogramtocomputetheFibonaccinumbers
isveryinefficient.RecallthattheprogramshowninFigure10.40hasarunningtime,T(N),
thatsatisfiesT(N)≥T(N−1)+T(N−2).SinceT(N)satisfiesthesamerecurrencerelation
astheFibonaccinumbersandhasthesameinitialconditions,T(N)infactgrowsatthe
samerateastheFibonaccinumbersandisthusexponential.
Ontheotherhand,sincetocomputeF
N
,allthatisneededisF
N−1
andF
N−2
,weonly
needtorecordthetwomostrecentlycomputedFibonaccinumbers.ThisyieldstheO(N)
algorithminFigure10.41.
1
/**
2
* Compute Fibonacci i numbers as described d in Chapter 1.
3
*/
4
long long fib( ( int n n )
5
{
6
if( n n <= 1 1 )
7
return 1;
8
else
9
return fib( n - - 1 1 ) + fib( ( n n - 2 );
10
}
Figure10.40 InefficientalgorithmtocomputeFibonaccinumbers
1
/**
2
* Compute Fibonacci i numbers as described d in Chapter 1.
3
*/
4
long long fibonacci( int t n )
5
{
6
if( n n <= 1 1 )
7
return 1;
8
9
long long last = = 1;
10
long long last nextToLast = = 1;
11
long long answer r = = 1;
12
13
for( int t i i = 2; i <= n; ++i i )
14
{
15
answer = last + + nextToLast;
16
nextToLast = = last;
17
last = = answer;
18
}
19
return answer;
20
}
Figure10.41 LinearalgorithmtocomputeFibonaccinumbers
C# Word - Table Processing in C#.NET
C# Word - Table Processing in C#.NET. Provide C# Users with Variety of Methods to Setup and Modify Table in Word Document. Overview. Create Table in Word.
converting pdf to ppt; export pdf to powerpoint
C# Word - Table Row Processing in C#.NET
C# Word - Table Row Processing in C#.NET. How to Set and Modify Table Rows in Word Document with C#.NET Solutions. Overview. Create and Add Rows in Table.
how to change pdf to ppt on; pdf to ppt converter online for large
484
Chapter10 AlgorithmDesignTechniques
Thereasonthattherecursivealgorithmissoslowisbecauseofthealgorithmusedto
simulaterecursion.TocomputeF
N
,thereisonecalltoF
N−1
andF
N−2
.However,since
F
N−1
recursively makes acalltoF
N−2
and F
N−3
,thereareactually twoseparatecalls
tocomputeF
N−2
.Ifonetracesouttheentirealgorithm,thenwecanseethatF
N−3
is
computedthreetimes,F
N−4
iscomputedfivetimes,F
N−5
iscomputedeighttimes,and
soon.AsFigure10.42shows,thegrowthofredundantcalculationsisexplosive.Ifthe
compiler’srecursionsimulationalgorithmwereabletokeepalistofallprecomputedvalues
andnotmakearecursivecallforan alreadysolvedsubproblem,thenthisexponential
explosionwouldbeavoided.ThisiswhytheprograminFigure10.41issomuchmore
efficient.
As asecond example,wesaw in Chapter7 how tosolvethe recurrence C(N) =
(2/N)
N−1
i=0
C(i)+N, with C(0) = = 1.Supposethat t we want tocheck, numerically,
whetherthesolutionweobtainediscorrect.Wecould thenwritethesimpleprogram
inFigure10.43toevaluatetherecursion.
Onceagain,therecursivecallsduplicatework.Inthiscase,therunningtimeT(N)
satisfiesT(N)=
N−1
i=0
T(i)+N,because,asshowninFigure10.44,thereisone(direct)
recursivecallofeachsizefrom0toN−1,plusO(N)additionalwork(whereelsehavewe
seenthetreeshowninFigure10.44?).SolvingforT(N),wefindthatitgrowsexponentially.
F1
F0
F2
F1
F3
F1
F0
F2
F4
F1
F0
F2
F1
F3
F5
F1
F0
F2
F1
F3
F1
F0
F2
F4
F6
Figure10.42 TraceoftherecursivecalculationofFibonaccinumbers
1
double eval( ( int n )
2
{
3
if( n == 0 0 )
4
return 1.0;
5
else
6
{
7
double sum m = 0.0;
8
9
for( int i = 0; i i < < n; ++i )
10
sum += eval( i );
11
return 2.0 0 * sum / n n + + n;
12
}
13
}
Figure10.43 RecursivefunctiontoevaluateC(N)=2/N
N−1
i=0
C(i)+N
C# Word - Table Cell Processing in C#.NET
C# Word - Table Cell Processing in C#.NET. Online Tutorial for Users to Set and Modify Table Cells in Word Document. Overview. Create and Add Cells in Table.
converting pdf to powerpoint online; images from pdf to powerpoint
How to C#: Convert PDF, Excel, PPT to Word
Footnote & Endnote Processing. Table Row Processing. Table Cell Processing. VB.NET How-to, VB.NET PDF, VB.NET Word, VB.NET Excel, VB.NET PowerPoint, VB.NET Tiff
convert pdf to powerpoint slide; online pdf converter to powerpoint
10.3 DynamicProgramming
485
C1
C0
C2
C0
C3
C1
C0
C0
C4
C1
C0
C2
C0
C1
C0
C0
C5
C1
C0
C2
C0
C3
C1
C0
C0
C1
C0
C2
C0
C1
C0
C0
Figure10.44 Traceoftherecursivecalculationineval
1
double eval( ( int t n )
2
{
3
vector<double> c( n n + + 1 );
4
5
c[ 0 ] = = 1.0;
6
for( int t i i = 1; i <= n; ++i i )
7
{
8
double sum = = 0.0;
9
10
for( int t j = = 0; j j < i; ++j j )
11
sum += = c[ j j ];
12
c[ i i ] ] = = 2.0 0 * * sum m / i i + + i;
13
}
14
15
return c[ n n ];
16
}
Figure10.45 EvaluatingC(N)=2/N
N−1
i=0
C(i)+Nwithatable
Byusingatable,weobtaintheprograminFigure10.45.Thisprogramavoidstheredun-
dantrecursivecallsandrunsinO(N
2
).Itisnotaperfectprogram;asanexercise,you
shouldmakethesimplechangethatreducesitsrunningtimetoO(N).
10.3.2 OrderingMatrixMultiplications
Supposewearegivenfourmatrices,A,B,C,andD,ofdimensions= 50×10,=
10×40,C=40×30,andD=30×5.Althoughmatrixmultiplicationisnotcommutative,
itisassociative,whichmeansthatthematrixproductABCDcanbeparenthesized,and
thusevaluated,inanyorder.Theobviouswaytomultiply twomatricesofdimensions
p×qandq×r,respectively,usespqrscalarmultiplications.(Usingatheoreticallysuperior
C# Word - Header & Footer Processing in C#.NET
Create and Add Table to Footer & Header. The following demo code shows how to create table in footer and header. String docFilePath
convert pdf to powerpoint; pdf to ppt
How to C#: Overview of Using XDoc.Word
Rapidly load, create, and edit Word document (pages) in C# class library. Able to render and convert Word document to/from supported document (PDF and ODT).
how to convert pdf to powerpoint in; convert pdf to editable ppt online
486
Chapter10 AlgorithmDesignTechniques
algorithmsuch as Strassen’salgorithmdoesnotsignificantlyaltertheproblemwewill
consider,sowewillassumethisperformancebound.)Whatisthebestwaytoperformthe
threematrixmultiplicationsrequiredtocomputeABCD?
Inthecaseoffourmatrices,itissimpletosolvetheproblembyexhaustivesearch,
sincethereareonlyfivewaystoorderthemultiplications.Weevaluateeachcasebelow:
(A((BC)D)): Evaluating BC requires 10 0 ×40×30 0 = = 12,000 0 multiplications.
Evaluating(BC)Drequiresthe12,000multiplicationstocomputeBC,plusanaddi-
tional 10×30 ×5 5 = 1,500 0 multiplications, , for a a total l of 13,500. Evaluating
(A((BC)D))requires13,500multiplicationsfor(BC)D,plusanadditional50×10×
5=2,500multiplications,foragrandtotalof16,000multiplications.
(A(B(CD))):EvaluatingCDrequires40×30×5=6,000multiplications.Evaluating
B(CD)requiresthe6,000multiplicationstocomputeCD,plusanadditional10×40×
5=2,000multiplications,foratotalof8,000.Evaluating(A(B(CD)))requires8,000
multiplicationsforB(CD),plusanadditional50×10×5= 2,500multiplications,
foragrandtotalof10,500multiplications.
((AB)(CD)):EvaluatingCDrequires40×30×5=6,000multiplications.Evaluating
ABrequires50×10×40=20,000multiplications.Evaluating((AB)(CD))requires
6,000multiplicationsforCD,20,000multiplicationsforAB,plusanadditional50×
40×5=10,000multiplicationsforagrandtotalof36,000multiplications.
(((AB)C)D): Evaluating AB requires 50 0 ×10×40 0 = = 20,000 0 multiplications.
Evaluating(AB)Crequiresthe20,000multiplicationstocomputeAB,plusanaddi-
tional50×40×30 = = 60,000multiplications,foratotalof f 80,000.Evaluating
(((AB)C)D)requires80,000multiplicationsfor(AB)C,plusanadditional50×30×
5=7,500multiplications,foragrandtotalof87,500multiplications.
((A(BC))D): Evaluating BC requires 10 0 ×40×30 0 = = 12,000 0 multiplications.
EvaluatingA(BC)requiresthe12,000multiplicationstocomputeBC,plusanaddi-
tional50×10×30 = = 15,000multiplications,foratotalof f 27,000.Evaluating
((A(BC))D)requires27,000multiplicationsforA(BC),plusanadditional50×30×
5=7,500multiplications,foragrandtotalof34,500multiplications.
Thecalculationsshowthatthebestorderingusesroughlyone-ninththenumberof
multiplicationsastheworstordering.Thus,itmightbeworthwhiletoperformafewcal-
culationstodeterminetheoptimalordering.Unfortunately,noneoftheobviousgreedy
strategies seems to work.Moreover, the number of possible orderings grows quickly.
Supposewe defineT(N)tobethisnumber.ThenT(1) ) = T(2) ) = 1,T(3) = = 2,and
T(4)=5,aswehaveseen.Ingeneral,
T(N)=
N−1
i=1
T(i)T(Ni)
To see e this, , suppose that the matrices are A
1
,A
2
,...,A
N
, and d the e last multiplica-
tionperformedis(A
1
A
2
···A
i
)(A
i+1
A
i+2
···A
N
).ThenthereareT(i)waystocompute
(A
1
A
2
···A
i
)andT(Ni)waystocompute(A
i+1
A
i+2
···A
N
).Thus,thereareT(i)T(Ni)
waystocompute(A
1
A
2
···A
i
)(A
i+1
A
i+2
···A
N
)foreachpossiblei.
C# Word - Document Processing in C#.NET
0); //Save the document doc0.Save(@""). Create, Add, Delete or Modify Paragraph and Table in Word Document. If you want to create
pdf to powerpoint converter online; convert pdf back to powerpoint
C# Word - Word Create or Build in C#.NET
Create Word Document from Existing Files Using C#. Create Word From PDF. Create Word From PowerPoint. Create Word From Open Office Files. Table Processing.
converting pdf to powerpoint slides; how to add pdf to powerpoint slide
10.3 DynamicProgramming
487
Thesolutionofthisrecurrenceisthewell-knownCatalannumbers,whichgrowexpo-
nentially.Thus,forlargeN,anexhaustivesearchthroughallpossibleorderingsisuseless.
Nevertheless,thiscountingargumentprovidesabasisforasolutionthatissubstantially
betterthanexponential.Letc
i
bethenumberofcolumnsinmatrixA
i
for1≤iN.Then
A
i
hasc
i−1
rows,sinceotherwisethemultiplicationsarenotvalid.Wewilldefinec
0
tobe
thenumberofrowsinthefirstmatrix,A
1
.
Suppose m
Left,Right
is the e number of multiplications required d to o multiply
A
Left
A
Left+1
···A
Right−1
A
Right
.Forconsistency,m
Left,Left
= 0.Supposethelastmultipli-
cation is s (A
Left
···A
i
)(A
i+1
···A
Right
),where Left ≤ ≤ Right. Then the number of
multiplicationsused ism
Left,i
+m
i+1,Right
+c
Left−1
c
i
c
Right
.Thesethreetermsrepresent
themultiplicationsrequiredtocompute(A
Left
···A
i
),(A
i+1
···A
Right
),andtheirproduct,
respectively.
If wedefine M
Left,Right
tobethenumberofmultiplicationsrequired in an optimal
ordering,then,ifLeft<Right,
M
Left,Right
=
min
Lefti<Right
{M
Left,i
+M
i+1,Right
+c
Left−1
c
i
c
Right
}
This equation implies s that t if we e have e an optimal l multiplication arrangement t of
A
Left
···A
Right
,thesubproblemsA
Left
···A
i
andA
i+1
···A
Right
cannotbeperformedsub-
optimally.This shouldbeclear,sinceotherwisewecouldimprovetheentireresultby
replacingthesuboptimalcomputationbyanoptimalcomputation.
Theformulatranslatesdirectlytoarecursiveprogram,but,aswehaveseeninthe
lastsection,suchaprogramwouldbeblatantlyinefficient.However,sincethereareonly
approximatelyN
2
/2valuesofM
Left,Right
thateverneedtobecomputed,itisclearthata
tablecanbeusedtostorethesevalues.FurtherexaminationshowsthatifRightLeft=k,
thentheonlyvaluesM
x,y
thatareneededinthecomputationofM
Left,Right
satisfyyx<k.
Thistellsustheorderinwhichweneedtocomputethetable.
Ifwewanttoprintouttheactualorderingofthemultiplicationsinadditiontothefinal
answerM
1,N
,thenwecanusetheideasfromtheshortest-pathalgorithmsinChapter9.
WheneverwemakeachangetoM
Left,Right
,werecordthevalueofithatisresponsible.This
givesthesimpleprogramshowninFigure10.46.
Althoughtheemphasis ofthischapterisnotcoding,itisworthnoting thatmany
programmerstendtoshorten variablenames toasingleletter.
c
,
i
,and
k
areused as
single-lettervariablesbecausethisagreeswiththenameswehaveusedinthedescription
ofthealgorithm,whichisverymathematical.However,itisgenerallybesttoavoid
l
asa
variablename,because
l
lookstoomuchlike
1
andcanmakeforverydifficultdebugging
ifyoumakeatranscriptionerror.
Returningtothealgorithmicissues,thisprogramcontainsatriplynestedloopandis
easilyseentoruninO(N
3
)time.Thereferencesdescribeafasteralgorithm,butsincethe
timetoperformtheactualmatrixmultiplicationisstilllikelytobemuchlargerthanthe
timetocomputetheoptimalordering,thisalgorithmisstillquitepractical.
10.3.3 OptimalBinarySearchTree
Ourseconddynamicprogrammingexampleconsidersthefollowinginput:Wearegiven
alistofwords,w
1
,w
2
,...,w
N
,andfixedprobabilities,p
1
,p
2
,...,p
N
,oftheiroccurrence.
C# Word - Footnote & Endnote Processing in C#.NET
Create or Add Table in Footnote & Endnote. The following demo code shows how to create table in the footnote. String docFilePath
convert pdf to powerpoint slides; convert pdf to powerpoint with
C# Word - Convert Word to PDF in C#.NET
Word: Convert Word to PDF. C# Word - Convert Word to PDF in C#.NET. Online C# Tutorial for Converting Word to PDF (.pdf) Document. Word to PDF Conversion Overview
convert pdf to powerpoint online; how to change pdf to powerpoint format
488
Chapter10 AlgorithmDesignTechniques
1
/**
2
* Compute optimal ordering of matrix multiplication.
3
* c contains the e number r of columns for each h of the e n matrices.
4
* c[ 0 ] is the number of rows in matrix x 1.
5
* The e minimum number r of multiplications is left in m[ 1 ][ n ].
6
* Actual ordering is computed d via a another procedure e using lastChange.
7
* m and lastChange are indexed starting at 1, instead of 0.
8
* Note: Entries below w main n diagonals of m and lastChange
9
* are e meaningless s and d uninitialized.
10
*/
11
void optMatrix( const vector<int> > & & c,
12
matrix<int> & m, matrix<int> > & & lastChange )
13
{
14
int n = = c.size( ( ) - 1;
15
16
for( int left t = = 1; ; left t <= n; ; ++left t )
17
m[ left ][ left ] ] = = 0;
18
for( int k k = = 1; k < n; ++k )
// k k is s right - left
19
for( int left = 1; left <= n n - - k; ; ++left t )
20
{
21
// For r each position
22
int right = left t + + k;
23
m[ left t ][ [ right ] ] = INFINITY;
24
for( int i i = = left; i < right; ; ++i i )
25
{
26
int thisCost t = = m[ [ left t ][ [ i i ] ] + m[ i + + 1 1 ][ right t ]
27
+ c[ left - - 1 ] * * c[ i i ] * c[ right ];
28
if( thisCost t < < m[ [ left t ][ [ right ] ] ) ) // / Update e min
29
{
30
m[ left t ][ right t ] ] = thisCost;
31
lastChange[ left t ][ [ right ] ] = = i;
32
}
33
}
34
}
35
}
Figure10.46 Programtofindoptimalorderingofmatrixmultiplications
Theproblemistoarrangethesewordsinabinarysearchtreeinawaythatminimizes
theexpectedtotalaccesstime.Inabinarysearchtree,thenumberofcomparisonsneeded
toaccessanelementatdepthdisd+1,soifw
i
isplacedatdepthd
i
,thenwewantto
minimize
N
i=1
p
i
(1+d
i
).
Asanexample,Figure10.47showssevenwordsalongwiththeirprobabilityofoccur-
rence in n some e context. Figure 10.48 shows s three e possible binary search trees.Their
searchingcostsareshowninFigure10.49.
10.3 DynamicProgramming
489
Word
Probability
a
0.22
am
0.18
and
0.20
egg
0.05
if
0.25
the
0.02
two
0.08
Figure10.47 Sampleinputforoptimalbinarysearchtreeproblem
if
a
and
egg
two
the
am
if
a
and
egg
two
the
am
if
a
and
egg
two
the
am
Figure10.48 Threepossiblebinarysearchtreesfordatainprevioustable
Thefirsttreewasformedusingagreedystrategy.Thewordwiththehighestprobability
ofbeingaccessedwasplacedattheroot.Theleftandrightsubtreeswerethenformed
recursively.Thesecondtreeistheperfectlybalancedsearchtree.Neitherofthesetrees
Input
Tree#1
Tree#2
Tree#3
Word
Probability
AccessCost
AccessCost
AccessCost
w
i
p
i
Once
Sequence
Once
Sequence
Once
Sequence
a
0.22
2
0.44
3
0.66
2
0.44
am
0.18
4
0.72
2
0.36
3
0.54
and
0.20
3
0.60
3
0.60
1
0.20
egg
0.05
4
0.20
1
0.05
3
0.15
if
0.25
1
0.25
3
0.75
2
0.50
the
0.02
3
0.06
2
0.04
4
0.08
two
0.08
2
0.16
3
0.24
3
0.24
Totals
1.00
2.43
2.70
2.15
Figure10.49 Comparisonofthethreebinarysearchtrees
490
Chapter10 AlgorithmDesignTechniques
isoptimal,asdemonstratedbytheexistenceofthethirdtree.Fromthiswecanseethat
neitheroftheobvioussolutionsworks.
Thisisinitiallysurprising,sincetheproblemappearstobeverysimilartothecon-
structionofaHuffmanencodingtree,which,aswehavealreadyseen,canbesolvedbya
greedyalgorithm.Constructionofanoptimalbinarysearchtreeisharder,becausethedata
arenotconstrainedtoappearonlyattheleaves,andalsobecausethetreemustsatisfythe
binarysearchtreeproperty.
Adynamicprogrammingsolutionfollowsfromtwoobservations.Onceagain,suppose
wearetryingtoplacethe(sorted)wordsw
Left
,w
Left+1
,...,w
Right−1
,w
Right
intoabinary
searchtree.Supposetheoptimalbinarysearchtreehasw
i
astheroot,whereLeft≤ i
Right.Thentheleftsubtreemustcontainw
Left
,...,w
i−1
,andtherightsubtreemustcontain
w
i+1
,...,w
Right
(bythebinarysearchtreeproperty).Further,bothofthesesubtreesmust
alsobeoptimal,sinceotherwisetheycouldbereplacedbyoptimalsubtrees,whichwould
giveabettersolutionforw
Left
,...,w
Right
.Thus,wecanwriteaformulaforthecostC
Left,Right
ofanoptimalbinarysearchtree.Figure10.50maybehelpful.
IfLeft>Right,thenthecostofthetreeis0;thisisthe
nullptr
case,whichwealways
haveforbinarysearchtrees.Otherwise,therootcostsp
i
.Theleftsubtreehasacostof
C
Left,i−1
relativetoitsroot,andtherightsubtreehasacostofC
i+1,Right
relativetoitsroot.
AsFigure10.50shows,eachnodeinthesesubtreesisoneleveldeeperfromw
i
thanfrom
theirrespectiveroots,sowemustadd
i−1
j=Left
p
j
and
Right
j=i+1
p
j
.Thisgivestheformula
C
Left,Right
=
min
LeftiRight
p
i
+C
Left,i−1
+C
i+1,Right
+
i−1
j=Left
p
j
+
Right
j=i+1
p
j
=
min
LeftiRight
C
Left,i−1
+C
i+1,Right
+
Right
j=Left
p
j
Fromthisequation,itisstraightforwardtowriteaprogramtocomputethecostofthe
optimalbinarysearchtree.Asusual,theactualsearchtreecanbemaintainedbysavingthe
valueofithatminimizesC
Left,Right
.Thestandardrecursiveroutinecanbeusedtoprintthe
actualtree.
w
i
w
Left
w
i−1
w
i+1
w
Right
Figure10.50 Structureofanoptimalbinarysearchtree
10.3 DynamicProgramming
491
Iteration=1
a..a
am..am
and..and
egg..egg
if..if
the..the
two..two
Left=1
Left=2
Left=3
Left=4
Left=5
Left=6
Left=7
.22
a
.18
am
.20
and
.05
egg
.25
if
.02
the
.08
two
Iteration=2
a..am
am..and
and..egg
egg..if
if..the
the..two
.58
a
.56
and
.30
and
.35
if
.29
if
.12
two
Iteration=3
a..and
am..egg
and..if
egg..the
if..two
1.02
am
.66
and
.80
if
.39
if
.47
if
Iteration=4
a..egg
am..if
and..the
egg..two
1.17
am
1.21
and
.84
if
.57
if
Iteration=5
a..if
am..the
and..two
1.83
and
1.27
and
1.02
if
Iteration=6
a..the
am..two
1.89
and
1.53
and
Iteration=7
a..two
2.15
and
Figure10.51 Computationoftheoptimalbinarysearchtreeforsampleinput
Figure10.51showsthetablethatwillbeproducedbythealgorithm.Foreachsub-
rangeofwords,thecostandrootoftheoptimalbinarysearchtreearemaintained.The
bottommostentrycomputestheoptimalbinarysearchtreefortheentiresetofwordsin
theinput.TheoptimaltreeisthethirdtreeshowninFigure10.48.
Theprecisecomputationfortheoptimalbinarysearchtreeforaparticularsubrange,
namely,am..if,isshowninFigure10.52.Itisobtainedbycomputingtheminimum-cost
treeobtainedbyplacingam,and,egg,andifattheroot.Forinstance,whenandisplacedat
theroot,theleftsubtreecontainsam..am(ofcost0.18,viapreviouscalculation),theright
subtreecontainsegg..if(ofcost0.35),andp
am
+p
and
+p
egg
+p
if
=0.68,foratotalcost
of1.21.
Therunning timeofthisalgorithmisO(N
3
),becausewhenitisimplemented,we
obtainatripleloop.AnO(N
2
)algorithmfortheproblemissketchedintheexercises.
10.3.4 All-PairsShortestPath
Ourthirdandfinaldynamicprogrammingapplicationisanalgorithmtocomputeshortest
weightedpathsbetweeneverypairofpointsinadirectedgraph,G=(V,E).InChapter9,
wesawanalgorithmforthesingle-sourceshortest-pathproblem,whichfindstheshortest
pathfromsomearbitraryvertex,s,toallothers.Thatalgorithm(Dijkstra’s)runsinO(|V|
2
)
timeondensegraphs,butsubstantiallyfasteronsparsegraphs.Wewillgiveashortalgo-
rithmtosolvetheall-pairsproblemfordensegraphs.Therunningtimeofthealgorithmis
O(|V|
3
),whichisnotanasymptoticimprovementover|V|iterationsofDijkstra’salgorithm
butcouldbefasteronaverydensegraph,becauseitsloopsaretighter.Thealgorithmalso
Documents you may be interested
Documents you may be interested