z*****k
发帖数: 57 | 1 给定一有向图G=(V,E)，G中每条边都有非负权值，且G中至少存在一条过所有节点的回
路(circle,环)。请问有没有好的算法求过所有节点的最小权回路？
注意当G接近完全图的时候，存在O(|V|！)条回路.枚举所有回路是不可能的。 |
d**a
发帖数: 84 | 2 这个是hamilton 回路吧，NP
【在 z*****k 的大作中提到】
: 给定一有向图G=(V,E)，G中每条边都有非负权值，且G中至少存在一条过所有节点的回
: 路(circle,环)。请问有没有好的算法求过所有节点的最小权回路？
: 注意当G接近完全图的时候，存在O(|V|！)条回路.枚举所有回路是不可能的。
|
z*****k
发帖数: 57 | 3 不是hamilton回路，不要求只过每个点一次。
只要是过所有点的回路就行，不要求只有|V|条边。
这道题应该是有多项式解的。
【在 d**a 的大作中提到】
: 这个是hamilton 回路吧，NP
|
c**t
发帖数: 2744 | 4 find min-spanning tree first
【在 z*****k 的大作中提到】
: 不是hamilton回路，不要求只过每个点一次。
: 只要是过所有点的回路就行，不要求只有|V|条边。
: 这道题应该是有多项式解的。
|
n*****g
发帖数: 82 | 5 因为每条边的权值为非负，所以必定有一个最优解使得每一个节点只被访问过一次。同
时，对于任何一个最优解，我们都可以找到另外一个最优解使得每一个节点只被访问过
一次，因为我们只要把原来最优解的circle去掉就可以。也就是说，如果这个问题可以
在多项式时间解决，那么travelling sales man problem也可以在多项式时间解决。但
因为TSP是NP-hard，所以。。。
【在 z*****k 的大作中提到】
: 给定一有向图G=(V,E)，G中每条边都有非负权值，且G中至少存在一条过所有节点的回
: 路(circle,环)。请问有没有好的算法求过所有节点的最小权回路？
: 注意当G接近完全图的时候，存在O(|V|！)条回路.枚举所有回路是不可能的。
|
