我有一个元素数组 ( arr) 和一个函数 ( f)，它接受 2 个元素并返回一个数字。
我需要数组的排列，这样对于每个inf(arr[i], arr[i+1])尽可能少。（它应该循环，即它也应该最小化）iarrf(arr[arr.length - 1], arr[0])
此外，f工作有点像距离，所以f(a,b) == f(b,a)
如果效率太低，我不需要最佳解决方案，但是一个运行合理且速度快的解决方案，因为我需要实时计算它们（我不知道长度arr是多少，但我认为它可能是大约30）
“这样 f(arr[i], arr[i+1]) 对于 arr 中的每个 i 尽可能少”是什么意思？你想最小化总和吗？你想最小化其中最大的吗？你想首先最小化 f(arr[0],arr[1])，然后在所有最小化这个的解决方案中，选择一个最小化 f(arr[1],arr[2]) 等的解决方案，等等在？
如果你想最小化总和，这正是旅行商问题的全部普遍性（好吧，“度量 TSP”，也许，如果你的 f 确实形成一个度量）。对幼稚的解决方案进行了巧妙的优化，可以为您提供确切的优化并在合理的时间内运行大约 n=30；您可以使用其中之一，或者可以使用一种启发式方法来为您提供近似值。
如果你想最小化最大值，这是一个更简单的问题，尽管仍然是 NP-hard：你可以对答案进行二分搜索；对于特定值 d，为具有 f(x,y) 的对绘制边
如果要按字典顺序最小化它，这很简单：选择距离最短的对并将其作为 arr[0],arr[1]，然后选择最接近 arr[1] 的 arr[2]，依此类推.
根据你的 f(,)s 来自哪里，这可能比 TSP 容易得多；你也可以提一下。
您并不完全清楚您正在优化什么 - f(a[i],a[i+1]) 值的总和，它们的最大值，还是其他什么？
无论如何，由于您的速度限制，贪婪可能是您最好的选择 - 选择一个元素来制作 a[0] （由于环绕而无关紧要），然后选择每个连续的元素 a[i+1]是最小化 f(a[i],a[i+1]) 的那个。
这将是 O(n^2)，但有 30 个项目，除非这是在一个内部循环中或其他什么都可以的。如果你的 f() 真的是关联的和可交换的，那么你也许可以在 O(n log n) 中做到这一点。减少到排序显然不会更快。
我认为问题在这种形式中没有得到很好的定义：
让我们定义 n fcns g_i ： Perms -> Reals
g_i(p) = f(a^p[i], a^p[i+1]), and wrap around when i+1 > n
说你想在所有排列上最小化f实际上意味着你可以选择i的值并在所有排列上最小化g_i ，但是对于最小化g_i的任何p，相关但不同的排列最小化g_j（只是共轭排列）。因此，在每个i的排列上最小化 f 是没有意义的。
除非我们对 f(x,y) 的结构有更多了解，否则这是一个 NP-hard 问题。给定一个图 G 和任何顶点 x,y 如果没有边，则 f(x,y) 为 1，如果有边，则为 0。问题要求对顶点进行排序，以使最大 f(arr[i],arr[i+1]) 值最小化。因为对于这个函数，它只能是 0 或 1，返回 0 相当于在 G 中找到一条哈密顿路径，而 1 表示不存在这样的路径。
该函数必须具有某种不允许此示例的结构，才能使其易于处理。