2

多目的/多目的サブセット和問題の高速な解決策を探しています。

追加の制約（IMOの計算を少し簡単にする）として、合計に含まれるすべての値が正であり、すべて既知の制限値にバインドされていると想定できます。

私は、1つの目的のサブセット和問題に対してO（NK）疑似多項式ソリューションがあることを知っています。私は、ウィキペディアとこのスタック交換の回答に基づいたソリューションを実装しました。

この問題を別の方法で説明すると、限界がわかっている正の数が2セットあります。最初のセットの値Aごとに、合計がAになる2番目のセットの値の組み合わせがあります。最初のセットのすべての値が、2番目のセットに関連付けられた対応する競合しない値の組み合わせを持っていることをアプリオリに知っています。 2番目のセットのどの要素が最初のセット値のそれぞれに関連付けられているかを計算するための既知の高速な方法はありますか？

4

1 に答える 1

1

あなたの問題は、私が修士論文で研究した多重集合制約問題のバリエーションだと思います。

このプロジェクトでは、DPテーブルを検索して解決策を見つけるアルゴリズムを設計しました。疑似多項式ではありませんが、一般的には十分速いと思います。

また、これらの問題を解決するためにPythonツールを実装しています。多分あなたはそれを試してみたいです！

このツールはmsatと呼ばれ、githubで管理されています。

msatを参照できます。

または、単にpipそれをインストールするために使用します（これはPython3ツールです）：

$ pip install msat

紹介のスライドもあります：スライド。

詳細を知りたい場合は、論文を参照してください。

于 2016-04-21T19:37:08.127 に答える