複数のセットにわたるIsSubset関係のテスト

Question

グラフのトラバーサルで、アークが既に移動したアークで到達できない追加のノードにアクセスできるかどうかをテストする必要があります。実際には、問題の弧の後続の集合が既に訪問された弧の結合後継の部分集合であるかどうかをテストしたいと思います。ここで

は、所望の動作を説明するためにいくつかの（inoptimal）コードです：

public static bool ReachesAdditionalSuccs(
        ISet<int> additionalSuccCandidates, 
        ISet<int>[] succsAlreadyReachable) 
    { 
     ISet<int> curCombinedSuccsReachable = new HashSet<int>(); 
     foreach (ISet<int> set in succsAlreadyReachable) 
      curCombinedSuccsReachable.UnionWith(set); 
     return (!additionalSuccCandidates.IsSubsetOf(curCombinedSuccsReachable)); 
    } 

私は時間の動的ゲームツリーを展開し、検索の過程でこの操作を実行する必要があるとして、私は事前に構築することはできませんメモリの制約のために後継者の組み合わせセット。訪問されたノードをオプションでマークすることもありません。私は何かをスピードアップするために後継者の直接のセットを作ることができます。

私は今、これを行う最も速い方法が何か不思議です。上記のコードでは、新しいHashsetオブジェクトに組み合わされたセットを一時的に構築します。それは非常に時間がかかり、確かに賢い方法ではありません。私の考えでは、すべてのノードを循環し、ハッシュセットを使用してすべての部分集合に対して手動でテストする方法があります。しかし、それはまた、最善の方法ではないかもしれません...

私は思いついた最後のことは、（O（n）で、マージソートのように）簡単に組み合わせる必要があり、isSubset操作O（n） - 複雑さを有する。これを自分でコーディングすることなくこれを達成するスマートな方法はありますか？多分Framworkに組み込みますか？それとももっと速いアプローチがありますか？

Answer 1

私はあなたが他のセットに含まれていない1つの番号を見つけてすぐそこに止まるまで、セットを1つずつフィルタリングしていると思います。 LINQので表現されること：最悪の場合（すべての数字は既にセットに含まれている）O(mn)あろうため

public static bool ReachesAdditionalSuccs(
        ISet<int> additionalSuccCandidates, 
        ISet<int>[] succsAlreadyReachable) 
{ 
    return additionalSuccCandidates.Where(x => !succsAlreadyReachable.Any(set => set.Contains(x))) 
            .Any(); 
} 

総合努力 - mは数字の数である - セットルックアップ時間を仮定すると、O（1）でありますadditionalSuccCandidatesおよびnはsuccsAlreadyReachableのセット数です。

一つの更なる最適化がSortedSetsを使用されるだろう - あなたが最初の場所で確認する必要はありませんセットフィルタリングするために最小値と最大値を使用することができます。

public static bool ReachesAdditionalSuccs(
        SortedSet<int> additionalSuccCandidates, 
        SortedSet<int>[] succsAlreadyReachable) 
{ 

    var remainingSets = succsAlreadyReachable.Where(set => (set.Min <= additionalSuccCandidates.Min 
                 && set.Max >= additionalSuccCandidates.Min) 
                 || (set.Min <= additionalSuccCandidates.Max 
                 && set.Max >= additionalSuccCandidates.Max)) 
              .ToList(); 

    return additionalSuccCandidates.Where(x => !remainingSets.Any(set => set.Contains(x))) 
            .Any(); 
}