我最近在采访中遇到一个案例，要求解决的用例属于旅行商问题/车辆路径问题。我能告诉他们实际的问题是什么，以及这个问题涉及到什么数学。我解释了如何使用hadoop的mapreduce范例部分来解决下面提到的用例解释了多个map-reduce作业如何使用jimmy lin和chris dyer在这本书中提到的graph算法来解决这个问题。
出于好奇，我在google上做了一些研究，我可以看到很多针对这个问题的实现和研究以不同的方式进行。我被问到的问题有（x，y）格式中提到的城市坐标，我在google上看到的许多解决方案考虑了一些其他因素，比如单位距离、负/正测量单位等等。所以简言之，我做的研究和阅读越多，我就越困惑。
我的问题是在下面的用例中，什么是可能的解决方案，什么是其中最好的解决方案。如果一些有经验的人能对这一点有所了解，这将有助于澄清我的困惑，更好地理解解决办法。或者如果有人能指引我正确的方向（这样我就不会在探索整个解决方案的海洋时更加困惑）
访谈中询问的用例：
一家公司正在努力寻找最好的解决方案，为其拥有12名员工的300名客户群提供服务。他们需要一个技术解决方案，告诉他们如何能够满足客户的要求，因为业务将增长和其他变化，如客户的位置变化，新的地点增加等。
问题基本上是一种形式的旅行商问题（tsp）或车辆路径问题（vsp）。下面的事情需要在这里完成。
起始坐标为（0,0），城市坐标示例如下。以下是预期在文本文件中作为输入提供的工作解决方案的坐标：
X coordinate Y Coordinate
420 278
421 40
29 178
350 47
298 201
417 186
378 134
447 239
42 114
45 199
362 195
381 243
429 1
338 209
176 9
364 26
326 182
500 129
190 51
489 103
368 142
132 260
305 200
446 137
375 154
440 190
9 118
437 32
383 266什么是正确的方法来处理这个np-hard问题，或者如果不是正确的方法，有什么不同的方法来处理它们的优缺点。
由于其更多的是基于分析的问题，因此可以通过某种可视化来解决这一问题。比如一些图表或者使用r/分析工具
让我知道如果你需要更多的细节，或者如果你可以建议我在哪里可以阅读和理解更多。
提前谢谢
4条答案
按热度按时间sh7euo9m1#
解决np问题没有正确的方法。因为复杂性是指数级的，所以除了一些琐碎的例子之外，任何事情都需要很长的时间。
但是，有一些近似值可以非常接近真实答案，并且可能对您的应用程序足够好（例如，它不是最短路径，但在它的某个相对范围内）。
查看我们的维基百科页面。他们甚至有一些例子。
n9vozmp42#
我不是Maven，但你不能计算原点和所有其他点之间的距离，找到最近的点，然后对该点重复这个过程，直到你覆盖了所有点吗？
qyzbxkaa3#
如果我在面试时问这个问题，我会提出一些类似于本文所描述的，看起来最符合你的任务表述的问题。在本文中，您将找到一种优化的近似方法来解决多个销售人员的问题，所有销售人员从一个点开始。如果我们从特定推销员的家庭/家庭办公室开始，通过解决每个旅行推销员子问题（聚类将主要问题划分为经典问题）来知道员工离开哪里，则可以采用该方法。
如果我们有位置图作为输入，而不仅仅是坐标-我们可以用像mcl这样的图聚类算法来代替k-均值。
slwdgvem4#
事实上，正如德米特里提到的，这是一个多旅行推销员问题的例子。作为np难自然面试官正在寻找你建议一个启发式优化算法。
我认为在这种情况下，关键是他们正在寻找一种能够实时更新的算法，以适应目的地数量和位置的变化。蚁群优化（粒子群优化的一种形式）实际上最初是针对旅行推销员问题制定的，见论文和维基百科：
https://en.wikipedia.org/wiki/ant_colony_optimization_algorithms
“m。多里戈，v。maniezzo等人。colorni，蚂蚁系统：合作代理群体的优化，ieee系统、人与控制论学报，第26卷，第b部分éro 1，第29-41页，1996年。”
这已经被推广到多个旅行推销员的问题，例如，请参阅本文（开源）中的一些不错的工作：
http://www.researchgate.net/publication/263389346_multi-type_ant_colony_system_for_solving_the_multiple_traveling_salesman_problem
在面试的情况下，我会详细说明它的优点如下：1。是一个有效的启发式解决方案；2能够实时更新图形中的两个变化；三。对于额外的点，我提到，一旦在硅片中获得了合理有效的解决方案，就可以以稍微概率的方式为驾驶员自己分配路线，随后可以执行由真实数据驱动的优化。
缺点是，与dmitry建议的先减少搜索空间的问题相比，可能需要相当大的处理能力。其次，如果他们真的想让你起草一个算法，这在面试的时候可能是相当有挑战性的。
有趣的问题：）