z*f
发帖数: 293 | 1 就是不能让你求最佳解，可能求次佳解，或者次次佳解
比如两个STRING ALIGN的话，如果题目要求你限制移动字符的次数 | z*f
发帖数: 293 | 2 或者说从NY 到LAX，的路线问题，题目要求你限制停留次数 （图里面的经过的边的总
数） | s*****g
发帖数: 5159 | 3 你需要精确定义你的问题，这样的描述，得不到你想要的答案。
【在 z*f 的大作中提到】
: 或者说从NY 到LAX，的路线问题，题目要求你限制停留次数 （图里面的经过的边的总
: 数）
| z*f
发帖数: 293 | 4 比如一个无向图求A点到B点的最短距离，但同时也要求所这个最短距离所经过的边的数
目不能大于某个给定值，比如5
【在 s*****g 的大作中提到】
: 你需要精确定义你的问题，这样的描述，得不到你想要的答案。
| s*****g
发帖数: 5159 | 5 Define this way.
Let a graph G(E,V) be undirected. |E|=m and |V|=n. for each e in E, e is
associated with a weight w_e>0. Let A and B be different vertices in V, find
a path, which is a subsect of E, such that its cardinality is less than K
and its norm is minimized.
Now I ask you a question, if the graph a complete one (which means there
must be a path from A to B with lengh 1, 2, ..., n-1).
【在 z*f 的大作中提到】
: 比如一个无向图求A点到B点的最短距离，但同时也要求所这个最短距离所经过的边的数
: 目不能大于某个给定值，比如5
| s*****g
发帖数: 5159 | | a****9
发帖数: 418 | 7 记D[X,Y,i]为无向图中X到Y hop数不超过i的最短距离
最优子结构：
D[X,Y,i] = min {D[X,Z,k]+D[Z,Y,i-k]}
边界：
D[X,Y,1] = W[X,Y]
【在 z*f 的大作中提到】
: 比如一个无向图求A点到B点的最短距离，但同时也要求所这个最短距离所经过的边的数
: 目不能大于某个给定值，比如5
| s*****g
发帖数: 5159 | 8 子结构和原来的问题无异啊，除非最后对归结到i=1的情况，那样的话，是poly(n)但是
不是poly(i)的。
【在 a****9 的大作中提到】
: 记D[X,Y,i]为无向图中X到Y hop数不超过i的最短距离
: 最优子结构：
: D[X,Y,i] = min {D[X,Z,k]+D[Z,Y,i-k]}
: 边界：
: D[X,Y,1] = W[X,Y]
| a****9
发帖数: 418 | 9 又一想， 这样用DP做很浪费，
直接DFS 设置最大深度不就好了
的数
【在 a****9 的大作中提到】
: 记D[X,Y,i]为无向图中X到Y hop数不超过i的最短距离
: 最优子结构：
: D[X,Y,i] = min {D[X,Z,k]+D[Z,Y,i-k]}
: 边界：
: D[X,Y,1] = W[X,Y]
| l******e
发帖数: 470 | 10 DFS做不出吧。
【在 a****9 的大作中提到】
: 又一想， 这样用DP做很浪费，
: 直接DFS 设置最大深度不就好了
:
: 的数
| z*f
发帖数: 293 | 11 这样每个K都要算一次，还有中间Z，好像很大
【在 a****9 的大作中提到】
: 记D[X,Y,i]为无向图中X到Y hop数不超过i的最短距离
: 最优子结构：
: D[X,Y,i] = min {D[X,Z,k]+D[Z,Y,i-k]}
: 边界：
: D[X,Y,1] = W[X,Y]
| y***u
发帖数: 101 | 12 The problem is trivial: Find all vertices within K hops using BFS, then
run Dijkstra.
find
【在 s*****g 的大作中提到】
: Define this way.
: Let a graph G(E,V) be undirected. |E|=m and |V|=n. for each e in E, e is
: associated with a weight w_e>0. Let A and B be different vertices in V, find
: a path, which is a subsect of E, such that its cardinality is less than K
: and its norm is minimized.
: Now I ask you a question, if the graph a complete one (which means there
: must be a path from A to B with lengh 1, 2, ..., n-1).
| l******e
发帖数: 470 | 13 dijkstra may give you a path more than k hops
【在 y***u 的大作中提到】
: The problem is trivial: Find all vertices within K hops using BFS, then
: run Dijkstra.
:
: find
| y***u
发帖数: 101 | 14 I see. 还是用DP吧:)
Let D[u,k] be the shortest distance from source to u with <= k hops
D[u,k] = min_v{D[v,k-1]+d(v,u)}
running time: O(|E|*k)
dijkstra may give you a path more than k hops
【在 l******e 的大作中提到】
: dijkstra may give you a path more than k hops
|
|
