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

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

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

※ 引述《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