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