首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在暴力方法和并发线程之间进行选择

问在暴力方法和并发线程之间进行选择
EN

Stack Overflow用户
提问于 2011-01-08 14:50:18
回答 4查看 754关注 0票数 1

我有一个关于图的问题。考虑一个包含节点和边的图,每条边都有一个代价。问题是访问所有节点,以便遍历的边的成本总和最小(我想是旅行商问题)。

你会推荐哪种方法?通过递归使用暴力方法,或者通过产生线程来使用暴力来并发运行不同的路径,并计算它们的成本。

或者你有更好的方法来解决这个问题?

EN

回答 4

Stack Overflow用户

发布于 2011-01-08 15:56:52

TSP是NP难问题。参见维基百科。它的伸缩性非常可怕。在一个4核上进行多线程可以使它的速度提高4倍,这与当你尝试一个稍微大一点的问题时,它的速度慢了100倍,1000倍或1000000倍相比,这算不了什么。只需尝试使用实际大小的数据,可能需要数年时间才能完成。

一种解决方案是元启发式,有几个库,例如Drools Planner (开源,java)。看看它的TTP示例。

票数 2
EN

Stack Overflow用户

发布于 2011-01-08 15:35:05

递归更简单,而且由于它是蛮力的,多线程并不能保证你能更快地得到解决方案。但在您重新发明轮子之前,请查看Concorde TSP Solver:

http://www.tsp.gatech.edu/concorde/index.html

它是免费下载的,并包含源代码。

票数 1
EN

Stack Overflow用户

发布于 2011-01-08 15:01:58

我会选择多线程方法,因为它会并行地做事情。作为额外的优化,我还会在某个共享变量中保留完整路径的最低成本,并让每个线程检查该成本-如果在两次遍历之间超过该成本,我将立即终止处理。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/4632785

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档