21

(順序付けられていない) オブジェクトのセットがあります。オブジェクトの順序付きリストを取得し、そのリスト内に少なくとも 1 つの順序付き競合があった場合は true を返し、それ以外の場合は false を返すオラクルもあります。順序付けされた競合は、オラクルが任意の入力リスト [...、A、...、B、...] に対して true を返すようなオブジェクト (A,B) の順序付けられたペアです。(A,B) が順序付き競合であることは、(B,A) が順序付き競合であることを必ずしも意味しません。

セット内のすべての順序付けられていない競合を特定したい: つまり、(x, y) または (y, x) のいずれかが上で定義した順序付けられた競合であるようなすべてのペア {x, y} を見つけます。オラクルは遅い (呼び出しごとに数十ミリ秒から数百ミリ秒) ため、オラクル呼び出しの数を最小限に抑えることが不可欠です。明らかな素朴なアルゴリズム (セット要素のすべての可能な順序付けられたペアをオラクルに供給する; O(n²) 呼び出し) は受け入れられません。何百ものセット要素があり、全体で 10 未満の競合があると予想されます。

これは私が得た限りです。オラクルが2要素リストに対してtrueを返す場合、リスト内の要素は明らかに競合を構成します。オラクルがいずれかのリストに対して false を返す場合、そのリストには順序付けされた競合はありません。オラクルがリスト L とリスト L の反転の両方に対して false を返す場合、L には順序付けられていない競合はありません。

Put all the set elements in a list L (choose any convenient order).
Invoke the oracle on L.
  If the oracle returns false, invoke the oracle on rev(L).
    If the oracle again returns false, there are no unordered conflicts within L.

# At this point the oracle has returned true for either L or rev(L).
If L is a two-element list, the elements of L constitute an unordered conflict.

Otherwise, somehow divide the set in half and recurse on each

「セットを半分に分割して再帰する」部分で立ち往生しています。2 つの合併症があります。最初に、順序付けられたリストの上半分と下半分を取得するだけでは十分ではありません。これは、競合が分割によって解消される可能性があるためです ([...A1、A2、... An ... を検討してください)。 ][...B1、B2、...Bn ...])。サイズ n/2 のすべてのサブセットを列挙するとうまくいくはずですが、それを効率的に行う方法がわかりません。第 2 に、単純な再帰は、コール スタックの暗黙の状態のために大量の作業を繰り返す可能性があります。A が B と競合することを特定したとします。その場合、A と B の両方を含むリストを使用したオラクルの呼び出しは無駄になりますが、それでも他の競合 {A, x} および {B, x} を除外する必要があります。(A, B) が既にテストされている場合にのみ、M[a][b] が true になるようなメモ行列を維持できますが、そうではありません。

コンテキストによる追加の複雑さ: オブジェクトがリストに複数回表示される場合、2 番目以降のインスタンスは無視されます。さらに、一部のオブジェクトには依存関係があります。(P,Q) が依存関係である場合、Q が P の最初の出現 (存在する場合) の前に出現するオラクル入力は、誤って競合を報告します。このアルゴリズムが開始される前に、すべての依存関係がすでに特定されています。P が A と競合する場合、Q も A と競合するかどうかを知ることはできませんが、これは許容できる制限です。

(コンテキスト: これは、同じソース ファイルに含めることができない C システム ヘッダーのペアを識別するためのものです。「oracle」はコンパイラです。)

4

3 に答える 3

0

何百ものヘッダーと 10 未満の競合があるとおっしゃっているので、競合に関与する n 個のアイテムと O(lg n) 個のアイテムがあるという仮定の下で、最悪の場合の最適なソリューションを提供します。最悪の場合、競合に関与する Theta(lg n) アイテムがある場合、これらのアイテムはすべて互いに競合し、Omega((lg n)^2) より少ないオラクル呼び出しを使用してこれを判断する方法はありません。 . したがって、O((lg n)^2) オラクル呼び出しは、Theta(lg n) 個のアイテムが競合に関与していると仮定すると最適です。

とにかく、ここにアルゴリズムがあります。最初に、別の回答が言ったように、O(lg n) オラクル呼び出しで競合を繰り返し特定し、競合のないセットが残るまで、競合内の 1 つのアイテムをセットから削除します。これには、最大で O((lg n)^2) 回のオラクル呼び出しが必要です。次に、削除したアイテム Z ごとに、Z を非競合セットの先頭に置き、バイナリ検索を実行して競合を作成する後のアイテム X を見つけるか、存在しないと判断します。(そして、そのような X が見つかった場合は、X を削除して繰り返します)。したがって、Z で始まるすべての競合が見つかり、そのような競合はそれぞれ O(lg n) オラクル呼び出しで見つかります。同様に、競合しないリストの最後に Z を配置し、バイナリ検索を実行して、競合を作成するすべての先行要素 X を見つけます。それで、あとは、アルゴリズムの最初のステップで最初に削除したアイテム間の競合をすべて見つけるだけです。しかし、仮定によりそれらは O(lg n) しかないため、これには O((lg n)^2) オラクル呼び出しが必要です。したがって、オラクル呼び出しの総数は O((lg n)^2) です。

于 2013-07-16T00:33:00.637 に答える
0

n*(n-1) の質問に対する答えを見つける必要があります。各質問は、順序付けられたペアに競合があるかどうかです。長さ k のシーケンスを送信し、オラクルが「良い」と言うときはいつでも、k(k-1) 個のそのような質問に対する答えがあります。

これらの n*(n-1) の質問を、デフォルト値 -1 (自己エッジを 0 に設定) を持つ隣接行列として作成して初期化します。シーケンスをランダムに並べ替え、再帰アルゴリズムを適用します。シーケンスに競合がないことがわかった場合はいつでも、マトリックス (0) 内の対応する答えをマークしてください。ちょうど 2 つのシーケンスに競合がある場合は、競合 (1) としてマークします。

さて、大きな反復の後、-1、​​0、および 1 を含むこのマトリックスが得られます。-1 がエッジであると仮定し、最長パスを見つけます。アルゴリズムを再適用します。未知数の数が非常に少なくなるまでこれを続けます。その時点で、オラクルにペアを送信します。

于 2013-07-15T21:21:12.997 に答える