java - 蛮力方法和并发线程之间的选择

Question

我有一个关于图表的问题。考虑一个具有节点和边的图，每条边都有成本。问题是访问所有节点，以使遍历的边的成本总和最小（我猜是旅行推销员问题）。

您会推荐哪种方法？通过递归使用蛮力方法或通过产生线程使用蛮力同时行进不同的路径并计算它们的成本。

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

Answer 1

TSP 是 NP 难的。参见维基百科。它可怕地扩展。在 4 核上对其进行多线程处理可以使其速度提高 4 倍，这与尝试稍微大一点的问题时速度慢 100 倍、1000 倍或 1000000 倍相比简直是微不足道。只需使用真实大小的数据进行尝试，可能需要数年时间才能完成。

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

Answer 2

递归更简单，并且由于它是蛮力的，因此不能保证多线程可以更快地为您提供解决方案。但在重新发明轮子之前，请查看 Concorde TSP Solver：

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

它是免费下载的，包括源代码。

Answer 3

我会采用多线程方法，因为它会并行执行。作为一项额外的优化，我还将在某个共享变量中保持完整路径的最低成本，并让每个线程检查该成本 - 如果在遍历之间它们超过该成本，我将立即终止处理。

Answer 4

由于我不知道您为什么要这样做，也不知道您的约束是什么，所以我投票支持单线程递归。这更容易。