一个旅行家问题算法题的变种题，各位算法大佬来提供个思路

[black11black]

如题，最终公司最近在折腾有个项目涉及到巨额计算量的分布式解耦问题，跟同事简单讨论了一下也没啥结果，我想了想这个问题可以抽象成以下这个算法题：

假设太平洋上有 N 个岛屿，我们有 M 个旅行家，为了简化问题，我们取特殊值假设现在有 1000 个岛屿和 2 个旅行家。这 1000 个岛屿中，任意两个岛屿之间必有且只有一条航空通道，其距离最小值为 1km，最大值为 1000km 。

现在两个旅行家的目标是，他们可以从任意不同的岛屿出发，两人的足迹合起来要覆盖全部 1000 个岛屿，并且两人合计消耗的燃油数要最小（即两人合计走过的里程数最小）。即（某种理想的情况下），A 旅行家要走过其中 500 个岛屿而 B 要走过另外 500 个岛屿，求他们各自负责走过的范围。

==========================================================分割线

旅行家是传统的 DP 算法题，老生常谈了。这个问题如果让我求一个旅行家遍历所有岛屿的最短距离感觉还是蛮简单的，但是如果旅行家增多突然就两眼一抹黑不知道怎么写了。

如同上文说的这个实际上是一个资源分配解耦的问题。在实际生产中遇到的问题是目前有若干个计算任务，每个之间有若干耦合度，我希望将其打包成不同的块分布给不同的机器（核心），希望这种打包的方式可以让不同包之间的总耦合度最小。

因为是资源分配问题，所以除了总里程最小之外还可能有另外一个需求就是让 A 和 B 的里程数方差最小（任务分配到不同节点之后，我们希望每个节点所需的计算时间接近，而不要某个节点早早完成任务，而另一个节点还有很久才能完成）

=========================================================== 各位带佬给提个意见吧，学艺不精，完全没思路。

[MinQ]

我觉得可以用贪心试试，会不会简单一点？虽然不一定是最优解就是……

[whi147]

我有一个想法，找到两个最远的点画横线取中间值，然后画垂直线，垂直线的左右两边的点距离是最短的，这样就完成了两个旅行者对岛屿分割，然后就化简成一个旅行者对 n(0<n<1000)个岛屿的旅行

[Lipoic]

你这个 Tsp 问题我记得是属于 NP 困难吧，很简单能求出最短距离吗？

[black11black]

@Lipoic 没想到这，单纯想到这个问题，NP 困难的话意味着不可解吗？

[black11black]

@whi147 确实，工程上总有很多“妥协”的办法。

[luckyrayyy]

去滴滴美团负责派单的算法工程师里面劫持走一个看看能不能问出来。

[MinQ]

@black11black NP 困难意味着不能在多项式时间内求得最终结果，假设你有 10 万个岛和 1 万个旅行家，需要的时间会成指数倍增加，大概这样

[ayase252]

粒子群算法，不能保证收敛到最优解

[DrKaiser]

从目前的数学理论来说，NP 问题即不通过遍历，无法确认当前解是否为全局最优解

[MisakaTang]

单需要节点计算耗时接近这点可以看一下 work-stealing 算法 可能有点用处

[winglight2016]

具体算法我也给不出来，大概能提供一下思路给 lz 参考：
1.M 应该是小于 N 的，那么把 N 尽量平均分成 M 组，而且尽量靠近——这个通过坐标计算距离可以解决（总距离方差必然最小）
2.问题转化为一个旅行家在每个组里的最短路径，而且互相独立，可以分别计算
以上。

[kilasuelika]

近似解的话，可以简单考虑当成一个旅行家，求出遍历所有节点的路，再拆成两半。
这种规模的题，精确解恐怕是没戏的，只能近似了。

[damingxing]

先说一下，旅行商问题好久没看了全忘光了，我编程只用 ctrl c, ctrl v 行了吧。

这个问题解决方案你肯定是不愿意遍历了对不对。

那么，就这么做：
把这些岛直接分成两拨，分开的方法就是以每个岛到初始旅行家的距离和夹角来定。
也就是设计一个距离和夹角的公式。
那么你就知道了，每个夹角和两个边不就是一个三角形吗。
三角形中效率最高的不就是等边三角形吗。
也就是越和等边三角形接近的就是和最终公式最贴合。

具体公式我懒得想了，你可以再想一想。

为什么这么分呢？
很简单圆形的效率是最高的，对应正方形的效率也就是最高的。

利用对称的原理就可以分开啊。

不用谢。

[MiffyLiye]

NP 问题除了暴力穷举，还可以用 backtracking 或者 branch and bound

曾经写过 1 个旅行家的，用的 branch and bound，几十个岛屿的复杂地图在单机上算起来就很慢了

2 个旅行家，1000 个岛屿，考虑上 distributed branch and bound 吧

[damingxing]

好，现在假定你已经设计出几个公式了。

你需要一个生成岛间距离的算法，然后代入公式进行计算。

最后你会得到一个最优的公式。

[casparchen]

https://developers.google.com/optimization

[sarvatathagata]

要是我来写个乱搞，我会先使用 k means 把点分成 m 组，然后对每一组用模拟退火近似一个解出来。

[cassyfar]

耦合具体指什么？如果是指，任务 B 依赖任务 A 的结果，那么看着很像 topological sorting，类似应用是 package building 。
如果是指，任务 B 需要和任务 A 一起跑，就是说这个节点需要保留任务 A 和任务 B 的 binary，那么你的块不是已经被决定了吗？确保每个快都是独立的，然后用 queue + workers 去跑就好了。

[Lipoic]

@black11black 楼上已经有人解释了，np 问题只是不能在多项式时间内得出最优解。你这个一千个岛，如果用稍微复杂点的近似算法，计算量也已经不小了。当然，最简单的贪心法，那就又太容易了。网上和楼上都能找到不少思路吧，看你怎么平衡精度和计算量了。

[rwalle]

楼主你这根本不是算法题，而是实际项目中需要考虑多方面平衡的非常具体的工程问题。“燃油数要最小”是不要想的了，而且毫无意义，你要考虑的是如何让输出的资源和输入的资源比最大。举个例子，最小燃油数是 50，倒数第二小是 50.1，然后是 50.12 ，50.15 。算法上 50 是正确结果，但是可能要很长时间才能得到，而 50.12 这样水平的结果有个好的初始条件很快就能达到。而这几个结果实际效果差不多。你愿意牺牲大量的时间去寻找最优解吗？