北邮通信求定位,谢谢# EE - 电子工程
l*r
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就行)
那么下面的几个问题中,哪些同样可以用动态规划解决,哪些不能,哪些能用但不一定
是最优解决方案的呢?
1. 两个节点之间的次短路径
2. 两个节点之间的最短路径,但是两两节点间的路径“长度”可能为负数
3. 两个节点之间不含重复节点的最长路径
4. 某个节点集合到集合外的某节点的最短路径
i.e. shortestpath(S,t) = min[ shortestpath(s,t)] where s \in S, t \notin S
5. 最短路径的某种近似算法(只要有合理的bound就行)