Speed-Up in Dynamic Programming
5星 · 超过95%的资源 需积分: 10 97 浏览量
2011-04-26
20:01:02
上传
评论
收藏 893KB PDF 举报 
SIAM
J.
ALG.
DISC.
METH.
Vol.
3,
No.
4,
December
1982
1982
Society
for
Industrial
and
Applied
Mathematics
0196-5212/82/0304-0015
$01.00/0
SPEED-UP
IN
DYNAMIC
PROGRAMMING*
F.
FRANCES
YAO"
Abstract.
Dynamic
programming
is
a
general
problem-solving
method
that
has
been
used
widely
in
many
disciplines,
including
computer
science.
In
this
paper
we
present
some
recent
results
in
the
design
of
efficient
dynamic
programming
algorithms.
These
results
illustrate
two
approaches
for
achieving
efficiency:
the
first
by
developing
general
techniques
that
are
applicable
to
a
broad
class
of
problems,
and
the
second
by
inventing
clever
algorithms
that
take
advantage
of
individual
situations.
1.
Introduction.
Dynamic
programming
is
a
general
problem-solving
technique
that
has
been
used
widely
in
operations
research,
economics,
control
theory
and,
more
recently,
computer
science.
The
present
paper
will
be
oriented
toward
the
use
of
dynamic
programming
as
a
paradigm
for
designing
algorithms
in
computer
science.
As
computational
efficiency
is
a
major
goal
in
algorithm
design,
we
will
be
interested
in
techniques
which
allow
us
to
speed
up
algorithms
produced
by
straightforward
dynamic
programming.
There
are
two
promising
directions
for
such
research,
namely,
the
development
of
general
techniques
that
are
applicable
to
a
large
class
of
problems,
and
the
invention
of
efficient
algorithms
for
specific
problems
by
taking
advantage
of
their
special
properties.
In
this
paper
we
give
a
review
of
some
recent
progress
in
these
directions.
In
2,
we
discuss
a
general
speed-up
technique
that
can
be
applied
to
dynamic
programming
problems
when
the
cost
function
satisfies
certain
restrictions
known
as
the
Quadrangle
Inequalities.
In
3,
we
give
an
improved
algorithm
for
finding
the
optimal
order
of
multiplying
a
sequence
of
matrices.
We
will
not
give
proofs
for
the
theorems
cited
in
this
paper.
For
proofs
as
well
as
further
discussions,
the
reader
is
referred
to
[8]
for
the
topic
considered
in
2,
and
[4],
[9]
for
the
topic
considered
in
3.
2.
Quadrangle
inequalities.
Example
1.
Given
a
set
of
points
X
on
the
plane,
how
do
we
find
five
points
that
span
a
pentagon
with
maximum
perimeter?
A
natural
solulion
based
on
dynamic
programming
would
be
to
seek
out
maximum
triangles,
maximum
quadrilaterals,
and
maximum
pentagons
in
turn.
It
is
not
difficult
to
argue
that
we
can
restrict
our
consideration
to
the
extreme
points
of
X.
Therefore
let
us
assume
the
convex
hull
of
X
to
be
P
(vl,
v.,
,
vn),
and
the
distance
between
vi
and
vj
to
be
dij.
Then
maximum
triangles
can
be
found
by
computing
the
largest
entry
in
the
matrix
D
+
D
(R)D,
where
D
(dij),
and
(R)
denotes
the
(max,
+)-multiplica-
tion
of
two
matrices
defined
by
F(R)G
(p/j),
wherepij
max
{f
+gli
<-k
<-f}forF=(fij)
and
G
(g/j).
Since
(R)
is
associative,
we
will
write
D
2
for
D
(R)D,
and
D
for
D
t-1
(R)D.
A
maximum
pentagon
then
corresponds
to
a
maximum
entry
in
D
+
D
4,
where
D
4
may
be
evaluated
as
D2(R)D
2.
In
general,
a
maximum
t-gon
can
be
found
by
first
computing
D
t-
and
then
finding
a
maximum
entry
in
D
+D
t-i.
Since
D
t-
can
be
obtained
from
D
in
O(log
t)(max,
+)-multiplications
(see
[7,
4.6.3],
for
example)
at
a
cost
of
O(n
3)
steps
per
matrix
multiplication,
the
answer
can
be
obtained
in
O(n
3
log
t)
steps.
Now
we
pose
the
question:
Can
D
(R)D
be
computed
in
time
faster
than
O(n3)?
It
turns
out
that,
by
properties
of
the
Euclidean
metric
dij,
if
we
let
K(i,
])
denote
*
Received
by
the
editors
February
25,
1982.
f
Xerox
Palo
Alto
Research
Center,
Palo
Alto,
California
94304.
532
资源评论
且走且珍惜2012-11-29很好的讲动态规划的资料！ 下载了！
