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