我正在为一个看似非常简单的问题研究算法，但我找不到有效的算法。问题如下: 我有一个数字列表 (0-50) 和一个起始位置，并且必须访问每个数字，同时最小化总行进距离。有些地方需要我先去另一个地方(所以要去 29，我必须先在 26 拿点东西)。但是，如果不生成每个选项，我似乎无法弄清楚如何做到这一点。有什么想法吗？
例如我们有以下内容
startLocation=25;
targetPairs=[[1,5],[7,12],[22,23]]
visitLocations=[4,6,8,2]
这意味着我们必须在 5 之前访问 1，在 12 之前访问 7，在 23 之前访问 22。我们还必须访问位置 4、6、8 和 2。 开始的一个选择是也去 1(距离 24)然后去 4(距离 3 总计 27)然后去 5(距离 1 总计 28)然后我们可以继续到 6(距离 1 总计 29)或全套(7(30)，8(31)，12(35)，22(45)，23(46))。
从逻辑上讲，我们必须访问的位置数量限制为 50 对和 50 个位置。
最佳答案
问题可以通过以下潜在的指数时间算法解决，如果它是 NP-hard(正如我怀疑的那样)那么你将无法做得更好(通过“much”，我的意思是找到一个具有多项式时间复杂度的算法——它很可能会减少指数时间算法的基数。
基本上，在状态空间中进行最佳优先搜索，其中每个状态由两部分组成:当前位置和一组已经访问过的位置。 (不幸的是， 仅仅跟踪已经访问过的城市的数量是不够的。)我们总是从这个状态空间中的每个点最多进行以下 2 次移动:
- 向左移动到最近可访问的位置
- 向右移动到最近可访问的位置
这是因为总有一个最佳解决方案，在每个位置变得可访问后，我们第一次移动到或经过它时就访问了它。这里，“可访问”是指一个位置的所有前辈(包括前辈的前辈等)都已经被访问过。
已经访问过所有位置的任何状态都是目标状态。使用最佳优先搜索(可通过优先级队列实现，或者在这种情况下，只需一个大小为 50 的数组即可)，找到的第一个此类状态将对应于最佳解决方案。该算法所花费的时间与需要访问的位置数量成指数关系。
这种搜索可以通过使用 A* 算法来加速——也就是说，通过使用一些可接受的启发式算法来确定距给定状态剩余距离的下限。在这里想出一些合理的东西应该相当容易——例如设 x 是最左边未访问的位置，y 是最右边，那么如果我们当前的位置 z 在它们之间，则至少需要 min(2(z-x) + y-z, z-x + 2(y-z)) 从 z 访问它们两个. (如果 z 位于所有未访问城市的左侧或右侧，则至少需要 y-z 或至少 z-x。)考虑前辈可以显着改善边界。
关于algorithm - 有约束的一维旅行推销员，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34631958/