作者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