use*_*611 12 java algorithm statistics analytics hadoop
我最近遇到了一个案例,当被要求解决的用例属于旅行商问题/车辆路径问题时.我能够告诉他们实际问题是什么以及问题涉及什么数学.我确实解释了如何使用Hadoop的MapReduce范例部分解决下面提到的用例.(解释了多个地图减少工作将如何解决问题)使用本书中提到的数据密集文本处理与MapReduce提到的图谱算法"由Jimmy Lin和Chris Dyer编写.
出于好奇,我在google上做了一些研究,我可以看到很多实现和研究已经针对不同风格的这个问题做了.问题我被问到有(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难题,或者如果不正确的方式可能是不同的方法与他们的利弊.
由于其更多基于分析的问题可以进行某种可视化来解决这个问题.像一些图形或使用R /分析工具
如果您需要更多详细信息,或者您可以建议我可以阅读和了解更多内容,请告诉我.
提前致谢
我不是专家，但你不能只计算原点和所有其他点之间的距离并找到最近的点，然后对该点重复该过程，直到覆盖所有点吗？