异步旅行商子旅行的局部搜索启发式算法
异步旅行商子旅行的局部搜索启发式算法
提问于 2015-09-05 17:29:02
假设我希望最小化一系列城市之间的距离：
初游：S-1-2-3-4-5-E
最佳旅游：S-5-1-2-3-4-E
旅游必须从S开始，必须在E结束，但可以按任何顺序访问城市。在我的用例中，S和E之间的城市数量将介于1到35之间。
我目前使用的启发式方法是重复的双选择(如伪javascript所示)：
minStopSequence = ['S', 1, 2, 3, 4, 5, 'E'];
changed = true;
while (changed === true) {
changed = false;
for (i = 1; i < minStopSequence.length - 2; i++) {
for (j = i + 1; j < minStopSequence.length - 1; j++) {
newStopSequence = reverseTheMiddleSection(minStopSequence, i, j);
newSegmentDur = getDuration(newStopSequence);
if (newSegmentDur < minSegmentDur) {
minSegmentDur = newSegmentDur;
minStopSequence = newStopSequence;
changed = true;
}
}
}
}这通常无法找到最优的解决方案(例如，在上面的示例中找不到最优的巡演)。我尝试通过一个shift (对于每个索引，每个长度，将该段移动到末尾)来增加这个值，但是这样做会导致两个问题：
- 我重复一些旅游的可能性(效率低下)。
- 我仍然没有达到最佳状态，即使是在5个城市的小游
我已经看到了算法在尺寸小于50的情况下实现了最优性，并且一个“精确”的变化适用于异步图(problem/links/02e7e527676733456d000000.pdf p.11)，但我不确定如何使它适应我的用例。
如果可以使用这种启发式，你能帮我找出如何实现它吗？如果不是，对于最小问题(例如n< 15)和大问题返回最优结果的最合适的启发式是什么？
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-09-06 15:25:01
最简单的算法，可以最优地解决15个城市的问题是指数时间动态程序：https://class.coursera.org/algo2-002/lecture/181。以它为起点，你可以通过把它应用到15个城市的子旅游中来做一个大范围的邻里搜索。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/32415857
复制相关文章
相似问题
腾讯云开发者
