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