(ここで頭を悩ませています。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) ?
あなたの助けは非常に高く評価されます!