我有一个关于图的问题。考虑一个包含节点和边的图,每条边都有一个代价。问题是访问所有节点,以便遍历的边的成本总和最小(我想是旅行商问题)。
你会推荐哪种方法?通过递归使用暴力方法,或者通过产生线程来使用暴力来并发运行不同的路径,并计算它们的成本。
或者你有更好的方法来解决这个问题?
发布于 2011-01-08 15:56:52
TSP是NP难问题。参见维基百科。它的伸缩性非常可怕。在一个4核上进行多线程可以使它的速度提高4倍,这与当你尝试一个稍微大一点的问题时,它的速度慢了100倍,1000倍或1000000倍相比,这算不了什么。只需尝试使用实际大小的数据,可能需要数年时间才能完成。
一种解决方案是元启发式,有几个库,例如Drools Planner (开源,java)。看看它的TTP示例。
发布于 2011-01-08 15:35:05
递归更简单,而且由于它是蛮力的,多线程并不能保证你能更快地得到解决方案。但在您重新发明轮子之前,请查看Concorde TSP Solver:
http://www.tsp.gatech.edu/concorde/index.html
它是免费下载的,并包含源代码。
发布于 2011-01-08 15:01:58
我会选择多线程方法,因为它会并行地做事情。作为额外的优化,我还会在某个共享变量中保留完整路径的最低成本,并让每个线程检查该成本-如果在两次遍历之间超过该成本,我将立即终止处理。
https://stackoverflow.com/questions/4632785
复制相似问题