请教下面的Dynamic Programming的全称是什么？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教下面的Dynamic Programming的全称是什么？

请教下面的Dynamic Programming的全称是什么？# JobHunting - 待字闺中

l*n2013-09-08 07:09

1 楼

下面是从本版面经里找到的关于DP的简称，烦请了解的人帮忙解答。
出自：http://www.mitbbs.com/article_t/JobHunting/32043661.html
2. COV
3. ILP
4. KS
6. LSP
8. ODP
9. SCP
10. SPA
11. SPC
12. TSP
非常感谢。

a*m2013-09-08 07:09

2 楼

晕倒。只知道一个KnapSack

I*s2013-09-08 07:09

3 楼

这些是我以前做研究时一个项目涉及到的常见的DP问题. 我为了资料全面起见加上了,
但多数不会见于面试.
BST Optimal Binary Search Tree Problem
COV Optimal Covering Problem
ILP Integer Linear Programming Problem
KS01 0/1 Knapsack Problem
LCS Longest Common Subsequence Problem
LSP Longest Simple Path Problem
MCM Matrix Chain Multiplication Problem
ODP Optimal Distribution Problem
RAP Production: Reject Allowances Problem
SCP Stagecoach Problem
SPA Shortest Path in an Acyclic Graph Problem
SPC Shortest Path in an Cyclic Graph Problem
TSP Traveling Salesman Problem
WLV Investment: Winning in Las Vegas Problem

【在 l**********n 的大作中提到】

: 下面是从本版面经里找到的关于DP的简称，烦请了解的人帮忙解答。
: 出自：http://www.mitbbs.com/article_t/JobHunting/32043661.html
: 2. COV
: 3. ILP
: 4. KS
: 6. LSP
: 8. ODP
: 9. SCP
: 10. SPA
: 11. SPC

e*82013-09-08 07:09

4 楼

mark~
顺便问句：LSP Longest Simple Path Problem好象没法用dp？

,

【在 I**********s 的大作中提到】

: 这些是我以前做研究时一个项目涉及到的常见的DP问题. 我为了资料全面起见加上了,
: 但多数不会见于面试.
: BST Optimal Binary Search Tree Problem
: COV Optimal Covering Problem
: ILP Integer Linear Programming Problem
: KS01 0/1 Knapsack Problem
: LCS Longest Common Subsequence Problem
: LSP Longest Simple Path Problem
: MCM Matrix Chain Multiplication Problem
: ODP Optimal Distribution Problem

I*s2013-09-08 07:09

5 楼

可以. 递归方程是(latex 格式):
begin{equation}
label{LSP}
f(S,v)=
left{
begin{array}{ll}
{displaystyle max_{d notin S} { f(S cup {d}, d) +c_{v,d} } }
& mbox{if $v ne t$}
0 & mbox{if $v = t$}
end{array}
right.
end{equation}

【在 e*******8 的大作中提到】

: mark~
: 顺便问句：LSP Longest Simple Path Problem好象没法用dp？
:
: ,

e*82013-09-08 07:09

6 楼

这样子时间复杂度是多少呢？我怎么感觉好象是exponential的时间复杂度。。。。

【在 I**********s 的大作中提到】

: 可以. 递归方程是(latex 格式):
: begin{equation}
: label{LSP}
: f(S,v)=
: left{
: begin{array}{ll}
: {displaystyle max_{d notin S} { f(S cup {d}, d) +c_{v,d} } }
: & mbox{if $v ne t$}
: 0 & mbox{if $v = t$}
: end{array}

I*s2013-09-08 07:09

7 楼

问题本身是NP-hard. DP是基于路迳长度的exponential, 不是基于节点数的
exponential. wiki有更多介绍.

【在 e*******8 的大作中提到】

: 这样子时间复杂度是多少呢？我怎么感觉好象是exponential的时间复杂度。。。。

e*82013-09-08 07:09

8 楼

原来如此。。。thanks！
看wiki去～～

【在 I**********s 的大作中提到】

: 问题本身是NP-hard. DP是基于路迳长度的exponential, 不是基于节点数的
: exponential. wiki有更多介绍.