3

(ここで頭を悩ませています。X={x1,x2,...,xn} を整数集合とします。A1,A2,...Am を X の m 個のサブセットとします。任意の i と j に対して、 Ai と Aj は必ずしも互いに素であるとは限りません. ここでの目標は、各 Ai (i=1,...,m) の最大値を効率的に見つけ、操作の数をできるだけ少なくすることです。

たとえば、X={2,4,6,3,1} とそのサブセット A1={2,3,1}、A2={2,6,3,1}、A3={4,2, 3,1}。Max{A1}、Max{A2}、Max{A3} をそれぞれ見つける必要があります。

Max{A1}、Max{A2}、Max{A3} を見つけるための強引な方法は、各 Ai のすべての要素をスキャンすることであり、(m*d) 操作が必要です。m は X のサブセットの数です。 d X のサブセット {Ai} の平均長。

今、私はいくつかの観察があります:

(1) 任意の集合 Y⊆X に対して、max{Y}≤max{X}、

たとえば、Max{X}=6 で 6 は A2 にあるため、Max{A2}=6 を直接見つけることができます。

(2) 任意の 2 つのセット A と B について、A∩B が空でない場合、Max{A} と Max{B} は次のように識別できます。

まず、c=max{A∩B} のように deonted された、A と B の間の共通部分を見つけます。

次に、Max{A}=Max{Max{A-(A∩B)}, c} と Max{B}=Max{Max{B-(A∩B)}, c} を求めます。

これらの最大値を見つけるための他の興味深い観察があるかどうかはわかりません。どんなアイデアでも大歓迎です!

私の質問は、X={x1,x2,...,xn} であり、A1,A2,...Am として示される X のサブセットが m 個ある場合の一般的なケースについて、見つけるためのより効率的な手法があるかどうかです。そのような最大値 Max{Ai} (i=1,...,m) ?

あなたの助けは非常に高く評価されます!

4

2 に答える 2

5

与えられたセットの典型的な表現を仮定すると、ブルートフォースよりも漸近的に優れた方法はありません。セットをスキャンしてそれぞれの最大メンバーを見つけるには線形時間が必要ですが、最大値を決定するにはセットのすべてのメンバーを読み取る必要があるため、線形時間が最適です。

入力表現が各セット内の要素の単なるリストではない場合、他の境界とアルゴリズムが適用される可能性があります。たとえば、入力セットがソートされていて、セットの長さが入力の一部として与えられていることがわかっている場合、時間の最大要素は明らかに、サブセットの数にのみ線形であり、サブセットの長さには比例しません。

于 2012-09-01T04:33:00.200 に答える
3

セットがハッシュで実装されている場合 (または、より一般的には、O(1) 時間でセット内の値の存在を確認できる場合)、ブルート フォース アプローチを改善できます。

サブセットの要素を反復して最大値を維持する代わりに、親セットの要素を降順で反復し、サブセット内のそれらの要素の存在を確認します。最初に見つかった要素は、必然的にサブセットの最大値です。技術的には、これには一般的なケースではまだ O(n) 時間 (n = サブセット カーナリティ) がかかりますが、実際には一般にパフォーマンスが大幅に向上します。(サブセットの数とサイズに関するデータがあり、それらがこのアプローチを支持している場合は、平均的なケースで O(n) を改善できます。)

ただし、このアプローチでは、親セットの要素 (n log n) を並べ替える必要があるため、サブセットの数が親セットのカーナリティよりもはるかに多い場合にのみ価値があります。

于 2012-09-01T04:55:33.343 に答える