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

我有一个arr元素的array()和一个带有f2个元素并返回一个数字的函数().

我需要的阵列,使得置换f(arr[i], arr[i+1])是尽可能少为每个i在arr.(它应该循环,即它也应该最小化f(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难:你可以做答案的二元搜索; 对于特定值d,绘制具有f(x,y)的对的边

如果你希望尽量减少它lexiocographically,这是微不足道的:挑对最短距离,并把它作为编曲[0],编曲[1],然后选择ARR [2]最接近arr中[1],等等.

根据你的f(,)来自何处,这可能比TSP更容易解决问题; 你也可以提到它.