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

Question

我有一个数组（arr）元素和一个函数（f），它接受2个元素并返回一个数字。

我需要数组的排列，这样f(arr[i], arr[i+1])对于i中的每个f(arr[arr.length - 1], arr[0])都尽可能少。 （它应循环，即它也应该最小化f(a,b) == f(b,a)）

此外，<=>有点像距离，所以<=>

如果效率太低，我不需要最佳解决方案，但由于我需要实时计算它们（我不知道<=>的长度是什么）但我认为这可能是30岁左右的事情。

Answer 1

对于arr <！>中的每个i，f！arr [i]，arr [i + 1]）的含义尽可能少。意思？你想要最小化总和吗？你想最大限度地减少那些最大的？你想首先最小化f（arr [0]，arr [1]），然后在所有最小化这个的解决方案中，选择最小化f（arr [1]，arr [2]）等的那个，等等上？

如果你想最小化总和，那么正好旅行商问题的完整普遍性（好吧，<！>“公制TSP <！>” ;或许，如果你的f确实形成一个指标）。对天真的解决方案进行了巧妙的优化，这将为您提供准确的最优解，并在合理的时间内运行大约n = 30;你可以使用其中一种，或者一种能给你近似的启发式算法。

如果你想最小化最大，这是一个更简单的问题，虽然仍然是NP难：你可以在答案上进行二元搜索;对于特定值d，绘制具有f（x，y）的对的边

如果你想最小化它 lexiocographically ，它是微不足道的：选择具有最短距离的对并将其设为arr [0]，arr [1]，然后选择arr [ 2]最接近arr [1]，依此类推。

根据f（，）s的来源，这可能比TSP更容易解决问题;你也可以提到它。

Answer 2

你还不完全清楚你在优化什么 - f（a [i]，a [i + 1]）值的总和，它们的最大值或其他什么？

无论如何，由于你的速度限制，贪婪可能是你最好的选择 - 选择一个元素来制作[0]（由于环绕而无关紧要），然后选择每个连续的元素a [i + 1]是最小化f（a [i]，a [i + 1]）的那个。

那将是O（n ^ 2），但有30个项目，除非这是在内循环或什么会好的。如果你的f（）确实是关联的和可交换的，那么你可以在O（n log n）中完成它。通过减少排序显然没有更快。

Answer 3

我不认为问题在这种形式中有明确的定义：

让我们改为定义n fcns g_i：Perms - <！> gt;实数

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 ，相关但不同的 permatation最小化 g_j （只是使排列共轭）。因此，对于每个 i 而言，最小化f的排列是没有意义的。

Answer 4

除非我们对f（x，y）的结构有更多了解，否则这是一个NP难问题。给定图G和任何顶点x，y如果没有边，则f（x，y）为1，如果有边，则为0。问题是要求顶点的排序，以使最大f（arr [i]，arr [i + 1]）值最小化。因为对于这个函数它只能是0或1，返回0相当于在G中找到哈密顿路径，1表示不存在这样的路径。

该函数必须具有某种结构，不允许这个例子使它易于处理。