2

等しい k サブセットアルゴリズムの優れた効率的なアルゴリズムを知っている人はいますか? できれば、100要素のベクトルを処理できるcまたはc ++で、複雑さと時間の見積もりが必要になる可能性があります

元。9 要素ベクトル

x = {2,4,5,6,8,9,11,13,14}

i は合計 = 24 ですべての k=3 の互いに素なサブセットを生成する必要があります。アルゴリズムは、要素の合計が 24 である k 個の互いに素なサブセットがあるかどうかをチェックし、それらを昇順 (サブセット内およびサブセット間) でリストするか、または解が存在しません

ソリューション

解 1: {2 8 14} {4 9 11} {5 6 13}

解 2: {2 9 13} {4 6 14} {5 8 11}

ありがとう

4

1 に答える 1

1

残念ながら、制約付きkサブセット問題は難しい問題です...そして、そのようなkサブセットをすべて生成したい場合は、多くの可能な候補を評価する以外に選択肢はありません。

検索スペースを減らすために実行できる最適化がいくつかあります。

x整数値を含むドメインが与えられた場合、正の整数ターゲットMが与えられた場合、サブセットに正の整数kサイズが与えられた場合、

  1. xに正の整数のみが含まれ、上限Mが指定されている場合、M以上のすべてのアイテムをxから削除します。これらをサブセットの一部にすることはできません。
  2. 同様に、k> 1、与えられたM、および正の整数を含むxの場合、M + min0 + min1...minKより大きいすべてのアイテムをxから削除します。基本的に、サブセットの一部になり得ない大きな値をすべて削除します。小さな値を選択した場合でも、合計がMを超えるためです。
  3. 偶数/奇数の排他原理を使用して、検索スペースを削減することもできます。たとえば、kが奇数で、Mが偶数の場合、合計には3つの偶数または2つの奇数と1つの偶数が含まれることがわかります。この情報を使用してx、合計の一部である可能性のある候補値を削除することにより、検索スペースを減らすことができます。
  4. ベクトルxを並べ替えます。これにより、合計に含めることができない可能性のある値をすばやく除外できます。

これらの最適化の多く（偶数/奇数の除外を除く）は、ベクトルxに負の値が含まれている場合、もはや有用/有効ではありません。この場合、ほとんど徹底的な検索を行う必要があります。

Jilles De Witが指摘しているように、Xに負の数が含まれている場合は、Xの最小値の絶対値をXの各メンバーに追加できます。これにより、すべての値が正の範囲に戻ります。これにより、上記で説明した最適化の一部が再び可能になります。 。ただし、これには、拡大された範囲で正の値を正確に表すことができる必要があります。これを実現する1つの方法は、サブセット選択検索を実行するために、より広い型（たとえば、intではなくlong）を内部的に使用することです。ただし、これを行う場合は、結果を返すときに、この同じオフセットだけ結果サブセットを縮小することを忘れないでください。

于 2010-10-05T18:35:36.463 に答える