C**********n
发帖数: 100 | 1 计算机网络连接问题:
将n(n<=30)台计算机连成网络，连接方法是:除了首尾两台计算机只与一台计算机相连
外，其他所有的计算机都(只)与两台计算机相连。连接的长度为计算机连接电缆的长度。
求一种连接方式，使得所需要电缆总长度最短。
这道题怎么作阿，好像不能用动态规划把。是不是只能穷举了？ |
w****r
发帖数: 1384 | 2 忽然发现,这不就是30个点连成一条直线最短么?
中间的点都与两边的点相连(两个连接),首尾都只有一个连接
度。
【在 C**********n 的大作中提到】
: 计算机网络连接问题:
: 将n(n<=30)台计算机连成网络，连接方法是:除了首尾两台计算机只与一台计算机相连
: 外，其他所有的计算机都(只)与两台计算机相连。连接的长度为计算机连接电缆的长度。
: 求一种连接方式，使得所需要电缆总长度最短。
: 这道题怎么作阿，好像不能用动态规划把。是不是只能穷举了？
|
n******r
发帖数: 1247 | 3 个人意见，随便说说
当TSP处理，然后把最长的一段连接去掉，虽然不能保证最优，但是算出来的肯定
是一个非常好的上界
30个city的TSP用最原始的L-K算法，基本是100%的成功率，普通电脑上几秒内找到最优
，虽然总的解的个数是30！
这个上界应该还可以继续优化，但是如果近似解就可以的话，TSP是一个思路
度。
【在 C**********n 的大作中提到】
: 计算机网络连接问题:
: 将n(n<=30)台计算机连成网络，连接方法是:除了首尾两台计算机只与一台计算机相连
: 外，其他所有的计算机都(只)与两台计算机相连。连接的长度为计算机连接电缆的长度。
: 求一种连接方式，使得所需要电缆总长度最短。
: 这道题怎么作阿，好像不能用动态规划把。是不是只能穷举了？
|
m*****f
发帖数: 1243 | 4 你确定这道题没错？
首尾一个连接， 其他点只有两个连接， 这只有一条直线才能做到， 根本不可能有分叉
题错了吧 |
C**********n
发帖数: 100 | 5 可能是我题目没说清楚。
这么说把，n台计算机互不相连，现在给你很长的一条电缆，让你把这些计算机连起来。
除了首尾只和一台计算机相连外，另外n-2台各与两台计算机相连。
你说的没错，是只有一条直线相连，关键是怎么找这条直线。
分叉
【在 m*****f 的大作中提到】
: 你确定这道题没错？
: 首尾一个连接， 其他点只有两个连接， 这只有一条直线才能做到， 根本不可能有分叉
: 题错了吧
|
f*****e
发帖数: 2992 | 6 dijstra算法,p1 到 p2-n的最短距离, p2-到 p3-pn的最短距离,...
然后从中选一个最短的出来
来。
【在 C**********n 的大作中提到】
: 可能是我题目没说清楚。
: 这么说把，n台计算机互不相连，现在给你很长的一条电缆，让你把这些计算机连起来。
: 除了首尾只和一台计算机相连外，另外n-2台各与两台计算机相连。
: 你说的没错，是只有一条直线相连，关键是怎么找这条直线。
:
: 分叉
|
m*****f
发帖数: 1243 | 7 这样岂不是旅行商问题....解法很多阿， 贪心法， 模拟退火...
来。
【在 C**********n 的大作中提到】
: 可能是我题目没说清楚。
: 这么说把，n台计算机互不相连，现在给你很长的一条电缆，让你把这些计算机连起来。
: 除了首尾只和一台计算机相连外，另外n-2台各与两台计算机相连。
: 你说的没错，是只有一条直线相连，关键是怎么找这条直线。
:
: 分叉
|
C**********n
发帖数: 100 | 8 不一定对把，
这里首尾未定，也能用dijstra法吗？
【在 f*****e 的大作中提到】
: dijstra算法,p1 到 p2-n的最短距离, p2-到 p3-pn的最短距离,...
: 然后从中选一个最短的出来
:
: 来。
|
C**********n
发帖数: 100 | 9 对于n<30的TSP问题用什么解法比较好?
【在 m*****f 的大作中提到】
: 这样岂不是旅行商问题....解法很多阿， 贪心法， 模拟退火...
:
: 来。
|
g*******y
发帖数: 1930 | 10 是给定30个电脑的coordinates的话，好像就是Euclidean TSP，这个貌似就不是NPC了?
我记得我很久以前问过类似的问题，好像是应该用delaunay triangle，解这个
Euclidean TSP |
n******r
发帖数: 1247 | 11 Euclidean TSP is TSP with Euclidean distance. It is NPC.
了?
【在 g*******y 的大作中提到】
: 是给定30个电脑的coordinates的话，好像就是Euclidean TSP，这个貌似就不是NPC了?
: 我记得我很久以前问过类似的问题，好像是应该用delaunay triangle，解这个
: Euclidean TSP
|
k***e
发帖数: 556 | 12 given Euclidean TSP it is easy to design an approximation algorithm with
ratio
2 (not so sure)
it is still npc
了?
【在 g*******y 的大作中提到】
: 是给定30个电脑的coordinates的话，好像就是Euclidean TSP，这个貌似就不是NPC了?
: 我记得我很久以前问过类似的问题，好像是应该用delaunay triangle，解这个
: Euclidean TSP
|
