0

私はいくつかの数字のセットを持っていると考えてください。たとえば、{1、2、3、7、8、9、11、15、16} です。私が必要とするのは、このセットをできるだけ少ないサブセットに分割することです。また、最小数と最大数の差が 9 未満であることも必要です。
私の例のセットからは、たとえば
{1, 2, 3, 7, 8} になります。 {9, 11, 15, 16}
これは、Modbus を介した「複数レジスタの読み取り」リクエストの数を最適化するために必要です。
私はすでにセットを連続した数字でサブセットに分割しようとしましたが、それらをマージしましたが、理想的ではありません:
{1, 2, 3}, {7, 8, 9, 11}, {15, 16}または {1, 2, 3}, {7, 8, 9}, {11, 15, 16}
ご覧のとおり、このアプローチでは 2 つではなく 3 つのサブセットが得られます。
では、使用可能なアルゴリズムはありますか?
ありがとう

4

1 に答える 1

3

貪欲なアプローチについてはどうですか。つまり、要素を左からセットに挿入し、必要な違いを超えたら、新しいセットを作成します。

したがって、次の場合1, 2, 3, 7, 8, 9, 11, 15, 16：

1 から始めます
。2-1 = 1 < 9 なので、2を足します。3-1
= 2 < 9 なので、3 を足します
。7-1 = 6 < 9 なので、7 を足します
。8-1 = 7 < 9 なので、8 を足します
。9-1 = 8 < 9 なので、9 を足します
。11-1 = 10 > 9 なので、新しいセットを作成します。
15-11 = 4 < 9 なので、15 を
足します。16-11 = 5 < 9 なので、16 を足します。

出力: {1, 2, 3, 7, 8, 9}, {11, 15, 16}.

ノート：

要素が必ずしも順序付けされていない場合は、最初に単純に並べ替えることができます。

これらのサブセットが連続である必要がない場合、違いはありません。順序付けられた入力から連続セットを選択することは、非連続セットよりも常に優れているためです。

要素が必ずしも順序付けられておらず、サブセットが連続している必要がある場合、問題は少し変わります。

最適性の証明:

S を、任意の入力に対してこのアルゴリズムによって生成された集合割り当てとします。

設定された割り当て T を取ります。

S iを S の i 番目のセットとします
。T iを T の i 番目のセットとします。

S i-sizeを S の i 番目のセットのサイズとします
。T i-sizeを Tの i 番目のセットのサイズとします。

S と T が異なると仮定すると、一部の S iと T iについて、 S i-size != T i-size となります。具体的iには、2 つが異なる最初のセットを選択します。

したがって、 S i-size > T i-sizeまたは S i-size < T i-sizeのいずれかです。

このアルゴリズムは最初からできるだけ多くの要素を使用するため、j > i は不可能です。

j < i の場合、S i+1の最初の要素は T i+1の最初の要素よりも大きくなり、アルゴリズムが貪欲であるため、S i+1には少なくとも T i+1のすべての要素が含まれません。すでに S iに含まれています。

ここで、上記の理由により、S i+2の最初の要素は同様に T i+2の最初の要素よりも大きくなり、したがって Si +2には少なくとも T i+2のすべての要素がまだ含まれていないことが含まれます。 S の前のセット。S と T の残りのセットについても同様です。したがって、少なくとも S と同じ数のセットが T に存在します。

したがって、このアルゴリズムによって生成されたセットの割り当ては、他の割り当てよりも悪いことはありません。したがって、最適です。

于 2013-10-30T11:25:26.350 に答える