問題タブ [partition-problem]

目標を達成するために、セットから最大 1 つの要素を除外できます。例：-

N=3

与えられた数字は = 1,2,5

そう、

セット 1 は :- [1]

セット 2 は :- [2]

どちらのグループにも属さなくても差が小さくなる可能性があるため、5 を除外しました。

N=4

数字 = 1,2,2,5

Set1 = [1,2,2]

セット 2 = [5]

これに最適なアルゴリズムは何ですか? これが NP 完全問題であることはわかっています。そして、力ずくで正しい解決策が得られると思いますが、可能であればアルゴリズムが必要です。

与えられた数値のリスト L = { a1, a2, a3, a4, ... , aN}

問題は、このLを一度だけではなく、アトミックになるまで再帰的に 2 つの部分に分割することです。主なアイデアはこの投稿のようなものですが、再帰的なものを追加しています。

(追加: 6 月 9 日) たとえば、 L = {10, 20, 1, 2} (編集: 6 月 10 日)の場合、解はまず {10, 1, 2} と {20} に分割します。 、次に前者を {1, 2} と {10} に分割し、{1, 2} を {1}, {2} に続けます。これで、L のすべてのメンバーがアトミックになり、分割できなくなりました。

分割後は、ある種の二分木のように見えるはずです。

このように見えるとしましょう..

各ノードでの類似度関数は

この関数の「合計」に従って、リストを分割する（ツリーを作成する）「最適化された」方法を見つけたいと思います。最上位では、この値は下位の値よりも影響が大きくなる可能性があるため、重みを指定する必要があることに注意してください。

let levelは、二分木におけるこのノードのレベルです。

時間計算量が O(2^N) の動的計画法を使用して、これを解決できると思います。ただし、このソリューションは私には遅すぎるようです。誰もがより良い解決策を持っていますか?

最適化と近似の両方も大歓迎です。

前もって感謝します。

次のような問題があります。

一連の数値 (S)、初期値 (V)、および目標値 (T) が与えられた場合、一連の + 操作と - 操作がシーケンス S に割り当てられるかどうかを確認します (操作はシーケンスの順序を尊重する必要があります)。 ) V から開始して、T 以上の数に到達します。また、いつでも破ることができない制限 X があります (合計がいつでも間隔 [0, X] を出る場合、その解パスは無効です。問題のすべての数値もこの間隔内にあります)。

また、制限ルールを尊重して、これらの操作から取得できる最大の合計を見つける必要があります (-last- 操作で合計が制限を超えると、ルールが破られる可能性があります)。

私はそれを調べて、ナップザックの問題とパーティションの問題に対する動的プログラミングの解決策について少し調べましたが、解決策はこの行にあると思います。

ただし、制限ルールを処理する方法と、最大の合計を見つける方法がわかりません。制限の問題は、いくつかの状況で発生します: 足し算され、残りの数が引かれることになる数を見つけるためのナップザックの解を見つけようとするとします。ナップザック ソリューションは合計の上限を破る可能性がありますが、操作の順序が原因で実際​​の合計が破れない可能性があります (制限が実際に破られる前に何かを減算する可能性があり、その後は破られません)。全て）。

これに対する良いアプローチを見つけるのを手伝ってくれる人はいますか? ありがとうございました。

浮動小数点値のセットを、サイズが最大で 1 要素だけ異なる 2 つのセットに分割したいと考えています。さらに、2 つのセット間の値の合計の差は最小限に抑える必要があります。必要に応じて、要素の数が奇数で合計が等しくない場合は、小さい方のセットの合計が大きくなる必要があります。

それが最適な解決策ですが、サブセットサイズの制約に関する正確な解決策だけが本当に必要です。合計の差は厳密に最小である必要はありませんが、それに近づく必要があります。また、小さい方のセット (ある場合) の合計が大きい方がよいと思います。

これはパーティションの問題に関連している可能性がありますが、まったく同じではなく、厳密でもありません。

私の現在のアルゴリズムは次のとおりですが、それを改善する方法があるかどうかは疑問です。

このアプローチに関する私の問題は、実際の複雑さと、それを改善できるかどうかがわからないことです。それは確かに、より大きな合計を持つ小さなサブセットを残すという要件を満たしていません。

私が達成したいことをたまたま実行する既存のアルゴリズムはありますか? そうでない場合は、アルゴリズムを改善するか、それがすでに問題に適している可能性があることを理解する方法を提案できますか?

分割問題は NP 困難であることが知られています。問題の特定のインスタンスに応じて、動的計画法または差分などのヒューリスティック (Karmarkar-Karp アルゴリズムとも呼ばれます) を試すことができます。

後者は、大きな数のインスタンス (動的プログラミングを扱いにくくするもの) には非常に便利なようですが、必ずしも完全ではありません。より良い解を見つける効率的な方法は何ですか (ランダム、タブー検索、その他の近似)?

PS: 質問には裏話があります。2004 年 7 月から、ジョニー ゴーズ ショッピングが SPOJ で利用できる課題があります。現在までに、この課題は 1087 人のユーザーによって解決されましたが、正しい Karmarkar-Karp アルゴリズムの実装よりも良いスコアを獲得したのは 11 人だけでした (現在のスコアでは、Karmarkar-Karp は 11.796614 を与えます)。ポイント）。より良い方法は？（承認された提出によってサポートされる回答が最も望まれますが、コードを公開しないでください。）

パーティションの問題の変形を解決しようとしています。私には2つの重要なひねりがあります。古典的なパーティションの問題のように、2 つだけでなく、k 個のパーティションを解決する必要があります。

次のコードはそれを行います。

https://gist.github.com/ishikawa/21680

また、最適な解を得ることができるように、項目の順序をごちゃまぜにする自由を許可する必要もあります。したがって、古典的な問題では要素の順序をそのままにしておく必要があり、配列が準最適な点で分割されているだけの場合、パーティションは最小です。

どうすればこれに取り組むことができますか? この実際のアプリケーションには、両方のひねりが必要です。すでにこれを処理している Java ライブラリを見つけることができれば、非常にうれしいです。

私にはパーティションの問題のように見える問題を解決しています:私は一連の整数を持っており、それらの合計がすべての整数の合計のちょうど半分です。

動的計画法で解決しようとしていますが、私の解決策はテストではまだ遅すぎます (2/10 テストしかパスできず、残りは遅すぎます)。手伝ってくれてありがとう。

私のコード: