重複していないシーケンスの最大カバレッジを見つけるためのアルゴリズム。（すなわち、重み付き間隔スケジューリングProb。)

StackOverflow https://stackoverflow.com//questions/24026073

質問

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

リンクされた質問との唯一の違いは、重複していないタプルのセットを見つけるのではなく、 最長シーケンス, 、私はを表す重複しないタプルのセットを見つける必要があります 最高の適用範囲, 、それによって私は意味します タプルの長さの合計 は最大値(a)です。 タプルの長さ であること 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)).

役に立ちましたか？

解決

ここには O（nlog n）-時間、O（n）-スペース アルゴリズム。まず、タプルの配列がまだこの順序でない場合は、開始位置で並べ替えます。ゼロベースの配列インデックスを想定します。

タプルi b(i)の開始位置と終了位置e(i)を呼び出して、その全長がe(i)-b(i)+1になるようにしましょう。また、タプルiの右側に現れることができる最初のタプルのタプルリスト内の位置を返す関数next(i)を定義しましょう。Next(i)は、バイナリ検索を使用してO(log n)時間で計算できることに注意してください:すべてのタプルの開始位置b(i)を配列b[]に保持し、部分配列b[i+1の最初のjを検索します。.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の有無を意味するかど（両方の入力が等しい場合、複数の最適解があり、どちらかに従うことができます。)

他のヒント

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

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>";
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top