要素の配列 ( ) と、 2 つの要素を取り、数値を返すarr関数 ( ) があります。f
配列の順列が必要です。これは、 inf(arr[i], arr[i+1])ごとにできるだけ少なくなります。（そしてループする必要があります。つまり、最小化する必要もあります）iarrf(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(arr[1],arr[2]) などを最小化するソリューションを選択しますか?の上？
sumを最小化したい場合、これは完全に一般的な巡回セールスマン問題です (f が実際にメトリックを形成する場合は、「メトリック TSP」かもしれません) 。正確な最適値を提供し、約 n=30 に対して妥当な時間で実行される単純なソリューションに対する巧妙な最適化があります。それらの1つ、または近似値を与えるヒューリスティックの1つを使用できます。
最大値を最小化したい場合は、まだ NP 困難ですが、より単純な問題です。答えに対して二分探索を行うことができます。特定の値 d に対して、f(x,y) を持つペアのエッジを描画します
辞書編集的に最小化したい場合は、簡単です: 距離が最も短いペアを選択し、arr[0]、arr[1] として配置し、arr[1] に最も近い arr[2] を選択します。 .
f(,) がどこから来ているかによっては、これは TSP よりもはるかに簡単な問題かもしれません。それについても言及していただけると助かります。
f(a[i],a[i+1]) 値の合計、それらの最大値、またはその他の何かを最適化しているものは完全には明らかではありませんか?
いずれにせよ、速度制限があるため、おそらく貪欲が最善の策です-a [0]を作成する要素を選択し（ラップアラウンドのためにどちらでもかまいません）、連続する各要素a [i + 1]を選択して作成しますf(a[i],a[i+1]) を最小化するものになります。
これは O(n^2) になりますが、30 個のアイテムがあります。ただし、これが内側のループにあるか、問題がない場合を除きます。f() が本当に結合的かつ可換的である場合、O(n log n) で実行できる可能性があります。ソートへの削減によって明らかに速くなりません。
問題がこの形式で明確に定義されているとは思わない:
代わりに n fcns g_i を定義しましょう: Perms -> Reals
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については、関連するが異なる順列が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 はそのようなパスが存在しないことを示しています。
関数は、扱いやすいものにするために、この例を許可しないある種の構造を持つ必要があります。