1

私は次のように抽象化した C# 4.0 でプログラムを作成しています (どのライブラリを使用する必要があるかを理解できるように、言語について言及します。サードパーティのライブラリは使用しません)。

しましょうS = { s1, s2, s3, ..., sn }。

すべてのsi、sjin S、i != jfunctionf(si, sj)は の要素です{ true, false }。ただし、この関数の呼び出しfは非常にコストがかかるため、できるだけ少ない回数で実行する必要があります。

setT = { t1, t2, t3, ..., tm }の空でないサブセットを指定すると、 for all 、およびallおよびinなどのすべての要素を含むSシーケンスを計算します。そのようなシーケンスが存在すると仮定できます。U = u1, u2, u3, ..., uoTf(ui, uj) == falsei < jf(ui, s') == falseis'S - U

これは学校とはまったく関係ありませんが (これは仕事のためです)、私がより多くを学べるように、あなたが考えることができる最も最適な解決策にたどり着くために、最小限の支援を希望します :)

ヒント（私が考えたいくつかのこと:)

  1. 各ノードに少なくとも 1 回アクセスする必要があります。とのすべてのT = { t }と の場合を考えてみましょう。この場合も1回で十分です。f(t, s') == falses'S - T|S| >= 2

  2. 最低限U計算する必要があります。この計算は、次のように表すことができます|S|x|S|。

    • ?： 知らない
    • 1：場合によります。
    • 0：依存しない。
    • -： 私は気にしない。

これを考慮してください (アルゴリズムの開発に役立つ最適な潜在的なチェック シーケンスのパターンがあるかどうかを確認するために、例を見ていきます)。 S = { a, b, c, d, e } T = { a, b, c }(星印で示されます):

     a  b  c  d  e
   ----------------
*a | -  -  -  ?  ?
*b | -  -  -  ?  ?
*c | -  -  -  ?  ?
 d | -  -  -  -  ?
 e | -  -  -  ?  -

U = { a, b, c }最初に。オペランドが等しい場合、 は定義されない-ため、対角線は定義されません。とはすでにセットに含まれているfためa、誰かがそれらに依存していてもかまいません。したがって.bc-

f(a, d)、f(a, e)、f(b, d)、f(b, e)、はf(c, d)、f(c, e)対称性によりすべて等しい候補です。を選択するf(a, d)と、false が返されます。テーブルは次のようになります。

     a  b  c  d  e
   ----------------
*a | -  -  -  0  ?
*b | -  -  -  ?  ?
*c | -  -  -  ?  ?
 d | -  -  -  -  ?
 e | -  -  -  ?  -

ケース 1:U = { a, b, c }

これを見つけるために、運が良ければ、 をチェックし、それらをすべて にすることで、3 つのチェックでそれを行うことがf(b, d)でき ます。f(c, d)f(e, d)false

ケース 2:U = { a, b, c, d, e }

これを見つけるために、運が良ければ、チェックして両方を返すことで、2 つのチェックでそれを行うことがf(b, d)できf(a, e)ますtrue。

（まだ完全には考えていないので、食べに行く必要があります。読んでくれた皆さん、ありがとう！）

ケース 3:U = { a, b, c, d }

ケース 4:U = { a, b, c, e }

4

1 に答える 1

-1

私が理解したのは、サブセットT内の任意のノードから開始してアクセスできるすべてのノードが必要であるということでした...これが意味する場合は、これを試すことができます...

  1. 辞書にすべてのノードを入力します（ノードをキー、ブール値を値として（この値をfalseとして開始））
  2. サブセットTのノードでキューを埋めます（ノードを追加すると、辞書でノードを検索し、訪問済みとしてマークします）
  3. キューの最初の要素を選択し、ノードからアクセスできるかどうかを確認し、辞書でアクセスしたかどうかを検索します。アクセスした場合はスキップし、そうでない場合は、キューに追加して訪問済みとして設定し、キューの最初の要素を削除します。
  4. キューにアイテムがなくなるまで3を繰り返します

tから開始してアクセスできるノードのサブセットは、辞書でマークしたノードです。

それが役に立てば幸い...

于 2012-08-16T19:51:43.383 に答える