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

标签 java algorithm hadoop statistics analytics

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

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

提前致谢

最佳答案

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

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

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

关于java - 旅行推销员/车辆路线用例的最佳实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33589921/

相关文章:

java - 用Java制作螺旋桨动画

java - 5!是 120,但输出为 1!是120?

python - 关于 pandas.read_csv 的 float_precision 参数

hadoop - Hive 有等同于 DUAL 的东西吗?

java - 从字符串更改为对象名称 Java

python - 在python中递归实现 'minimum number of coins'

algorithm - 动态规划练习

Hadoop DNS 解析

hadoop - 向 YARN 提交 wordcount 示例(SchedulerUtils.validateResourceRequest 的异常)

java - 为什么 eclipse jsp 编辑器无法解析单独 scriptlet 中的 java block 注释?