作者changkh (留學生涯)
看板ck47th320
標題Re: [問題] 再一個演算法的問題
時間Sun Apr 3 21:07:45 2005
※ 引述《genie2 (新挑戰)》之銘言：
: ※ 引述《changkh (留學生涯)》之銘言：
: : 又一個演算法的問題。最近快要被這些問題整慘了。
: : 給一個undirected graph(V, E)。V是vertex，E是edge。
: : 每一個edge有兩個weight，分別是WA和WB。
: : 此外給定一個開始的vertex s,和一個結束的vertex t。
: : 是否有演算法能找到一條從s到t的路徑，其中每一個vertex最多只
: : 能經過一次。而且在這個路徑的每一個vertex上，如果把之前經過的edge
: : 的WA和WB分別加起來，(sum WA) < (sum WB) +1？
: : 這個演算法是P還是NP？如果這個問題是是NP，要如何證明？
: 剛剛想到，這個問題是不是可以transform成：
: 對每一個edge，assign weight 為 WB-WA
: 然後對s到t，尋找是否有weight 大於 2 的路徑存在
: 不知道有沒有幫助
嗯，除了s到t要weight大於2之外，路徑上的每一個點的weight也要
大於2。不過把兩個數字變成了一個之後問題似乎簡單許多。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.43.196.35