Re: 請問一個演算法的問題..

看板CSSE (電腦科學及軟體工程)作者ledia (contemplation)時間19年前 (2005/05/03 15:16)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/5 (看更多)

※ 引述《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 -- 重點是都要一樣不然意謂著這些事件先天上又有限制沒有同時開始的自由 -- 有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。　存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你　，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也　是比較不容易被擊倒的人。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.55 ※ 編輯: ledia 來自: 140.112.30.55 (05/03 15:28)