n*****n
发帖数: 100 | 1 比如任意一个network, 每条link上有两个cost=(a,b).现在我们要找一条路径 which,
minimize the sum of \sum (a_i) under the constaint of \sum (b_i) <= B. 在这
种情况下,如果我们想用greedy algorithm,该如何用呢?谢谢! | k****e
发帖数: 100 | 2 贪心法么，每步取最符合要求的，那么，每次取最小的a_i,最后检查sum(b_i)，再回溯。
,
【在 n*****n 的大作中提到】
: 比如任意一个network, 每条link上有两个cost=(a,b).现在我们要找一条路径 which,
: minimize the sum of \sum (a_i) under the constaint of \sum (b_i) <= B. 在这
: 种情况下,如果我们想用greedy algorithm,该如何用呢?谢谢!
| n*****n
发帖数: 100 | 3 那如果从同一节点出去有好几条links,每条的a_i是一样的,但是 b_i不一样,你觉得应
该是随机选一条还是要选一天b_i也最小的?
溯。
【在 k****e 的大作中提到】
: 贪心法么，每步取最符合要求的，那么，每次取最小的a_i,最后检查sum(b_i)，再回溯。
:
: ,
| B*****n
发帖数: 498 | 4 可是greedy algorithm无法garantee optimality啊。
,
【在 n*****n 的大作中提到】
: 比如任意一个network, 每条link上有两个cost=(a,b).现在我们要找一条路径 which,
: minimize the sum of \sum (a_i) under the constaint of \sum (b_i) <= B. 在这
: 种情况下,如果我们想用greedy algorithm,该如何用呢?谢谢!
| k****e
发帖数: 100 | 5 既然是贪心，那么每一步都是选最有利的那个，所以按你的约束条件就选b_i最小
【在 n*****n 的大作中提到】
: 那如果从同一节点出去有好几条links,每条的a_i是一样的,但是 b_i不一样,你觉得应
: 该是随机选一条还是要选一天b_i也最小的?
:
: 溯。
|
|
