发信人: longriver (大河), 信区: BrainTeaser
标 题: 提问：最短路径的变形
发信站: BBS 未名空间站 (Thu Dec 18 12:03:54 2008)

图中两个节点之间的最短路径可以通过动态规划（dynamic programming）解决
那么下面的几个问题中，哪些同样可以用动态规划解决，哪些不能，哪些能用但不一定
是最优解决方案的呢？

1. 两个节点之间的次短路径
2. 两个节点之间的最短路径，但是两两节点间的路径“长度”可能为负数
3. 两个节点之间不含重复节点的最长路径
4. 某个节点集合到集合外的某节点的最短路径
i.e. shortestpath(S,t) = min[ shortestpath(s,t)] where s \in S, t \notin S
5. 最短路径的某种近似算法（只要有合理的bound就行）



--
※ 修改:·longriver 於 Dec 18 12:06:37 2008 修改本文·[FROM: 128.36.]

发信人: hehehehhe (hehehehhe), 信区: BrainTeaser
标 题: Re: 提问：最短路径的变形
发信站: BBS 未名空间站 (Thu Dec 18 13:04:58 2008), 转信


哪个都可以用dp，关键是复杂度。除了3，其他都有polynomial time算法。3是经典的
NPC问题。
【 在 longriver (大河) 的大作中提到: 】
: 图中两个节点之间的最短路径可以通过动态规划（dynamic programming）解决
: 那么下面的几个问题中，哪些同样可以用动态规划解决，哪些不能，哪些能用但不一定
: 是最优解决方案的呢？
: 1. 两个节点之间的次短路径
: 2. 两个节点之间的最短路径，但是两两节点间的路径“长度”可能为负数
: 3. 两个节点之间不含重复节点的最长路径
: 4. 某个节点集合到集合外的某节点的最短路径
: i.e. shortestpath(S,t) = min[ shortestpath(s,t)] where s \in S, t \
notin S
: 5. 最短路径的某种近似算法（只要有合理的bound就行）



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 98.234.]