arrays - 最小化数组相邻项中的函数

Question

我有一个元素数组 (arr) 和一个接受 2 个元素并返回一个数字的函数 (f)。

我需要一个数组的排列，使得 f(arr[i], arr[i+1]) 对每个 i 尽可能小到。 (它应该循环，即它还应该最小化 f(arr[arr.length - 1], arr[0]))

此外，f 的工作原理有点像距离，所以 f(a,b) == f(b,a)

如果效率太低，我不需要最佳解决方案，但需要一个运行良好且速度很快的解决方案，因为我需要实时计算它们(我不知道 arr< 的长度是多少 是，但我认为它可能在 30 左右)

Answer 1

“使得 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[ 2] 最接近 arr[1]，依此类推。

根据 f(,) 的来源，这可能比 TSP 更容易解决问题；您也可以提及这一点。