java - 旅行推销员/车辆路线用例的最佳实现

Question

我最近在面试中遇到一个案例，要求解决的用例属于旅行商问题/车辆路径问题。我能够告诉他们实际问题是什么以及问题涉及什么数学。我确实解释了下面提到的用例如何也可以使用 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 

1. 处理这个 NP-hard 问题的正确方法是什么，如果不正确方式 什么可以是不同的方法及其优缺点。

2. 由于它更多的是基于分析的问题，所以某种可视化可以是完成解决这个问题。喜欢一些图表或使用R/分析工具

如果您需要更多详细信息，或者您可以建议我在哪里可以阅读和理解更多信息，请告诉我。

提前致谢

Answer 1

没有解决 NP 问题的正确方法。由于复杂性呈指数级增长，因此除琐碎的示异常(exception)，其他任何事情都将花费很长时间。

但是，有些近似值可以非常接近真实答案，并且可能对您的应用程序足够好(例如，它不是最短路径，但在它的某个相对范围内)。

查看 wikipedia page .他们甚至有一些例子。