l**********n
发帖数: 303 | 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********m
发帖数: 15480 | |
I**********s
发帖数: 441 | 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*******8
发帖数: 94 | 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**********s
发帖数: 441 | 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*******8
发帖数: 94 | 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**********s
发帖数: 441 | 7 问题本身是NP-hard. DP是基于路迳长度的exponential, 不是基于节点数的
exponential. wiki有更多介绍.
【在 e*******8 的大作中提到】
: 这样子时间复杂度是多少呢？我怎么感觉好象是exponential的时间复杂度。。。。
|
e*******8
发帖数: 94 | 8 原来如此。。。thanks！
看wiki去～～
【在 I**********s 的大作中提到】
: 问题本身是NP-hard. DP是基于路迳长度的exponential, 不是基于节点数的
: exponential. wiki有更多介绍.
|
