作者genie2 (新挑戰)
看板ck47th320
標題Re: [問題] 再一個演算法的問題
時間Sun Apr 3 14:23:31 2005
※ 引述《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 的路徑存在
不知道有沒有幫助
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 24.130.149.150