{技术}{询问}有没有办法判断这样一个问题是否NPC？

[windstorm]

组里一哥们在做一个课题，遇到一个问题，希望能证明其到底是不是NPC的，如果不是的话就要花精力继续找solution。在这里帮他问一下

问题抽象出来是这样的：

一个无向图G(V,E)，每个图中的节点v有个给定的评价函数n(v)。n(v)是个自然数。

给定一个阈值T，也是一个自然数。

任给图中的两个节点s和d作为源和目的

判定是否存在一条从源s到目的d的路径v0,v1,v2,...,vk使得，对于i,j属于0到k

max(n(vi))-min(n(vj))<T

max(n(vi))表示这条路径上所有点最大的评价函数值，min(n(vj))表示这条路径上所有点最小的评价函数值

如果存在，给出任意一条满足条件路径。

这个问题是NP-complete的么？如果不是，如果有可能的解法能提示一下就最好了，不用太详细。

[Shuo Chen]

不是NPC，简单的回溯算法就能解决。
从S出发，用BFS或DFS找出到D的路径，在执行途中，记录目前路径上的最大和最小的节点，用于剪枝。

[Wu Yin]

不得不说，您知道什么是NPC么？
哈密顿回路我也可以用回溯发解，莫非哈密顿回路问题也不是NPC？

2009/11/11 Shuo Chen <gian...@gmail.com>

--
滚滚长江东逝水，浪花淘尽英雄。
是非成败转头空。
青山依旧在，几度夕阳红。
白发渔樵江渚上，惯看秋月春风。
一壶浊酒喜相逢。
古今多少事，都付笑谈中。

[Shuo Chen]

还真不是NPC，有类似最短路径的算法。
每个节点有三个属性，val low high。
一开始
v.val = n(v)
v.low = -inf
v.high = +inf
low high是个区间，表示到达本节点的最佳路径的min/max。
然后，
s.low = s.high = s.val
用一个队列，s 入队
while not empty:
取队头v，尝试更新相邻节点x的low high 区间，如果更新成功，就把该节点加入队列
更新区间时，把v的区间与x.val合并成新区间，如果新区间小于x的区间，则更新x的区间，这算更新成功。

[windstorm]

这孩昨晚也给我说他想到了bfs后剪枝

多谢Shuo Chen

至于NPC，应该是他没有描述清楚，这个问题只要有合理solution就行。估计是赶deadline赶昏头了。

----------------------------------------------------------------------------------
Yours Sincerely
Kun

www.forwind.cn
http://twitter.com/lk_517

2009/11/11 Shuo Chen <gian...@gmail.com>:

[Cheng, Long]

1.将所有顶点按照n(v)排序
2.从min(s,d)-T的点开始遍历下界到min(s,d)结束
3.对遍历的下界M，求出所有M<=n(v)<M+T的顶点，构成一个新的子图，然后求最短
路径即可。如果这个子图不包含d则跳过。
肯定是多项式的算法。

windstorm 写道:

[Lin Liu]

路径没有什么要求么？ 如果 S D 在同一个连通分支，把该连通分支所有点遍历一遍，找到最大、最小就可以了吧。

2009/11/11 windstorm <likunar...@gmail.com>

[windstorm]

多谢后面两位朋友

我一开始也没仔细看他的问题，帮他发出来后就睡觉了。今天到实验室后想了一下，我有几个疑问：

1 Cheng, Long的方法应该可行，也是最直观证what明其不是NPC的算法。但算法复杂度是不是有点高？

2 我觉得Shuo Chen的第二个方法应该不错，中午给那哥们说说

----------------------------------------------------------------------------------
Yours Sincerely
Kun

www.forwind.cn
http://twitter.com/lk_517

2009/11/11 Cheng, Long <long.x...@gmail.com>:

[windstorm]

Shuo Chen的第二个方法有一个问题：

可能一个节点并不能用low、high这一对值来表示。

比如说从原点到某个中间节点M有两条路，假设val(M) = 11，最大允许阈值是12

第一条路P1的(high,low)是(21,10)
第二条路P2的(high,low)是(15,5)

M又连接了两个还未访问过的节点E、F。val(E)=8，val(F)=18

这种情况下M必须记录两个high low的值。

从原点到节点E，必须通过P2、M、E，而通过P1、M、E，将会导致(high,low)是(21,8)从而违反阈值条件。

从原点到节点F，必须通过P1、M、F，而通过P2、M、F，将会导致(high,low)是(18,5)从而违反阈值条件。

而在这个算法中，如果更新M的值不当，可能导致找不到本来存在的路径。

如此说来，每个节点可能需要被访问多次，每条边也会访问多次，因而通过搜索来解决这个问题可能不是多项式时间的。

----------------------------------------------------------------------------------
Yours Sincerely
Kun

www.forwind.cn
http://twitter.com/lk_517

2009/11/11 windstorm <likunar...@gmail.com>:

[Shuo Chen]

是的，有这个问题。我怀疑可以构造变态数据集让算法变成指数。

[Haibo Huang]

不存在这种数据。
枚举路径上可能的最小节点。O(n)。
把超过大小的节点删除后bfs判断图的联通性。O(n)。
整体复杂度严格满足O(n^2)。

On 11月12日, 上午10时46分, Shuo Chen <giantc...@gmail.com> wrote:
> 是的，有这个问题。我怀疑可以构造变态数据集让算法变成指数。
>
>
>
> windstorm wrote:
> > Shuo Chen的第二个方法有一个问题：
>
> > 可能一个节点并不能用low、high这一对值来表示。
>
> > 比如说从原点到某个中间节点M有两条路，假设val(M) = 11，最大允许阈值是12
>
> > 第一条路P1的(high,low)是(21,10)
> > 第二条路P2的(high,low)是(15,5)
>
> > M又连接了两个还未访问过的节点E、F。val(E)=8，val(F)=18
>
> > 这种情况下M必须记录两个high low的值。
>
> > 从原点到节点E，必须通过P2、M、E，而通过P1、M、E，将会导致(high,low)是(21,8)从而违反阈值条件。
>
> > 从原点到节点F，必须通过P1、M、F，而通过P2、M、F，将会导致(high,low)是(18,5)从而违反阈值条件。
>
> > 而在这个算法中，如果更新M的值不当，可能导致找不到本来存在的路径。
>
> > 如此说来，每个节点可能需要被访问多次，每条边也会访问多次，因而通过搜索来解决这个问题可能不是多项式时间的。
>
> > --------------------------------------------------------------------------- -------
> > Yours Sincerely
> > Kun
>
> >www.forwind.cn
> >http://twitter.com/lk_517
>

> > 2009/11/11 windstorm <likunarmstr...@gmail.com>:

> > > 多谢后面两位朋友
>
> > > 我一开始也没仔细看他的问题，帮他发出来后就睡觉了。今天到实验室后想了一下，我有几个疑问：
>
> > > 1 Cheng, Long的方法应该可行，也是最直观证what明其不是NPC的算法。但算法复杂度是不是有点高？
>
> > > 2 我觉得Shuo Chen的第二个方法应该不错，中午给那哥们说说
>
> > > --------------------------------------------------------------------------- -------
> > > Yours Sincerely
> > > Kun
>
> > >www.forwind.cn
> > >http://twitter.com/lk_517
>

> > > 2009/11/11 Cheng, Long <long.x.ch...@gmail.com>: