|
以文本方式查看主题 - W3CHINA.ORG讨论区 - 语义网·描述逻辑·本体·RDF·OWL (http://bbs.xml.org.cn/index.asp) -- 『 算法理论与分析 』 (http://bbs.xml.org.cn/list.asp?boardid=60) ---- 这个问题属于那一类运筹学领域 [讨论] (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=20103) |
|
-- 作者：songlg -- 发布时间：7/3/2005 2:41:00 AM -- 这个问题属于那一类运筹学领域 [讨论] 有n各点，中间通过若干条有向线相连，点与线的属性与TSP问题类似。但这里不是求通过全部点的最短距离，而是指定其中的m个点对，在每一个点对间寻找路径，求这些路径的总长最短，要求对于每一条有向线，最多只能被一个点对所占用 |
|
-- 作者：ljb -- 发布时间：7/11/2005 11:46:00 PM -- generalized steiner network may capture your model and forturnately, it has 2 factor-approximation algorithm by Jain hope it helps |
|
-- 作者：songlg -- 发布时间：7/12/2005 11:06:00 AM -- 谢谢！ 能不能您说得再说的明白一些，我不太懂，搜了一下 2 factor-approximation algorithm，没懂。中文叫什么名字 |
|
-- 作者：ljb -- 发布时间：7/16/2005 4:34:00 PM -- the "generalized steiner network" problem is a well-known NP-hard problem. So polynomial time algorithm can't find a optimal solution for it. So what we can do in polynomial time is to approximate the optimal solution. A 2-factor approximation means there exist a polynomial algorithm that can find a solution with the cost at most two times the cost of optimal solution. 中文叫近似度为2的近似算法。 |
|
-- 作者：songlg -- 发布时间：7/17/2005 12:42:00 AM -- 谢谢 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
78.125ms |