我有一個元素的數組（arr）和一個函數（f），它接受2個元素並返回一個數字。在一個數組的相鄰項目中最小化函數
我需要一個數組的排列，因此f(arr[i], arr[i+1])儘可能少爲arr中的每個i。 （它應該環路，即它也應該儘量減少f(arr[arr.length - 1], arr[0])）
此外，f作品有點像的距離，所以f(a,b) == f(b,a)
我並不需要的最佳解決方案，如果它的效率太低，而是一個工作合理，並且速度很快，因爲我需要實時計算它們（我不知道arr的長度是多少，但我認爲它可能是30左右）
什麼是「such that f（ arr [i]，arr [i + 1]）對於arr中的每個我儘可能少意味着什麼？你想最小化總和？你想最大限度地減少那些最大的？你想首先使f（arr [0]，arr [1]）最小化，然後在所有使這個最小化的解決方案中，選擇使f（arr [1]，arr [2]）等最小化的那個，等等。上？
如果你想減少總和，這是正是在其全部一般性旅行商問題（好「的指標，TSP」，也許，如果F公司確實形成指標）。天真的解決方案有着巧妙的優化，可以爲您提供準確的最佳性能，並在合理的時間內運行約30次;你可以使用其中的一種，或者給出近似值的啓發式方法之一。
如果你想最大限度地減少最大，這是一個更簡單的問題，但仍然是NP-hard：你可以對答案進行二分法搜索;對於特定值d，繪製具有f（x，y）的對的邊緣如果要將其最小化，則它很平凡：選擇具有最短距離的對並將其設置爲arr [0]， arr [1]，然後選擇最接近arr [1]的arr [2]，依此類推。
根據你的f（，）來自哪裏，這可能是一個比TSP更容易的問題;對你來說也是有用的。
你不完全清楚你在優化什麼 - 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）中做到這一點。顯然沒有更快的減少排序。
我不認爲這種形式的問題是明確的：
讓我們而不是定義N種fcns的G_i：燙髮 - >雷亞爾
g_i(p) = f(a^p[i], a^p[i+1]), and wrap around when i+1 > n
如果說你希望儘量減少˚F在所有排列真的意味着你可以挑選的我值和全排列減少的G_i，但對於任何p最大限度地減少的G_i，一個相關但不同 permatation最小化g_j（只是共軛置換）。因此，說每個i最小化f排列是沒有意義的。
除非我們更多地瞭解f（x，y）的結構，否則這是一個NP難題。給定圖G和任何頂點x，y令f（x，y）如果沒有邊則爲1，如果有邊則爲0。問題要求的是頂點的排序，以便最大限度地減少f（arr [i]，arr [i + 1]）的值。因爲這個函數只能是0或1，所以返回0相當於在G中找到哈密爾頓路徑，而1則表示不存在這樣的路徑。
該函數必須具有某種結構，該結構不允許該示例使其易於處理。
如果你有零基數組，那麼你的循環條件應該是f（arr [arr.length - 1]，arr [0]））吧？ – 2008-11-22 03:31:21