2

現在、次の問題を解決しようとしていますが、どのアルゴリズムを使用すればよいかわかりません。質量識別の分野です。

私は一連の「重み」、*w_i* を持っています。これらを合計すると、合計の重みになります。測定時の総重量には誤差が伴うため、正確ではありません。

総重量Tが与えられた場合、合計に達することができる最も近いk 個の可能な重みの組み合わせを見つける必要があります。ここで、kはユーザーからの入力です。各ウェイトは複数回使用できます。

さて、これは境界整数複数ナップザック問題のように疑わしく聞こえますが、

  • 重量を超える可能性があり、
  • また、エラーの観点からランク付けされたすべてのソリューションが必要です

おそらく、ナップザック問題の複数のスイープを使用して、重み-エラー->重み+エラーから、十分に小さな増分をステップインすることで解決できますが、増分が大きすぎて、使用できる特定の重みの組み合わせを見逃す可能性があります。

通常、ウェイトの数は少なく (4 -> 10 ウェイト)、平均ウェイトに対する合計ウェイトの比率は、通常、約 2 または 3 です。

ここに適している可能性のあるアルゴリズムの名前を知っている人はいますか?

4

2 に答える 2

0

最初の試みとして、私は制約プログラミングに行きます (しかし、私はほとんどの場合そうするので、塩のピンチで提案を受け取ります):

  1. 重みに W=w_1, ..., w_i を指定し、エラーに E=e_1,.., e_i (非対称にすることもできます)、および T を指定します。
  2. すべてのセット S を検索します (重みが一意またはリストの場合) st sum w_1+e_1,..., w_k+e_k (w_1, .., w_k \elem and e_1, ..., e_k \elem E) \approx T は、k から導出されるデルタ内にあります。または、適度に大きな値に設定し、制約を解決するときに値を減らします。

式 w_n op e_m over op \elem +, - (重みと誤差項の任意の組み合わせ) もパラメータ化する必要があることに気付きましたが、頭のてっぺんから外れて、どの制約ソルバーが実行できるかわかりません。それ。いずれにせよ、いつでもプロローグにフォールバックできます。特にウェイトが多い場合は飛ばないかもしれませんが、すぐに解が得られます。

于 2013-07-04T14:35:36.817 に答える