サブセット近傍検索との和 - Java

Question

近傍アルゴリズムを使用してサブセット和問題を実装しようとしています。 ここに擬似コードがあります： 1. Generate a random solution for the problem and call it S 2. Compute the neighborhood of S and choose S' as the best solution in the neighborhood 3. If S' is better than S then go to step 4, else go to step 6 4. S = S' 5. Go to step 2 6. Return S as the best solution encountered 10個の要素（+ veと-ve）の集合Xが与えられた場合、その和ができるだけ0に近いようにXの部分集合を見つけなければなりません。

擬似コードに続いて、私はランダムなソリューションSを生成してきましたが、私はSの近傍を計算するにはどうすればよい近所S.

を構築するには、いくつかの困難に遭遇しましたか？ Sの近隣は何ですか？

など。

付近何X = [X0、X1、X2、X3、X4、X5、X6、X7、X8、X9]

S = [X1、X7、X2、X3]

S？

Answer 1

近隣の固有の定義はなく、問題によって異なります。あなたの場合、良い定義はall the tuples that have (at most) n different elements from the current solutionとなります。ここでnは1, 2 , size - 1となります（n = sizeとすれば、解空間全体を考えて、近所には意味がありません）。

D = [X0、X7、X2、X3]、[X4、X7：現在のソリューションは、以下の一連の国連終了から1つのステップの異なるすべてのソリューションを取るあなたの例では

、 x2、x3]、[x6、x7、x2、x3]、[x8、x7、x2、x3]、[x9、x7、x2、x3]、[x1、x0、 、X2、X3]、[X1、X4、X2、X3]、...]

Answer 2

のは、例を使ってみましょう：

Sは、我々はそれから別のものを生成することができます方法を見てみましょう、一つの解決策である。

• 私たちは、それが例えば作成に別のX_Iを追加することができます[X1、X2、X3、X7、X8]
• または私たちは、たとえば作成それからX_Iを削除することができます[X2、X3、X7]

上記の操作のうちの1つを使用してSから得られるそのような解はすべてSの近傍である。そのような解のすべてが近傍を形成する。

[x1、x3、x2]と[x1、x2、x3]は、要素の順序が重要でないのと同じ解決策です。

---

は正式すべての溶液は、対応する溶液はX_Iが含まれている場合は0と1のような V [I] == 1からなる長さ10のバイナリベクトルvです。

例からSに対応するベクトルは次のようになります のS = [0、1、1、1、0、0、0、1、0、0]

をすべてのそのようなベクターであります解のグラフの頂点。このような2つの頂点間のエッジは、上記のような単純な操作を使用して別の頂点に変換できる場合に存在します。

こちらがお役に立てば幸いです。