配列の隣接するアイテムの関数を最小化する

Question

要素の配列（ arr ）と、2つの要素を取り、数値を返す関数（ f ）があります。

f（arr [i]、arr [i + 1]）が各 i で可能な限り小さくなるように、配列の置換が必要です。 arr 。 （そして、ループする必要があります。つまり、 f（arr [arr.length-1]、arr [0]））

も最小化する必要があります。

また、 f は一種の距離のような働きをするため、 f（a、b）== f（b、a）

非効率な場合は最適なソリューションは必要ありませんが、かなりリアルタイムで計算する必要があるため、適切に機能し、高速なソリューションは必要ありません（ arr はありますが、30前後の可能性があると思います）

Answer 1

＆quot; f（arr [i]、arr [i + 1]）がarr内の各iについてできるだけ少ないようにすること」平均？ sum を最小化しますか？それらの最大のものを最小化したいですか？最初にf（arr [0]、arr [1]）を最小化し、次にこれを最小化するすべてのソリューションの中で、f（arr [1]、arr [2]）などを最小化するソリューションを選択します。 on？

sum を最小化する場合、これは完全に一般的なトラベリングセールスマン問題です（まあ、「メトリックTSP」、おそらく、f実際にメトリックを形成します）。素朴なソリューションには、正確な最適化を提供し、約n = 30の妥当な時間で実行される巧妙な最適化があります。それらのいずれか、または近似値を得るヒューリスティックのいずれかを使用できます。

最大を最小化する場合は、NP困難ではありますが、より単純な問題です。答えに対してバイナリ検索を実行できます。特定の値dに対して、f（x、y）を持つペアのエッジを描画します

それを辞書編集で最小化する場合は簡単です。最短距離のペアを選択し、arr [0]、arr [1]として配置してから、arr [ 2] arr [1]に最も近い、など。

f（、）がどこから来ているかによって、これはTSPよりもはるかに簡単な問題になるかもしれません。言及することも役立ちます。

Answer 2

最適化する対象が完全に明確ではない-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）でそれを行うことができるかもしれません。ソートを減らすことで明らかに速くなりません。

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 の場合、関連する異なる順列は 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はそのようなパスが存在しないことを意味します。

この関数を扱いやすいものにするためには、関数にこの例を許可しない何らかの構造が必要です。