Introduction to Algorithms, Third Edition


Reconstructing an optimal solution



Download 4,84 Mb.
Pdf ko'rish
bet253/618
Sana07.04.2022
Hajmi4,84 Mb.
#534272
1   ...   249   250   251   252   253   254   255   256   ...   618
Bog'liq
Introduction-to-algorithms-3rd-edition

Reconstructing an optimal solution
As a practical matter, we often store which choice we made in each subproblem in
a table so that we do not have to reconstruct this information from the costs that we
stored.
For matrix-chain multiplication, the table
sŒi; j 
saves us a significant amount of
work when reconstructing an optimal solution. Suppose that we did not maintain
the
sŒi; j 
table, having filled in only the table
mŒi; j 
containing optimal subprob-
lem costs. We choose from among
j
i
possibilities when we determine which
subproblems to use in an optimal solution to parenthesizing
A
i
A
i
C
1
A
j
, and
j
i
is not a constant. Therefore, it would take
‚.j
i /
D
!.1/
time to recon-
struct which subproblems we chose for a solution to a given problem. By storing
in
sŒi; j 
the index of the matrix at which we split the product
A
i
A
i
C
1
A
j
, we
can reconstruct each choice in
O.1/
time.
Memoization
As we saw for the rod-cutting problem, there is an alternative approach to dy-
namic programming that often offers the efficiency of the bottom-up dynamic-
programming approach while maintaining a top-down strategy. The idea is to
memoize
the natural, but inefficient, recursive algorithm. As in the bottom-up ap-
proach, we maintain a table with subproblem solutions, but the control structure
for filling in the table is more like the recursive algorithm.
A memoized recursive algorithm maintains an entry in a table for the solution to
each subproblem. Each table entry initially contains a special value to indicate that
the entry has yet to be filled in. When the subproblem is first encountered as the
recursive algorithm unfolds, its solution is computed and then stored in the table.
Each subsequent time that we encounter this subproblem, we simply look up the
value stored in the table and return it.
5
Here is a memoized version of R
ECURSIVE
-M
ATRIX
-C
HAIN
. Note where it
resembles the memoized top-down method for the rod-cutting problem.
5
This approach presupposes that we know the set of all possible subproblem parameters and that we
have established the relationship between table positions and subproblems. Another, more general,
approach is to memoize by using hashing with the subproblem parameters as keys.


388
Chapter 15
Dynamic Programming
M
EMOIZED
-M
ATRIX
-C
HAIN
.p/
1
n
D
p:
length
1
2
let
mŒ1 : : n; 1 : : n
be a new table
3

Download 4,84 Mb.

Do'stlaringiz bilan baham:
1   ...   249   250   251   252   253   254   255   256   ...   618




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish