3

最長の重複しないシーケンスを見つけるアルゴリズムに非常に似た質問があります。

リンクされた質問との唯一の違いは、最長シーケンスを表す重複しないタプルのセットを見つける代わりに、最大カバレッジを表す重複しないタプルのセットを見つける必要があることです。タプルの長さは最大です (タプルの長さは、次の文でタプルlast - first + 1の定義が与えられています)。

リンクされた問題とは異なる方法でタプルを表現します。の代わりに(starting index, length)、タプルを(first, last);として表します。たとえば、タプル(3,7)は数値のセットを表します[3, 4, 5, 6, 7]。(エンドポイントが一致していても、タプルは別のタプルとオーバーラップします。つまり、オーバー(2,6)ラップ(6,8) するため、ソリューションに両方を表示することはできません。)

例として、 でソートされた次のタプルのセットを考えてみましょうfirst:

[(0,100), (2,50), (30,150), (60,95), (110,190), (120,150), (191,200)]

ここでの最大セットは[(0,100), (110,190), (191,200)]、 のカバレッジになり101 + 81 + 10 = 192ます。(このソリューションのタプルは重複していないことに注意してください。)

これを解決するための最も複雑でないアルゴリズムの例は何ですか?また、そのアルゴリズムの複雑さはどのくらいですか? (これが で解決できれば最高ですがO(N)、それが可能かどうかは現時点ではわかりません。)

補遺:振り返ってみると、私がここで尋ねている質問は、重み付き間隔スケジューリング問題と同等であることがわかりました。これは、間隔スケジューリング問題の特殊なケースです。

以下の@j_random_hackerの答えは、実際には、重み付けされた間隔のスケジューリング問題に対する既知の解決策であり、時間の複雑さはO(N log(N)).

4

2 に答える 2

4

これは、O(nlog n) 時間、O(n) 空間のアルゴリズムです。最初に、タプルの配列を開始位置でソートします (まだこの順序になっていない場合)。ゼロベースの配列インデックスを想定しています。

タプル ib(i) の開始位置と終了位置 e(i) を呼び出して、その合計の長さが e(i) - b(i) + 1 になるようにします。また、関数 next(i) を定義して、タプル i の右側に現れる最初のタプルのタプル リスト内の位置。next(i) はバイナリ検索で O(log n) 時間で計算できることに注意してください: すべてのタプル開始位置 b(i) を配列 b[] に保持し、部分配列 b[ で最初の j を検索します。 i+1 .. n-1] で、b[j] > e(i) を持ちます。

f(i) を、タプル i以降で始まる重複しないタプルのセットの最大カバレッジと定義しましょう。タプル i 自体がこの最適なセットにあるかどうかにかかわらず、次のようになります。

f(i) = max(e(i) - b(i) + 1 + f(next(i)), f(i+1)) for 0 <= i < n

境界条件 もありますf(n) = 0。

明らかに、可能な限り最大のカバレッジは f(0) によって与えられます。これは簡単に計算できます。疑似 C++ の場合:

int b[] = /* Tuple beginning positions, in nondecreasing order */;
int e[] = /* Tuple end positions */;
int n = /* Number of tuples */;

// Find the array position of the leftmost tuple that begins to the right of
// where tuple i ends.
int next(int i) {
    return upper_bound(b + i + 1, b + n, e[i]);
}

int maxCov[n + 1];    // In practice you should dynamically allocate this

// After running this, maxCov[i] will contain the maximum coverage of any
// nonoverlapping subset of the set of n - i tuples whose beginning positions
// are given by b[i .. n-1] and whose ending points are given by e[i .. n-1].
// In particular, maxCov[0] will be the maximum coverage of the entire set.
void calc() {
    maxCov[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        maxCov[i] = max(e[i] - b[i] + 1 + maxCov[next(i)], maxCov[i + 1]);
    }
}

のループはcalc()n 回実行され、反復ごとに二分探索関数への O(log n) 呼び出しが 1 回行われますupper_bound()。

このサイズの実際のセットを再構築するには、f(0) の max() への両方の入力を計算し、どちらが実際に最大値を生成したかを確認し、それがタプル 0 の有無を意味するかどうかを記録し、再帰を処理して残り (f(next(0)) または f(1) に対応)。(両方の入力が等しい場合、複数の最適解があり、いずれかに従うことができます。)

于 2014-06-04T03:23:59.173 に答える
2

以下のアルゴリズムは、各要素が左端のメンバーである重複しない最大のセットを再帰的に取得し、最大のカバレッジを持つセットを返すことによって機能します。コード内のコメントを参照してください。

PHP で実装されています。ここでテストできますhttp://viper-7.com/xowTRF

このアルゴリズムの複雑さはO(2^N)、またはO(N^2)キャッシングの場合だと思います。同意できない場合は、遠慮なくコメントを残してください。

$set = [[0,100], [2,50], [30,150], [60,95], [110,190], [120,150], [191,200]];
$GLOBALS['cache'] = array(); //cache for overlapping sub problems

function maximumSet($set) {

    if(count($set) === 1) {
        return $set;
    }

    $cache_key = [];

    foreach($set as $k) {
        $cache_key[] = implode($k,'.');
    }

    $cache_key = implode('_',$cache_key);

    if(isset($GLOBALS['cache'][$cache_key])) {
        return $GLOBALS['cache'][$cache_key];
    }

    $maximumResult = null;

    //for each element in the set,
    //get the largest non-overlapping set that the element is a member of
    //once all N sets have been computed, return the largest one
    foreach($set as $k => $element) {

        unset($set[$k]);

        //create a new set $copy, which contains the remaining elements that
        //do not overlap with $element            
        $copy = $set;

        foreach($set as $k2 => $element2) {
            if($element2[0] <= $element[1]) { 
                //element is considered non overlapping if its start 
                //is less than or equal to current element's end
                unset($copy[$k2]);
            }
            else break; //because the list is sorted we can break the 1st time
            //see a non-overlapping element
        }

        if(!empty($copy)) {
            //if there is at least one non-overlapping element
            //recursively get the maximum set
            $maximumSubset = maximumSet($copy);
            //prepend the current element to it
            array_unshift($maximumSubset,$element);
        }
        else {
            //otherwise the maximum non-overlapping set which contains this element
            //is the element itself                
            $maximumSubset = [$element];
        }

        //store the set in the results by coverage
        $coverage = getCoverage($maximumSubset);
        if(is_null($maximumResult) || $maximumResult['coverage'] < $coverage) {
            $maximumResult = [
                'coverage' => $coverage,
                'set' => $maximumSubset
            ];
        }
    }

    $GLOBALS['cache'][$cache_key] = $maximumResult['set'];
    return $maximumResult['set'];
}

function getCoverage($set) {
    $range = 0;
    foreach($set as $v) {
        $range += ($v[1] - $v[0]);
    }
    return $range;
}

$x = maximumSet($set);
print "<pre>";
print_r($x);
print "</pre>";
于 2014-06-04T00:57:05.853 に答える