作者qazzwsx (qazzwsx)
看板CSSE
标题Re: 请问一个演算法的问题..
时间Tue May 3 17:46:01 2005
※ 引述《ledia (contemplation)》之铭言：
: ※ 引述《qazzwsx (qazzwsx)》之铭言：
: : 最近看到一个bellman-ford 求最短路径的演算法
: : 他的其中一个应用是用来解一组联立不等式
: : 解法是先在原图中加入一个新节点v , 并令v到图上各节点的距离为0
: : 然後用bellman-ford演算法解这个新节点v到图上各点的最短路径
: : 即为联立不等式的解
: : 请问有人知道为什麽要令距离为0吗?
: : 不为零可以吗?
: 不知道你看的是不是 introduction to algorithms
: 假设如书上的举例, 每个未知数指的是某件事发生的时间
: 而某个 constraint xi - xj <= bij 的意思是
: xi 的事件发生要在 xj 事件发生再 bij 时间之前 (bij 可以是正负)
: 我们要找一组 X = (x1, .. xn) 符合给定的 constraint
: 其实就要找到某个时间发生的关系, 符合上述时间的限制
: 但是, 这些事件发生的时间都是相对的
: (课本上也有证明, Ax<=b 是一组解, x+d 也会是一组解)
: 因此, 我们需要一个基础时间: 0
: 而 v0 就担任了这个角色
: 它到各结点距离也都是 0, 意谓着每个事件初始条件同时开始
: 之後用 bellman-ford 再去调整各别的 constraint 之下
: 事件发生的时间的调整 (且这又刚好 map 到最短路径上)
: 当然你也可以令这个基础时间为任意 constant d
: 也就是它到每一个节点都要一样是 d -- 重点是都要一样
: 不然意谓着这些事件先天上又有限制
: 没有同时开始的自由
假使目标只是要找到一组解
不令为0 , 令为d 也可以找到一组解吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.59.211.123