我最近在面试中遇到一个案例,要求解决的用例属于旅行商问题/车辆路径问题。我能够告诉他们实际问题是什么以及问题涉及什么数学。我确实解释了下面提到的用例如何也可以使用 Hadoop 的 MapReduce 范例部分来解决。 (解释了多个 map reduce 作业将如何解决问题)使用 Jimmy Lin 和 Chris Dyer 撰写的 Data-Intensive Text Processing with MapReduce 一书中提到的 Graph 算法。
出于好奇,我在谷歌上做了一些研究,我可以看到很多实现和研究已经针对这个问题以不同的方式进行。 我被问到的问题有 (x,y) 格式中提到的城市坐标,我在谷歌上看到的许多解决方案都考虑了一些其他因素,如单位距离、负/正测量单位等。所以简而言之,我做了更多的研究和阅读,我变得更加困惑。
我的问题是对于以下用例,哪些是可能的解决方案,哪些是最佳解决方案。如果一些有经验的人可以对此有所了解,这将有助于消除我的困惑并以更好的方式理解解决方案。或者如果有人可以指导我正确的方向(这样我就不会在探索整个解决方案海洋时更加困惑)
面试中被问到的用例:
一家公司正在努力寻找最佳解决方案来为其拥有 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/分析工具
如果您需要更多详细信息,或者您可以建议我在哪里可以阅读和理解更多信息,请告诉我。
提前致谢
最佳答案
没有解决 NP 问题的正确方法。由于复杂性呈指数级增长,因此除琐碎的示异常(exception),其他任何事情都将花费很长时间。
但是,有些近似值可以非常接近真实答案,并且可能对您的应用程序足够好(例如,它不是最短路径,但在它的某个相对范围内)。
查看 wikipedia page .他们甚至有一些例子。
关于java - 旅行推销员/车辆路线用例的最佳实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33589921/