6

次の簡単な例のような一連の範囲がある場合...

[
    [12, 25], #1
    [14, 27], #2
    [15, 22], #3
    [17, 21], #4
    [20, 65], #5
    [62, 70], #6
    [64, 80]  #7
]

...最大に交差するサブセットをどのように計算しますか(言い方はよくわかりませんが、「交差し、カーディナリティが最も高い範囲のサブセット」を意味します)、交差度(そのサブセット内の範囲のカーディナリティ)を決定します)?

論理的には解決できますし、それを素朴なアルゴリズムに変換できるかもしれません。リストを下に進むと、1-5 が交差し、5-7 が交差し、#5 が両方のセットと交差することがわかります。

私が望む結果は、単にサブセットです。これにより、カーディナリティに関する情報が得られ、すべてが交差する限り、セットの交差を簡単に計算できます。上記の例では、 になります[[14, 27],[15, 22],[12, 25],[17, 21],[20, 65]]。

思いつきで、各範囲をグラフ ノードに変換し、交差する範囲を接続して、最大の全結合グラフを見つけようとするかもしれません。

また、最初から開始し、交差しない要素にヒットするまで、交差する範囲のリストを構築し続け、それぞれに実行中の交差をチェックすることを繰り返し考えていました。その後、新しいリストを開始します。各項目を既存の交差に対して引き続きチェックします。ただし、これが完全かどうかはわかりません。

何かを実装することに挑戦することもできますが (lang は ruby​​ FWIW)、他の人がこの問題をどのように解決するか、また最も効率的でエレガントな方法は何かを知りたいです。

アップデート：

これは、最大クリーク問題の特定のケースであり、NP 困難であり、したがって実際には困難であると思います。近似/実世界での使用に関する提案をいただければ幸いです。

参照: http://en.wikipedia.org/wiki/Maximum_clique /グラフ内のすべての完全なサブグラフを検索

更新 2

ここで、この問題の NP 困難性と NP 完全性の良い証拠を見つけました: http://www.cs.bris.ac.uk/~popa/ipl.pdf

その時はこれで終わりのようです。ごめんなさい！十分に貪欲な近似で作業します。ありがとう。

回答で述べたように、紙がこの問題を説明しているとは思いません...おそらく、範囲に基づいて詳細な情報がここにあります。

4

2 に答える 2

16

問題を正しく理解していれば、リンク先の論文で説明されている NP 問題のインスタンスではありません。これが問題の私の理解と多項式時間の解決策です。

  1. 実数の範囲の有限集合が与えられます。たとえばn : [A 1 , B 1 ], [A 2 , B 2 ], ..., [A n , B n ] で、A i ≤ B iです。

  2. 開始点と終了点のソートされたリストを作成し、番号順に並べ替えて、その点が開始点か終了点かを示します。

あなたの例では、これは次のようになります: 12+、14+、15+、17+、20+、21-、22-、25-、27-、62+、64+、65-、70-、80-

  1. 初期化curOverlapしmaxOverlapてゼロにします。

  2. curOverlap+ ごとに増分し、- ごとに減分しながら、リストを反復処理します。maxOverlap = max(curOverlap, maxOverlap)増分ごとに設定します。

例を続けるには:
val, cur, max
12, 1, 1
14, 2, 2
15, 3, 3
17, 4, 4
20, 5, 5
21, 4, 5
22, 3, 5
25, 2, 5
27, 1, 5
62, 2, 5
64, 3, 5
65, 2, 5
70, 1, 5
80, 0, 5

最大オーバーラップは 5 です。最大オーバーラップが発生した場所を知りたい場合は、最大に関連付けられた val を保存することもできます。この例では 20. になります。その後、範囲の初期セットを調べて、20 を含む 5 を見つけるのは簡単です。

-編集- 値が繰り返される場合は、各値のマイナスの前にプラスを数えて、1 つのポイントで重複する範囲を含めるようにします。

于 2013-02-25T02:32:12.950 に答える
3

以下は、Dave によって提案されたソリューションの Java 実装です。

public static List<Range> getMaxIntersectingSubset(List<Range> ranges) {
    // First, we collect "a sorted list of the starting and ending points".
    // We're sorting such that all lower bounds come first
    List<Bound> intersections = Arrays.stream(ranges)
        .flatMap(arr -> Stream.of(Bound.ofLowerBound(arr[0]), Bound.ofUpperBound(arr[1])))
        .sorted(Comparator
            .comparing(Bound::value)
            .thenComparing((a, b) -> Boolean.compare(!a.isLowerBound(), b.isLowerBound())))
        )
        .collect(Collectors.toList());

    long curOverlap = 0;
    long maxOverlap = 0;
    List<Integer> indexes = new ArrayList<>();

    // Then we iterate the list, searching for the highest overlap
    for (int i = 0; i < intersections.size(); i++) {
        Bound intersection = intersections.get(i);
        curOverlap += (intersection.isLowerBound() ? 1 : -1);
        if (curOverlap > maxOverlap) {
            maxOverlap = curOverlap;
            indexes.clear();
            indexes.add(i);
        }
        else if (curOverlap == maxOverlap) {
            indexes.add(i);
        }
    }

    return indexes.stream()
        .map(index -> Range.of(intersections.get(index).value(), intersections.get(index + 1).value()))
        .collect(Collectors.toList());
}

public class Bound {

    private final int value;
    private final boolean lower;

    private Bound(int value, boolean lowerbound) {
        this.value = value;
        this.lower = lowerbound;
    }

    public static Bound ofLowerBound(int value) {
        return new Bound(value, true);
    }

    public static Bound ofUpperBound(int value) {
        return new Bound(value, false);
    }

    public int value() {
        return this.value;
    }

    public boolean isLowerBound() {
        return this.lower;
    }
}

public class Range {

    private final int start;
    private final int end;

    private Range(int start, int end) {
        if (start > end) {
            throw new IllegalArgumentException("start > end");
        }
        this.start = start;
        this.end = end;
    }

    public static Range of(int start, int end) {
        return new Range(start, end);
    }

    public int start() {
        return this.start;
    }

    public int end() {
        return this.end;
    }
}

これらはいくつかのテスト セットです。

  1. このStackoverflowの質問から

    int[][] ints = {
    { 1, 100 },
    { 30, 95 },
    { 10, 60 },
    { 15, 25 },
    { 33, 66 },
    { 20, 50 },
    { 51, 100 },
    { 25, 70 }
};

    上記の質問のOPによると、結果は[ 30, 55 ]. 提供されたコードは、この結果を出力します。ただし、幅は狭くなりますが、別のオーバーラップがあります。下の写真を参照してください。

    テストケース #1a

    テストケース #1b

  2. この質問のOPは、このリストについて言及しています：

    int[][] ints = {
    { 12, 25 },
    { 14, 27 },
    { 15, 22 },
    { 17, 21 },
    { 20, 65 },
    { 62, 70 },
    { 64, 80 }
};

    ここで、出力は[ 20, 21 ]です。これは、次の図と一致します。

    テスト ケース #2 の図

于 2020-09-15T12:50:56.527 に答える