我有一个元素数组(arr
)和一个函数(f
),它接受2个元素并返回一个数字。
我需要数组的排列,这样f(arr[i], arr[i+1])
对i
中的每个arr
都尽可能少(它应该循环,也就是说,它也应该最小化f(arr[arr.length - 1], arr[0])
)
而且,f
的工作方式有点像一段距离,所以f(a,b) == f(b,a)
如果效率太低,我不需要最佳解决方案,但是一个工作合理、速度快的解决方案,因为我需要实时计算它们(我不知道arr
的长度是多少,但我认为可能是30左右)
最佳答案
“对于arr中的每个i,f(arr[i],arr[i+1])尽可能小”是什么意思?你想把总数减到最少吗你想把最大的减到最小吗?是否要先最小化f(arr[0],arr[1]),然后在所有最小化f的解中,选择最小化f的解(arr[1],arr[2]),依此类推?
如果你想最小化这个和,这正是旅行商问题的全部普遍性(好吧,“度量TSP”,也许,如果你的f确实形成了一个度量)对天真的解决方案有巧妙的优化,它会给你精确的优化,并在大约n=30的合理时间内运行;你可以使用其中的一个,或者是给你近似的启发式方法之一。
如果你想最小化最大值,它仍然是一个简单的问题,尽管仍然是NP-难:你可以对答案进行二进制搜索;对于某个特定的值D,绘制具有F(x,y)的对的边。
如果你想把它降到最小,那就是微不足道的:选择最短距离的一对,把它作为ARR〔0〕,ARR〔1〕,然后选择最接近ARR〔1〕的ARR〔2〕,等等。
根据您的f(,)s来自何处,这可能比tsp容易得多;您也可以提到这一点。