• Non ci sono risultati.

Pred(j) = {i N : (i,j) A}.

N/A
N/A
Protected

Academic year: 2022

Condividi "Pred(j) = {i N : (i,j) A}."

Copied!
30
0
0

Testo completo

(1)

Giovanni Righini

Dipartimento diInformati a

PoloDidatti o edi Ri er a diCrema

Università degli Studi diMilano

Via Bramante65,26013 Crema, Italy

1 Introdu tion

In these notesI presentsomeexamplesof dis reteoptimization problems solvedby dynami programming

(D.P. forshort). Thebasi stepsin thedesignofaD.P.algorithmarethesamein allexamples:

1. Deneasequen eofde isions,that orrespondsto determiningasolution.

2. Denethestate. Thestateistheamountofinformationthat oneneedsto knowwhensomede isions

inthesequen ehavealreadybeentakenandothersarestilltobetaken. Theinformationinthestate

mustbeenoughtodeterminethefeasibilityandthe ostof theremainingde isions.

3. Deneare ursiveextensionfun tion,i.e. howthe ostofstates anbe omputedfromthe ostofother

states.

The exe ution of a D.P. algorithm resembles the sear h for an optimal path on an a y li and weighted

digraph, from agiven sour enode orrespondigto anempty solution(node isiontaken)to agiven target

node orresponding toa ompletesolution (allde isionstaken). Thestru ture and thesize ofthe digraph

depend ontheproblem at hand and theydeterminethe omplexityof theD.P. algorithm. WhentheD.P.

algorithm terminates,thelabel( osttobeminimizedorvaluetobemaximized)ofthenalstategivesthe

optimalvalueoftheobje tivefun tion.

Besides omputingtheoptimalvalue,oneusuallywantstore onstru tafeasiblesolutionwiththatvalue,

i.e. anoptimalsolution. Thisisa hievedbys anningthesequen eofthede isionsba kward,fromthenal

statetotheinitialstate. Forea hstateitsoptimalprede essorissele tedandforthispurposeitisrequired

that theoptimalprede essorhasbeenstoredforea hstate.

For ea h example, I will provide the des ription of the problem, the des ription of one or more D.P.

algorithms, the orrespondinga y li weighteddigraphs,the omplexityofthe algorithm. Ea hproblem is

illustrated by anumeri alexample with itssolution. I also providethe pseudo- ode of theD.P. algorithm

allowingforane ientandstraightforwardimplementation.

Renementssu hasbi-dire tionalD.P.andtheuseofsuitabledata-stru tureswillbealsodis ussed.

(2)

The problem. Given an a y li digraph

D = (N , A)

with

|N | = n

and

|A| = m

and a ost fun tion

w : A 7→ ℜ

,nd theshortestpathfrom agivennode

s ∈ N

to agivennode

t ∈ N

. Adigraph isa y li if

andonlyifitdoesnot ontainany ir uit.

Step1: sequen ing thede isions. Sin e

D

isa y li ,itispossibletosortitsnodesintopologi alorder in

O(m)

. If

D

isalsolayered,itispossibletosortthelayersanditisnotne essarytosortthenodesinea h

layer(anyorder ts). Weindi ateby

P red(j) ⊂ N

theset ofprede essorsofea hnode

j ∈ N

:

P red(j) = {i ∈ N : (i, j) ∈ A}.

Step 2: deningthe state. Thestate onsists ofthelastrea hednode. All pathsfromnode

s

to node

i ∈ N

orrespondto sub-poli iesleadingto thesamestate. Hen e states havethefollowing (trivial)form:

{i}

,with

i ∈ N

. The ostasso iatedwithea h state

{i}

isindi atedby

c(i)

.

Step 3: state extension.

Initialization:

c(s) := 0

.

Extension:

c(j) := min i∈P red(j) {c(i) + w ij }

.

Theoptimalvalueis

c(t)

whenthealgorithmstops.

Complexity. Thea y li weightedstate-transition digraphof theD.P. algorithm isthedigraph

D

itself.

Thisis whythisexampleissuitbaleto bepresentedastheintrodu toryproblemtoillustrateD.P..

Thetime omplexityimmediately follows: when extendingstates, ea h ar ofthedigraph is onsidered

onlyon e;hen ethe omplexityis

O(m)

.

Sin eea h nodehasasinglelabel

c(i)

anditsvalueis omputedonlyon e,theresultingD.P. algorithm

isalabelsettingalgorithm.

Pseudo- ode. Thepseudo- odeoftheD.P. algorithmis shownin Algorithm2.1. Ave tor

π

re ordsthe

optimalprede essorstateforea hstate,i.e. theoptimalprede essornodeforea hnodeinthis example.

Thesub-routine

ComputeP redecessors

isneededwhenthedigraphisgivenininputasalistofweighted

ar s. Insu ha asethelist issequentiallys annedandforea har

(i, j) ∈ A

node

i

isinsertedin

P red(j)

.

The omputational omplexityofthisoperationisobviously

O(m)

.

The omputational omplexityofthelabelextensionis

O(m)

, asalreadyproven.

The omputational omplexityof the lastpart, where anoptimal solutionis produ ed, depends onthe

requiredoutputformat: ifabinaryve tor

x

isrequired,thenthe omplexityis

O(m)

,asshowninAlgorithm

2.1, be ause

m

binary variables mustbe assigned avalue; if aset

X

of sele tedar s is required, then the

omplexityis

O(n)

, be ausetheinitialization

X ← ∅

takes onstanttime andno morethan

n − 1

ar s an

belongtothe

s − t

path.

(3)

1:

T opologicalSort

;

⊲ O(m)

2:

ComputeP redecessors

;

⊲ O(m)

3: /*Negle tunrea hablenodes(nodesbefore

s

),ifany*/

4: for

j = 0, . . . , s − 1

do

⊲ O(n)

5:

c(j) ← ∞

;

6: /*Initialization*/

7:

c(s) ← 0

;

8: /*Extension*/

9: for

j = s + 1, . . . , t

do

10: for

i ∈ P red(j)

do

11: if

(c(i) + w ij < c(j))

then

12:

c(j) ← c(i) + w ij

;

13:

π(j) ← i

;

14: /*Optimalobje tivefun tion value*/

15:

z ← c(t)

;

16: /*Retrievalofanoptimalsolution*/

17: for

(i, j) ∈ A

do

⊲ O(m)

18:

x (i, j) ← 0

;

19:

j ← t

;

20: while

(j > s)

do

⊲ O(n)

21:

x (π(j), j) := 1

;

22:

j ← π(j)

;

return

z , x

Label orre ting variation. A variationoftheD.P. algorithmis obtainedbyextendingthelabelsfrom

ea hstatetoitssu essors. Let

Succ(i)

bethesetofallsu essorsofnode

i

,i.e.

Succ(i) = {j ∈ N : (i, j) ∈ A}.

ThelabelextensionpartofAlgorithm2.1 ouldberepla edbythefollowingAlgorithm2.2.

Algorithm2.2Labelextension

9: for

i = s, . . . , t − 1

do

10: for

j ∈ Succ(i)

do

11: if

(c(i) + w ij < c(j))

then

12:

c(j) ← c(i) + w ij

;

13:

π(j) ← i

;

Thetime omplexityisthesame,i.e.

O(m)

, be auseeveryar isexaminedon e. However,inthis ase

thelabelofea hstate anbeupdatedseveraltimes. Thereforethisvariationisalabel orre tingalgorithm.

(4)

requires to omputeashortestpathfrom node

s = 0

tonode

t = 9

.

0

1

2

3

4

5

6

7

8

9 6

8

13

9

15 8

10

12 8

7

15

20

8

7

3

4

Figure1: A weighteda y li (andlayered)digraph.

Figure2showstheiterationin whi h node5is labeled. Nodes0to 4havealreadybeenlabeled. Their

asso iated ostsareshownbytheblue labelsinFigure2. Optimalprede essorsarerepresentedbyredar s.

Node 5is nowlabeled by omparing three prede essorstates, yielding osts equalto 21 (from node1), 18

(fromnode2)and21(fromnode3)andsele tingthebest option(the se ondone).

0 0

1 6

2 8

3 13

4 15

5 18

6

7

8

9 6

8

13

9

15 8

10

12 8

7

15

20

8

7

3

4

Figure2: Astateextension.

(5)

stru ted byfollowingthe hainofprede essors

π

ba kwardfrom node9tonode1: theresultisrepresented bythethi kredar s.

0 0

1 6

2 8

3 13

4 15

5 18

6 20

7 30

8 26

9 30 6

8

13

9

15 8

10

12 8

7

15

20

8

7

3

4

Figure3: Theexamplesolved.

(6)

The problem. Givenadigraph

D = (N , A)

with

|N | = n

and

|A| = m

and a ostfun tion

w : A 7→ ℜ

,

ndtheshortestpathfromagivennode

s ∈ N

toagivennode

t ∈ N

. Thedigraphisnot onstrainedtobe a y li asinthepreviousexample;we onsidernowageneri digraph,possibly ontaining ir uits. However

ir uitsareguaranteednottohavenegative ost.

Step1: sequen ingthede isions. Theproblemisverysimilartothepreviousone,butnowthedigraph

is nota y li andthereforeitsnodes annotbesortedasin thepreviousexample. We anreformulate the

problem onana y li andlayereddigraph

D = (N , A )

, where

• N

ismadebyaset

L

of

n

layers;

ea hlayer

L k

ontainsa opyofea h nodein

N

;hen eea hnodein

N

isindi atedbyapair

(i, k)

;

forea har

(i, j) ∈ A

thereisanar from node

(i, k)

tonode

(j, k + 1)

forea hlayer

k = 1, . . . , n − 1

.

Weindi ateby

P red (j, k) ⊆ N

thesetofprede essorsofea hnode

(j, k) ∈ N

:

P red (j, k) = {(i, k − 1) ∈ N : (i, j) ∈ A } ∀k = 2, . . . , n.

Theprede essorsofea hnodeinlayer

k

belongto layer

k − 1

. Thenodesin layer

1

havenoprede essor.

The

n

layersofdigraph

D

representthe

n

stagesofthe D.P. algorithm. Atea h stage

k

the algorithm

omputesand omparespathsmade by

k − 1

ar s. Sin enofeasible solution an ontainmorethan

n − 1

ar s,

n

layersaresu ienttoimpli itlyenumerateallpossiblesolutions.

Afterthis reformulation,the shortestproblem on ageneri digraph with

n

nodes is translatedinto the

shortestpathproblemonana y li digraphwith

m(n − 1)

nodes. Therefore,thesameD.P.algorithmshown

in thepreviousexampleapplies.

Step2: deningthestate. Thestate onsistsofthelastrea hednodein

N

. All

s − i

pathsmadeby

k

ar s orrespondto sub-poli iesleadingto thesamestate. Hen e labelshavethefollowingform:

{i, k}

,with

i ∈ N

and

k = 1, . . . , n

. The ostasso iatedwithea hlabel

{i, k}

isindi atedby

c(i, k)

.

Step 3: labelextension.

Initialization:

c(s, 1) = 0 c(i, 1) = ∞ ∀i 6= s

.

Extension:

c(j, k) = min (i,k−1)∈P red (j,k) {c(i, k − 1) + w ij , c(j, k − 1)}

.

Theoptimalvalueis

c(t, n)

.

Remark1. Thealgorithm anpossiblyterminateevenbeforerea hingstage

n

: ifno hangeinlabelsis

observedata ertainstage,no hange ano urintheremainingstageseither.

Remark2. Thealgorithm omputestheshortestpathfrom

s

toall theothernodesin

N

.

Complexity. Whenextendinglabels,ea h ar in

A

is onsideredonlyon e. Thenumberofar sin

A

is

m(n − 1)

. Hen ethe omplexityis

O(mn)

.

Thealgorithm isknownasBellman-Fordalgorithm.

Thelabelofasamenode anbeupdatedseveraltimes(on eforea hstage). ForthisreasontheBellman-

Fordalgorithm isalabel orre tingalgorithm.

A numeri alexample. Figure4showsaweighteddigraph ontaining ir uits. Wewantto omputethe

shortestpathfromnode1tonode6.

(7)

1

2

3

4

5

6 20

10 63

72

0

70

5

40

34

100

-20

-5

36

-31

5

80

Figure4: Aweighteddigraph.

1,1

2,2

3,2

4,2

5,2

6,2

2,3

3,3

4,3

5,3

6,3

2,4

3,4

4,4

5,4

6,4

2,5

3,5

4,5

5,5

6,5 0

20

10

63

72

15

10

50

44

90

13

10

49

44

85

13

10

49

44

83 20

10

63

72

0

40

70

5

40

34

100 -20

-5

36 -31

5

80

0

40

70

5

40

34

100 -20

-5

36 -31

5

80

0

40

70

5

40

34

100 -20

-5

36 -31

5

80

Figure5: Thestate-transitiongraphandthestateextensions. Costsarerepresentedinblue;optimalprede-

essorsarerepresentedinred. Theoptimalsolutionisindi atedbythi kar sandboldednumbers.

(8)

The problem. Givenadigraph

D = (N , A)

with

|N | = n

and

|A| = m

and a ostfun tion

w : A 7→ ℜ

,

ndtheshortestHamiltonianpathfrom agivennode

s ∈ N

toagivennode

t ∈ N

.

A Hamiltonianpathisapaththatvisitsallnodesofthedigraphon e. Notethatw.l.o.g. we anassume

A

to be omplete;just onsidermissingar sasar swithaverylarge ost.

Step 1: sequen ing the de isions. Similarlyto theprevious example,sin e

D

is nota y li , itis not

possibletosort itsnodesandto settheirlabelspermanently. Weresortto anauxiliarya y li and layered

digraph

D

usingthesame onstru tionofthepreviousexample.

Step 2: deningthe state. Thestatedoesnot onsistonlyof thelastrea hednode. Inorderto he k

the feasibility ofthe solutionone must knowwhi h nodes havealready beenvisited. All pathsfrom node

(s, 1)

to node

(i, k) ∈ N

orrespond to sub-poli ies leadingto thesamestate ifand only iftheyalso visit

the same subsetof nodes. Hen e labelshavethe following form:

{i, k, S}

, with

i ∈ N

and

S ⊆ N

. Note

that

k = |S|

,be auseoneadditionalnodeisvisitedeverytimeapathisextended. Thereforetheinformation givenby thelayerindex

k

is redundant and anbeomitted. The ost asso iated with ea h label

{i, S}

is

indi atedby

c(i, S)

.

Step 3: labelextension.

Initialization:

c(s, {s}) = 0

.

Extension:

c(j, S) = min i∈S {c(i, S\{j}) + w ij }

.

Theoptimalvalueis

c(t, N )

.

Complexity. Thenumberofstatestobelabeledisexponentialin

n

. Thenumberofdistin tvaluesofthe

possiblesubsets

S

is

2 n

andea hsubsetwith

k

nodesappearsin

k

dierentstates(dependingonwhi histhe

lastvisitednode). Hen ethenumberofstatesis

O(n2 n )

. Whenextendinglabelsthenumberofprede essors forea hstateis

O(n)

. Hen ethe omplexityoftheD.P.algorithmis

O(n 2 2 n )

.

Dominan e. Dominan e onsistsofdeletingsomestatesfromfurther onsiderationbe ausethereisaguar-

anteethat theydonot orrespondto optimalsub-poli iesandthereforethe orrespondingpartialsolutions

annot bepartof optimal solutions. Inthese examplesthe dominan e riteriaare impli itly applied when

thelabelobtainedfromthebestprede essorissele tedandallotherextensions(i.e. thelabelsprodu edby

the other prede essors)are dis arded. This is aspe ial ase of dominan e: astatedominates anotherone

whenithasasmaller ostandallinformationisidenti alinbothstates(samelastvisitednode,samelayer,

samesubsetofvisitednodes,...).

(9)

1

2

3

4

5

6 20

10 63

72

0

40

70

5

40

34

100

-20

-5

36

-31

5

80

Figure6: Aweighteddigraph. Wewanttondtheminimum ostHamiltonianpathfromnode1tonode6.

Notethat thedigraph ontainsar swithnegative ost. Howeveritdoesnot ontain ir uitsofnegative

ost. Cir uitsofzero ostareallowedandindeed thereisone, ontainingnodes4and5. Alsonotethatnot

all ar s are present. This makesthe instan e easierto solveand the orrespondingstate-transition graph

easiertorepresent: somestateshaveauniqueprede essor(seeFigure7).

Theoptimalsolutionisthepath

(1, 3, 4, 5, 2, 6)

,whose ostis84. Dominan e anbeobservedontheright

partof Figure 7,where somestateshavemorethan oneprede essor: this meansthat they anberea hed

in dierentways. Forinstan e, state

{5, 1345}

anberea hedthroughthesequen es

(1, 4, 3, 5)

with ost77

and

(1, 3, 4, 5)

with ost45. Theformersub-poli yisdominatedbythelatterone. Owingtodominan e,the

statesgeneratedbytheD.P.algorithmarefewerthanallpossiblesequen es(sub-poli ies).

(10)

1,{1}

2,{1,2}

3,{1,3}

4,{1,4}

5,{1,5}

2,{1,2,3}

2,{1,2,5}

3,{1,2,3}

3,{1,3,4}

4,{1,2,4}

4,{1,3,4}

4,{1,4,5}

5,{1,3,5}

5,{1,4,5}

2,{1,2,3,4}

2,{1,2,3,5}

2,{1,2,4,5}

3,{1,2,3,4}

3,{1,2,3,5}

3,{1,3,4,5}

4,{1,2,3,4}

4,{1,2,4,5}

4,{1,3,4,5}

5,{1,2,3,5}

5,{1,2,4,5}

5,{1,3,4,5}

2,{1,2,3,4,5}

3,{1,2,3,4,5}

4,{1,2,3,4,5}

5,{1,2,3,4,5}

6,{1,2,3,4,5,6}

0

20

10

63

72

41

20

43

60

50

77

44

58

13

27

40

41

57

55

81

49

54

55

45

14

27

53

50

84 20

10

63

72

0

40

5

40

34

-20

-5

-31

5

40

0

40

40

34 5

34 -20

-5

-5

-20

-31

5

-31

40 0

34 40 5

-5 5 -20 -31

70

100

36

80

Figure7: Thestate-transitiongraphandthestateextensions. Costsarerepresentedinblue;optimalprede-

essorsarerepresentedinred. Theoptimalsolutionisindi atedbythi kar sandboldednumbers.

(11)

The problem. Giventwostrings

S 1

and

S 2

, i.e. twosequen esof hara terstakenfromagivenalphabet

A

,givenanadditional hara terX noto urringin

S 1

and

S 2

andgivena ostfun tion

w : A + × A + 7→ ℜ

,

where

A + = A ∪ {“X ′′ }

,ndtheminimum ostalignment.

Analignmentisgivenbyinsertinganynumberof hara tersX inanypositionsalongthetwosequen es,

sothat thenal sequen es havethesamelength. The ost ofan alignmentis thesum ofthevaluesof the

ost fun tion omputedfor allpositionsalong theresultingsequen es: ea h pairof hara ters o urringin

thesamepositionistheargumentofthefun tionforthat position.

Formally,let

S 1 +

and

S 2 +

bethetwosequen esaftertheinsertionoftheo urren esoftheX hara ter.

Let

L

be their length. Let indi ate by

S i + (k)

the hara ter in position

k

in sequen e

S i +

. The ostof the

alignmentis

P L

k=1 w(S 1 + (k), S 2 + (k))

.

Remark. Obviouslythe fun tion

w

is dened to penalize misalignments,i.e. thepresen e of dierent hara tersin the sameposition,and to rewardalignments, i.e. thepresen e of identi al hara ters in the

samepositions. The alignmentof a hara terin

A

witha hara terX is usuallypenalized,but lessthan

a misalignment. Aligning two hara ters X is never optimal: they anbe deleted from both sequen es,

yieldingabettersolution.

Step1: sequen ing the de isions. Inthisexamplewe onsidertwosequen esofde isions,oneforea h

string. Forea hpositiononehastode idewhethertoinserta hara terX ornotinthestring.

Step 2: dening the state. The state must represent whi h de isionshave already been taken: sin e

there aretwosequen es, thestate ontainstwoindi es, say

k 1

and

k 2

, indi atinghowmanypositionshave

alreadybeens annedandalignedinea hsequen e. Nofurtherinformationisrequiredto he kthefeasibility

oftheremainingde isions. Hen ethestateshavethefollowingform:

{k 1 , k 2 }

. The ostasso iatedwithea h

state

{k 1 , k 2 }

isindi atedby

c(k 1 , k 2 )

.

Step 3: labelextension.

Initialization:

c(0, 0) = 0

.

Extension:

c(k 1 , k 2 ) = min{c(k 1 − 1, k 2 ) + w S 1 (k 1 ),“X ′′ , c(k 1 , k 2 − 1) + w “X ′′ ,S 2 (k 2 ) , c(k 1 − 1, k 2 − 1) + w S 1 (k 1 ),S 2 (k 2 ) }

.

Theoptimalvalueis

c(n 1 , n 2 )

,where

n 1

and

n 2

arethelengthsofthegivensequen es.

Complexity. Thenumberofstatestobelabeledis

(n 1 + 1)(n 2 + 1)

. Whenextendinglabelsthenumberof

prede essorsforea hstateisatmostequaltothree. Hen ethe omplexityoftheD.P.algorithmisquadrati

in theinputsize.

(12)

Instan e

S1

: AA ABAB

S2

: BABA BB

Cost A B X

A 0 2 1

B 2 0 1

X 1 1 -

Solution 1:

S 1

=A AABA B

S 2

=BABABB

Cost=8

Solution 2:

S 1

=AAA BABXX

S 2

=BAXXBABB

Cost=4

Figure8: Asampleinstan eofthestringmat hing problemwithtwofeasiblesolutions.

(13)

0,0 0,1 0,2 0,3 0,4 0,5 0,6

1,0 1,1 1,2 1,3 1,4 1,5 1,6

2,0 2,1 2,2 2,3 2,4 2,5 2,6

3,0 3,1 3,2 3,3 3,4 3,5 3,6

4,0 4,1 4,2 4,3 4,4 4,5 4,6

5,0 5,1 5,2 5,3 5,4 5,5 5,6

6,0 6,1 6,2 6,3 6,4 6,5 6,6

2 3 4 5 6

1 2 1 2

3 4 5

2 3 2 3 2

3 4

3 4

3

4

3

4 5

4 3 4

3

4

3

4

5 4 3 4

3 4

5

6 5 4 3 4

3 4

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

2 0 2 0 2 2

2 0 2 0 2 2

2 0 2 0 2 2

0 2 0 2 0 0

2 0 2 0 2 2

0 2 0 2 0 0

Figure 9: Thestate-transition graph. Thegraphisdire ted,a y li andlayered: ea h node anberea hed

fromatmostthreeprede essorsintheprevioustwolayers.Costsasso iatedwiththestatesarerepresentedin

blue. Optimalprede essorsarerepresentedbyredar s. Optimalsolutionsareindi atedbyboldednumbers

andthi kar s. Forthissmallinstan e multipleoptimalsolutionsexist.

6

p

-medians on a line

The problem. Givenastraightlineandaset

N = {1, . . . , n}

ofpointsalongitinxedpositions

x(i) ∀i ∈ N

,ndtheoptimalpositionalongthelinefor

p

additionalpoints, alledmedians,su hthatthesumofthe

distan esbetweenea hpointin

N

andits losestmedian isminimized. W.l.o.g. weassumethat thepoints

in

N

areorderedin thesameorderastheyo uralongtheline.

Remark1. The

p

-medianproblemisNP-hard ongraphs,butthissimpliedversioninwhi hallpoints

lieonastraightlineispolynomiallysolvablebydynami programming.

Remark2. The

1

-medianproblemonalineiseasy(itiseasy,i.e. polynomiallysolvable,evenongeneral graphs). Ifthenumberofpointsisodd,theoptimallo ationofthemedian oin ideswiththe entralpoint;

ifthe numberof pointsiseven, theoptimallo ationof themedianis anywhere alongthesegmentbetween

the two entral points. We indi ate by

w(i, j)

theoptimal (minimum) ostof lo ating a singlemedian to

servethepointsin theinterval

[i, j]

,with

i ∈ N, j ∈ N, j ≥ i

.

Step 1: sequen ing the de isions. Allsolutionsindu e apartition of

N

intonon-overlappingintervals

(14)

alongthelineandwede idehowmanymediansareusedtoservethepointsen ountered.

Step2: deningthe state. Thestaterepresentswhi hde isionshavealreadybeentaken: atea hstage

inthede isionpro essweneedtoknowwhi histhelasts annedpoint

i ∈ N

andthenumber

m

ofmedians

useduptothatpoint. Hen ethestateshavethefollowingform:

{i, m}

. The ostasso iatedwithea hstate

{i, m}

isindi atedby

c(i, m)

: itindi ates theminimum osttoservethepointsin

[1..i]

with

m

medians.

Step 3: labelextension.

Initialization:

c(i, 1) = w(1, i) ∀i ∈ N

.

Extension:

c(i, m) = min j<i {c(j, m − 1) + w(j + 1, i)} ∀i ∈ N : i ≥ 2 ∀m : 2 ≤ m ≤ min{i, p}

.

Theoptimalvalueis

c(n, p)

.

Complexity. Thenumberof statesto belabeledis givenby

np

and sin e

p ≤ n

itis notlargerthan

n 2

.

Whenextendinglabels,thenumberofprede essorsforea hstateis

O(n)

. Hen e the omplexityoftheD.P.

algorithmis

O(n 2 p)

or

O(n 3 )

.

(15)

A numeri alexample. Figure10representsaninstan eofthe

p

-median problemonaline.

0

A

2

B

4

C

7

D

10

E

11

F

14

G

18

H

19 20

Figure 10: Aninstan e ofthe

p

-median problemonaline. Forbetterreadabilitytheindi es

1, . . . , n

ofthe

givenpointshavebeenrepla edbyletters. Inthisinstan e

p = 3

.

The osts

w(j, i)

for all pairs of points an be omputed in

O(n 2 )

exploiting the property outlined in

Remark 1bythefollowingsimplealgorithm.

Algorithm6.1

1: for

j = 1, . . . , n − 1

do

2:

opt := j

;

3:

i := j

;

4:

w(j, i) := 0

;

5:

paritybit := 1

;

6: while

i < n

do

7:

i := i + 1

;

8:

paritybit := 1 − paritybit

;

9:

w(j, i) := w(j, i − 1) + (x(i) − x(opt))

;

10: if (

paritybit = 0

)then

11:

opt := opt + 1

;

Theresulting ostmatrixisasfollows.

w A B C D E F G H

A 0 2 5 11 15 22 30 39

B 0 3 6 10 14 22 30

C 0 3 4 8 15 23

D 0 1 4 11 16

E 0 3 7 12

F 0 4 5

G 0 1

H 0

The orrespondingstates-transitionsgraph,withtheoptimalsolution,isrepresentedin Figure11.

(16)

A,1

B,1

C,1

D,1

E,1

F,1

B,2

C,2

D,2

E,2

F,2

G,2

H,3 2

5

11

15

22

0

2

5

6

9

16

14 0

3

6

10

14

22 0

3

4

8 15

0

1 4

11

0

3 7

0

4

0

30

23

16

12

5

1

Figure 11: Thestates-transitionsgraphandthestatesextensions. Costsofthestatesare indi atedin blue;

ostsofthetransitionsareindi atedinred. Theoptimalsolutionisindi atedbybolded ostsandthi kar s.

7 The binary knapsa k problem

The problem. Givenaset

N = {1, . . . , n}

ofitemswithavalue

v i ∀i ∈ N

andaweight

w i ∀i ∈ N

,sele t

the subsetof itemsof maximumvaluesu hthat the overall weightof thesele teditemsdoesnotex eeda

given apa ity

W

.

Step1: sequen ingthede isions. We an onsidertheitemsa ordingtotheirnumberingfrom1to

n

.

Forea hitemwehavetode idewhethertosele titornot. Hen ewehaveasequen eof

n

binaryde isions.

Step2: deningthestate. Atea hpointalongthede isionpro essweneedtoknowtheresidual apa ity

(17)

i v i w i

1 45 4

2 55 5

3 42 4

4 62 6

5 61 6

6 80 8

7 69 7

Table1: Asmallinstan e. Itemsaresorteda ordingto theire ien y

v i /w i

. The apa ityis

W = 16

.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 0 0 0 0 45 45 45 45 45 45 45 45 45 45 45 45 45

2 0 0 0 0 45 55 55 55 55 100 100 100 100 100 100 100 100

3 0 0 0 0 45 55 55 55 87 100 100 100 100 142 142 142 142

4 0 0 0 0 45 55 62 62 87 100 107 117 117 142 149 162 162

5 0 0 0 0 45 55 62 62 87 100 107 117 123 142 149 162 168

6 0 0 0 0 45 55 62 62 87 100 107 117 125 142 149 162 168

7 0 0 0 0 45 55 62 69 87 100 107 117 125 142 149 162 169

Table2: Theoptimalsolution(in bold):

z = 169

,

x = [1, 1, 0, 0, 0, 0, 1]

.

the stateshavethefollowingform:

{i, q}

, where

i

indi ates the last item onsidered in thesequen e and

q

indi ates the apa ityused. The valueasso iated withea h state

{i, q}

isindi ated by

z(i, q)

: itindi ates

themaximumvaluethat anbea hieved withtherst

i

items,using anamountof apa ityequalto

q

. A

dummy initialstate indi atesthat at thebeginningno itemhasbeen onsidered and no apa ityhasbeen

used.

Step 3: labelextension.

Initialization:

z(0, q) = 0 ∀q = 0, . . . , W

.

Extension:

z(i, q) =

 z(i − 1, q) ∀i ∈ N ∀q < w i

max{z(i − 1, q), z(i − 1, q − w i ) + v i } ∀i ∈ N ∀q = w i , . . . , W.

Theoptimalvalueis

max q=0,...,W {z(n, q)}

.

Complexity. Index

i

rangesintheinterval

[0 . . . , n]

;thenumberofpossiblevaluesfor

i

is

n + 1

. Index

q

rangesin the interval

[0 . . . , W ]

; thenumberof possiblevaluesfor

q

is

W + 1

. Hen ethe numberofstates

growsas

O(nW )

. Whenextendinglabels,thenumberofprede essorsforea hstateis

2

. Hen etheworst- ase

time omplexity ofthe D.P. algorithm is

O(nW )

. This omplexityis notpolynomial, be ause

W

doesnot

determinethesizeoftheinstan e,like

n

;ratheritisthevalueofadatumoftheinstan e. Inthis ase,wesay

thatthe omputational omplexityispseudo-polynomial. Dynami Programmingisaverypowerfulte hnique

to designpseudo-polynomial omplexityalgorithms for

N P

-hardproblems. Ifan

N P

-hardproblem admits

su hanalgorithm,itis lassiedas weakly

N P

-hard.

Anumeri alexample. Table1showsasmallinstan eofthebinaryknapsa kproblem. The orresponding

optimalsolutionisreportedinTable7.

Implementation. Abasi versionoftheD.P.algorithmdes ribedabovedire tly omesfromthedenition

oftheextensionfun tion. It onsistsofllingthematrixshowninFigure7rowafterrow.

Howeverinthisalgorithmmanyiterationsarewasted,be ausenoallentriesofthematrix

z

areneeded. A

(18)

2: /*Inizialize*/

3: for

q = 0, . . . , W

do

4:

z[0, q] := 0

;

5: /*Computeallstates*/

6: for

i = 1, . . . , n

do

7: for

q = 0, . . . , w i − 1

do

8:

z[i, q] := z[i − 1, q]

;

9:

f lag[i, q] := 0

;

10: for

q = w i , . . . , W

do

11: if (

z[i − 1, q − w i ] + v i > z[i − 1, q]

)then

12:

z[i, q] := z[i − 1, q − w i ] + v i

;

13:

f lag[i, q] := 1

;

14: else

15:

z[i, q] := z[i − 1, q]

;

16:

f lag[i, q] := 0

;

17: /*Find theoptimalvalue*/

18:

z := 0

;

19: for

q = 0, . . . , W

do

20: if

(z[n, q] > z )

then

21:

z := z[n, q]

;

22:

q := q

;

23: /*Re onstru ttheoptimalsolution*/

24: for

i = n, . . . , 1

do

25:

x [i] := f lag[i, q ]

;

26: if

(f lag[i, q ] = 1)

then

27:

q := q − w i

;

return

z

,

x

(19)

asalinkedlist. Thealgorithm startsfrom asinglestate ofnullvalueon row

0

and onlyexisting statesin

row

i

generate su essorstates in row

i + 1

. Everytime astate

(i, q)

is generated, itis ne essaryto he k

whetheranotherstatealreadyexistswiththesamevalueof

q

. Ifitexists,thena omparisonisneededwhi h

of thetwostatesdominate. Thesear hforthis staterequires ingeneralmorestepsthanadire t a essto

amatrix entry. Howeverthis an be ompensated bythesparsityof thedata-stru ture: ea hlinked list is

likelyto ontainlessstatesthanasinglerowofthematrix

z

,espe iallyintheearliestiterations.

The notation used in 7.1 is the following. Ea h row is a doubly linked list made of re ords with the

followingelds:

• capac

: thevalueoftheused apa ity(

q

);

• value

: thea umulatedvalue(

z

);

• lef t

and

right

: pointerstotheadja entre ords;

• pred

: pointerto theoptimalprede essorstate;

• item

: lastelementinsertedintotheknapsa k.

An array

tail

ontainsthepointerstotherightmost elementsofea hrow.

Algorithm7.1Knapsa k(dynami data-stru ture)

1:

Initialize

;

2: /*Computeallstates*/

3: for

i = 1, . . . , n

do

4:

CopyList(i)

;

5: /*Initializepointersto s anthelist*/

6:

p := tail[i]

;

7:

s := tail[i]

;

8: repeat

9: if

(pˆ.capac + w i ≤ W )

then

10: while

(sˆ.capac > pˆ.capac + w i )

do

11:

s := sˆ.lef t

;

12: if

(pˆ.capac + w i > sˆ.capac)

then

13:

CreateN ewState(p, s, i)

;

14: else

15: /*Dominan etest*/

16: if

(sˆ.value < pˆ.value + v i )

then

17:

sˆ.value := pˆ.value + v i

;

18:

sˆ.item := i

;

19:

sˆ.pred := p

;

20:

p := pˆ.lef t

;

21: until

(p = nil)

;

22:

RetrieveOptimalSolution

;

Algorithm7.2

Initialize

1:

N ew(tail[0])

;

2:

tail[0]ˆ.value := 0

;

3:

tail[0]ˆ.capac := 0

;

4:

tail[0]ˆ.lef t := nil

;

5:

tail[0]ˆ.right := nil

;

6:

tail[0]ˆ.pred := nil

;

(20)

Algorithm7.3

CopyList(i)

1:

p := tail[i − 1]

;

2:

tail[i] := nil

;

3: while

(p <> nil)

do

4: if

(tail[i] = nil)

then

5:

N ew(tail[i])

;

6:

s := tail[i]

;

7:

sˆ.capac := pˆ.capac

;

8:

sˆ.value := pˆ.value

;

9:

sˆ.item := pˆ.item

;

10:

sˆ.right := nil

;

11:

sˆ.lef t := nil

;

12:

sˆ.pred := tail[i − 1]

;

13: else

14:

N ew(sˆ.lef t)

;

15:

sˆ.lef tˆ.capac := pˆ.capac

;

16:

sˆ.lef tˆ.value := pˆ.value

;

17:

sˆ.lef tˆ.item := pˆ.item

;

18:

sˆ.lef tˆ.right := s

;

19:

sˆ.lef tˆ.lef t := nil

;

20:

sˆ.lef tˆ.pred := p

;

21:

s := sˆ.lef t

;

22:

p := pˆ.lef t

;

Algorithm7.4

CreateN ew(p, s, i)

1:

N ew(t)

;

2:

tˆ.lef t := s

;

3:

tˆ.right := sˆ.right

;

4:

sˆ.right := t

;

5: if

(tail[i] = s)

then

6:

tail[i] := t

7: else

8:

tˆ.rightˆ.lef t := t

;

9:

tˆ.capac := pˆ.capac + w i

;

10:

tˆ.value := pˆ.value + v i

;

11:

tˆ.item := i

;

12:

tˆ.pred := p

;

Algorithm7.5

RetrieveOptimalSolution

1:

z := 0

;

2: for

i = 1, . . . , n

do

3:

x[i] := 0

;

4:

p := tail[n]

;

5: while

(p <> nil)

do

6: if

(pˆ.value > z )

then

7:

z := pˆ.value

;

8:

p := p

;

9:

p := pˆ.lef t

;

10: while

(p ˆ.pred <> nil)

do

11:

x[p ˆ.item] := 1

;

12:

p := p ˆ.pred

;

z x

(21)

1 0 45

2 0 45 55 100

3 0 45 55 87 100 142

4 0 45 55 62 87 100 107 117 142 149 162

5 0 45 55 62 87 100 107 117 123 142 149 162 168

6 0 45 55 62 87 100 107 117 125 142 149 162 168

7 0 45 55 62 69 87 100 107 117 125 142 149 162 169

Table 3: The sparse matrix in the implementation using dynami data-stru tures: about one half of the

statesarenotevaluated.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 0 45

2 0 45 55 100

3 0 45 55 87 100 142

4 0 62 69 80 123 131 142 149

5 0 61 69 80 130 141 149

6 0 69 80 149

7 0 69

Table4: Thetwosparsesub-matri esin thebi-dire tionalimplementation: about

75%

ofthestatesarenot

generated.

Inthisimplementationalargepartofthe matrix(i.e. alargepartof thestatespa e)isnotgenerated,

asshowninTable??.

However, onsideringhowmanyelementaryoperationsareneededinthese ondimplementation ompared

totherstone,thissavingmaybeinsu ienttojustifytheuseofdynami data-stru turestosolvethistoy

instan e. Theadvantageofthese ondimplementationislikelytobemeaningfulonlyforverylargeinstan es

(where omputingtimeisalsomoresigni ant).

An observation dire tly stemming from the analysis of Table ?? is that the number of states grows

with index

i

: top rowsin the matrixare sparserthan bottom rows. This suggestsafurther improvement:

bi-dire tionalD.P.. Inbi-dire tional D.P. non-dominated statesaregenerated in bothdire tions along the

sequen eofde isions;thereforewehavetomanageforwardandba kwardstatesseparatelyandindependently.

Theextensionofstatesstopswhenasuitablehalf-waypoint isrea hed. Thedenitionofthisstop riterion

mustsatisfyafundamentalproperty: itmustbepossibletoobtainanyfeasiblesolutionbysuitably ombining

aforwardstateandaba kwardstate,i.e. twonon-dominatedsub-poli ies. Inourexample,apossible riterion

istheuseoftheitems: forinstan e,wedeneforwardstatesasnon-dominated ombinationsofitems

1 . . . , 3

and ba kward states as non-dominated ombinations of items

4 . . . , 7

. Using the same extension rules of

forwardstatesfor generatingba kwardstates,withtheonly dieren ethat itemsare onsidered in reverse

order,weobtaintheresultshowninTable7.

Bi-dire tionalD.P. allowsto de reasesigni antlythenumberof statesto be onsidered. Onthe other

side, itrequires apost-pro essingoperationtojoin pairsofforwardand ba kwardstatesinorder toobtain

solutions. Pairsofstatesmustsatisfythe apa ity onstraint: ea hforwardstatewith apa ity onsumption

q

anbejoined with anyba kwardstatewith apa ity onsumptionnot largerthan

W − q

. Thejoin step

anbedonein

O(n)

, asillustratedinTable??.

Inthejoinstepea hforwardstateismat hedwiththemost onvenientba kwardstate,thatiswiththe

ba kwardstatewith maximum onsumption among thosesatisfying the apa ity onstraint. Forinstan e,

forwardstate with

q = 5

and

z = 55

an be feasibly mat hed with allba kwardstates with onsumption between

0

and

11

: themost onvenientoneistheba kwardstatewith

q = 8

and

z = 80

. This anbedone

in

O(n)

asshowninAlgorithm7.6: thepseudo- odeassumesanimplementationwithtwolinkedlists,whose

tail f w tail bw head f w head bw

(22)

FW 0 (0) (0) (0) 45 55 (55) (55) 87 100 (100) (100) (100) 142 (142) (142) (142)

BW 149 142 131 123 (80) (80) (80) 80 69 62 (0) (0) (0) (0) (0) 0

16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

149 149 142 131 168 135 135 135 167 169 162 100 100 142 142 142 162

Table5: Thejoinsteprequiresto s antheforwardand ba kwardlistofnon-dominatedstates.

theleftside. Itreturnstheoptimalvalue

z

andtwopointers

p

and

q

totheoptimalforwardandba kward

statepair. Sin ethetwolistsares annedonlyon e,theworst- asetime omplexityofthejoinpro edureis

O(n)

.

Algorithm7.6

Join

1:

z := 0

;

2:

p := tail f w

;

3:

q := head bw

;

4: while

(p 6= nil)

and

(q 6= nil)

do

5: repeat

6: if

(pˆ.value + qˆ.value > z )

then

7:

z := pˆ.value + qˆ.value

;

8:

p := p

;

9:

q := q

;

10:

q := qˆ.right

;

11: until

(q = nil)

or

(pˆ.capac + qˆ.capac > W )

12: repeat

13:

p := pˆ.lef t

;

14: until

(p = nil)

or

(pˆ.capac + qˆ.capac ≤ W )

return

z

,

p

,

q

(23)

The problem. Weare givenadis rete-time dynami system, i.e. a system hara terizedby aninput, a

stateandanoutput. Inthisexampletheyareallverysimple,just onsistingofas alarvalue. Inadis rete

set of

T

pointsin time

t = 1, . . . , T

thestate

x(t)

evolvesa ordingtotheequation

x(t) = x(t − 1) + u(t)

where

u(t)

istheinputat time

t

. Thedomains

U

and

X

of

u

and

x

are dis reteintervals. A ost

f t (x(t − 1), u(t))

is asso iatedwith ea h transition o urring from astate

x(t − 1)

withaninput value

u(t)

at time

t

. Whenthe ostis negativeitrepresentsabenet. The wholeset ofinputvaluesisto bede ided andthe

initialstate

x(0)

aswell. Wewantto leadthesystemto agivennalstate

x

byasequen eoftransitionsof minimum ost(ormaximumbenet).

Step 1: sequen ing the de isions. In this problem there is an obvious orresponden e between the

de isionpro essand thedynami system. Inthis orresponden e thesequen eof de isionsisthe sequen e

ofinputvaluestobe hosen. Sothereisade isionforea hpointin time

t ∈ 1, . . . , T

.

Step 2: dening the state. Owing to theabovementioned orresponden e,the statein dynami pro-

gramming orresponds with the state of the dynami system. Hen e the states have the following form:

{x, t}

,where

x

indi atesthestateofthesystemand

t

indi atesthepointin time. The ostasso iatedwith

ea hstate

{x, t}

is indi atedby

c(x, t)

: itindi ates theminimum ost thatmust bepaid forrea hingstate

x

attime

t

.

Step 3: labelextension.

Initialization:

c(x, 0) = 0 ∀x ∈ X

.

Extension:

c(x, t) = max u∈U {c(x − u, t − 1) + f t (x − u, u)} ∀x ∈ X ∀t ∈ 1, . . . , T

.

Theminimum ostis

c(x, T )

(ifitnegative,itrepresentsamaximumbenet).

Complexity. The numberof possiblevaluesfor

x

is

|X|

, while the numberof possible valuesfor

t

is

T

.

Hen e thenumberofstatesgrowsas

O(|X|T )

. Whenextendinglabels,thenumberofprede essorsforea h stateis

|U |

. Hen etheworst- asetime omplexityoftheD.P.algorithmis

O(|X||U |T )

. The omputational omplexityispseudo-polynomial.

(24)

A numeri alexample. Tables6representsaninstan eoftheproblemwith

X = {1, 2, 3}

,

U = {−1, 0, 1}

and

T = 3

. Thesystemisrequiredtorea hstate

x = 2

at

t = 3

. Thestates-transitionsgraphisrepresented

f 1 f 2 f 3

-1 0 1 -1 0 1 -1 0 1

1 2 -7 -3 1 -5 -9 0 -6 -4

2 0 5 -4 -2 -14 2 1 -1 0

3 3 -10 -3 15 20 -8 4 -9 -2

Table6: Thetransition osts. Rowsindi ate the

x

value, olumnsindi atethe

u

value.

in Figure12togetherwiththelabelsandtheoptimalsolution.

1,0

2,0

3,0

1,1

2,1

3,1

1,2

2,2

3,2

2,3 0

0

0

-7

-3

-10

-12

-17

-1

-18 -7

-3 0

5

-4 3

-10

-5

-9 -2

-14

2 15

20

-4

-1

4

Figure 12: The state-transition graph and the state extensions. Costs are represented in blue; optimal

prede essorsarerepresentedinred. Theoptimalsolutionisindi atedbythi kar sandboldednumbers.

(25)

The problem. We are given a set

P = {1, . . . , n}

of proje ts and a budget

R

. We have to assign an

investment to ea h proje t. Depending on the investment, ea h proje t is expe ted to yield a prot. No

assumptionismadeaboutthekindofrelationshipbetweentheinvestmentandtheprot,but forsimpli ity

hereweassumethattheinvestmentsareintegerandnon-negative. Forea hproje t

i ∈ P

the orresponding investmentisrepresentedby

x i

and the orrespondingexpe tedprotby

f i (x i )

. Thedomain of

x i

, i.e. the

set of possibleinvestments in proje t

i ∈ P

is indi ated by

X i

. Theobje tive is to maximize the overall

expe tedprotwithoutex eedingthebudget.

Step 1: sequen ing the de isions. Inthis problem we onsider theproje tsin asequen e, arbitrarily.

At ea h point in time during the de ision pro ess therst part of the sequen ehas already beens anned

while thelastpartofthesequen eis not,i.e. therstproje tshavebeenassigned aninvestmentwhilethe

investmentsin the remainingproje tsarestill to bede ided. Soade isionmust be takenforea h proje t

i ∈ P

.

Step2: deningthestate. Thestatemustrepresentallrelevantinformationatanygeneri stepduring

thede isionpro ess. Obviouslyweneedto knowwherewearein thede isionpro ess, i.e. whi histhelast

de ided investment. Furthermore, owingto the onstraint onthe limitedbudget

R

, weneed to know how

mu h resour e is left. Hen e the states have thefollowing form:

{i, r}

, where

i

indi ates the last proje t

onsidered and

r

indi ates the residual available budget. The prot asso iated with ea h state

{i, r}

is

indi ated by

p(i, r)

: it indi ates themaximum prot that anbe a hieved when rea hing state

{i, r}

. An

additionalinitialstate

{0, R}

orrespondstothebeginningofthede isionpro ess,whennoinvestmenthas beende idedyetandthewhole budgetisstillavailable.

Step 3: labelextension.

Initialization:

p(0, R) = 0

.

Extension:

p(i, r) = max x i ∈X i {p(i − 1, r + x i ) + f i (x i )} ∀i ∈ P ∀r ∈ 0, . . . , R

.

The maximum overall expe ted prot is

max R r=0 {p(n, r)}

. If the expe ted prots are largerthan the in-

vestments (i.e.

f i (x i ) ≥ x i ∀i ∈ P ∀x i ∈ X i

) and it is possible to invest all the resour e (i.e.

R ≤ P

i∈P max x i ∈X i {x i }

), then themaximum expe ted protis ertainly attained at state

(n, 0)

, be auseit is

ertainlyoptimaltoinvestthewholebudget.

Complexity. Thenumberofpossiblevaluesfor

i

is

n

, whilethenumberofpossiblevaluesfor

r

is

R + 1

(from

0

to

R

). Hen e thenumberofstatesgrowsas

O(nR)

. Whenextendinglabelstoea hstateofproje t

i ∈ P

,thenumberofprede essorsforea hstateisatmost

|X i |

,whi h annotbelargerthan

R+ 1

. Hen ethe

worst- asetime omplexityoftheD.P.algorithmis

O(nR 2 )

. The omputational omplexityofthisalgorithm ispseudo-polynomial.

(26)

P = {1, . . . , 4}

and

R = 10

.

x 1 f 1 x 2 f 2 x 3 f 3 x 4 f 4

0 0 0 -2 0 0 0 -5

1 7 1 4 1 5 1 -2

2 13 2 7 2 6 2 3

3 17 3 8 3 7 3 7

4 20 4 8

Table7: Thepossibleinvestmentsandthe orrespondingexpe tedprotsforea hproje t.

Thestates-transitionsgraphisrepresentedinFigure13togetherwiththelabelsandtheoptimalsolution.

0,10 1,10

1,9

1,8

1,7

1,6

2,7

2,6

2,5

2,4

2,3

3,3

3,2

3,1

3,0 4,0

0 0

7

13

17

20

17

21

24

27

28

32

33

34

35 39

0

7

13

17

20

8

7

8

4

7

8

-2

4

7

8

-2

4

7

8

8

7

8

6

7

8

5

6

7

8

0

5

6

7

7

3

-2

-5

Figure 13: The state-transition graph and the state extensions. Costs are represented in blue; optimal

prede essorsarerepresentedinred. Theoptimalsolutionisindi atedbythi kar sandboldednumbers.

(27)

The problem. Averysmall arrental ompanythereisonlyone ar. The ompanyhas olle tedaset

N

of ordersfrom potential ustomers andnowitmustde idewhi h ordersto satisfyinorder to maximizeits

prots. Ea horder

i ∈ N

is hara terizedbyastarttime

s i

,anend time

e i

andaprot

p i

. Obviously,no

twosele tedorders anoverlapin time.

Remark.Ingraphterminologythisproblemis alledMaxindependentsetproblemonanintervalgraph.

We andeneagraphwhereea hvertex orrespondstoanorderandanytwoverti es

i

and

j

are onne ted

by an edge if and only if thetwo orresponding orders overlap. For its parti ular stru ture, the resulting

graphis alledinterval graph. Overlappingordersarein ompatible,i.e. they annotbebothsele ted. This

onstraint translates into the sear h for an independent set, i.e. a subset of verti es su h that they are

not onne tedto oneanotherby any edge. Thesubsetof orders yielding themaximumprot orresponds

to a maximum weight independentset, after assigning ea h vertex

i

a weight equalto the prot

p i

of the

orrespondingorder. Themaxindependentsetproblemis

N P

-hardongeneralgraphs,butitispolynomially solvableonintervalgraphs.

Step 1: sequen ing the de isions. The orders an be sequen ed a ording to their start time

s

. A

binaryde isionmustbetakenforea hofthem(whether tosele tthatorderornot).

Step 2: deningthe state. Atea hpointalongthede isionpro essweneedtoknowwhereweare,i.e.

whi histhelastorder onsideredandwhat onstraintsarepropagatedtothefuturede isionsbe auseofthe

de isionsalreadytaken. Thisiseasilyrepresentedbythetimewhenthe arbe omesavailable. A tuallythe

timethe arbe omesavailableisnotdire tlyrelevantinitself;whatisrelevantisthenextorderthat anbe

sele ted. Ifweknowwhi histhenextorderthat anbesele tedwedonotevenneedtoknowwhi h isthe

lastorder onsidered.Hen ethestateshavethefollowing(verysimple)form:

{i}

,where

i

indi atesthenext

orderthat anbesele tedwhenthe arbe omesavailableagain. Theprotasso iatedwithea hstate

{i}

is

indi atedby

f (i)

: itindi atesthemaximumprotthat anbea hievedwhenrea hingstate

{i}

. Adummy

state

{n + 1}

representsthenalstate,whenallordershavebeende ided. Weset

s n+1

toanarbitraryvalue

largerthan

max i∈N {e i }

.

Step 3: labelextension.

Initialization:

f (1) := 0

.

Extension:

f (i) := max{0, max j∈N:e j ≤s i {f (j) + p j }} ∀i = 1, . . . , n + 1

.

Themaximumprotis

f (n + 1)

.

Complexity. Thenumber ofpossiblevaluesfor

i

is

n + 1

. Whenextendinglabelsto ea h state

{i}

, the

number of prede essors is at most

n

. Hen e the worst- ase time omplexity of the D.P. algorithm is not

worse than

O(n 2 )

. However, it is redundant to explore all prede essors for ea h state. A more e ient implementationisobtainedifweassignea hstate

j

auniquesu essor

succ(j)

su hthat

succ(j) = argmin

iinN:s i ≥e j

{s i }.

Theorder

succ(j)

isthe rstorderthat anbesele tedafter order

j

. Ifwe andetermine

succ(j)

forea h

j ∈ N

,thenwe an onstru tagraphinwhi hea hstate

j

hasonlytwooutgoingar s: anar withvalue

0

tothenextstate

j + 1

andanar ofvalue

p j

to

succ(j)

. Thesetwoar srepresentthetwoalternatives: sele t

j

ordo notsele t

j

. Theresultinggraphisdire ted,a y li andlayeredandhasonly

O(n)

ar s: therefore

thelabelpropagation algorithmtakes

O(n)

. The bottlene k determiningtheworst- asetime omplexity is the onstru tion ofthegraph. It an bedonein lineartimeif theordersare sorted,ashownin Algorithm

10.1. Iftheyarenot, ittakes

O(n log n)

tosort themand thereforethisis theresultingtime omplexity of

thealgorithm.

G 2n

Riferimenti

Documenti correlati

Attraverso la promozione e il trasferimento di approcci culturali, modelli e strumenti di gestione delle risorse umane che puntano a valorizzare le diversità trasformandole

Let S(n, k) be the Stirling number of the second kind, i.e., the number of ways to partition a set of n objects into k

[r]

[r]

This paper deals with prediction for time series models and, in particular, it presents a simple procedure which gives well-calibrated predictive distributions, generalizing

In particular, this work focuses on the issue of maximizing the amount of time over which a set of points of interest (target points), located in a given area, can be monitored by

Thanks to the strong convergence in L 2 0; T ; L 2 (D) one can pass to the limit and prove that u is a solution (this step depends on the sequence of approximating problems and thus

Recentemente, ad Alta è stato sviluppato un modello di ordine ridotto per la progettazione preliminare e la stima delle prestazioni non cavitanti per induttori a mozzo