خوارزمية للعثور على أقصى تغطية للتسلسلات غير المتداخلة.(أي مشكلة جدولة الفترات الموزونة.)

Question

لدي سؤال مشابه جدًا لـ خوارزمية للعثور على أطول تسلسلات غير متداخلة.

الاختلاف الوحيد عن السؤال المرتبط هو أنه بدلاً من العثور على مجموعة الصفوف غير المتداخلة التي تمثل أطول تسلسل, ، أحتاج إلى العثور على مجموعة الصفوف غير المتداخلة التي تمثل أقصى قدر من التغطية, ، وأعني بذلك مجموع أطوال الصفوف الحد الأقصى (أ طول الصف كون 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)).

Answer 1

هنا O(nlog n)-الوقت، O(n)-المسافة خوارزمية.أولاً، قم بفرز مصفوفة الصف حسب موضع البداية إذا لم تكن بهذا الترتيب بالفعل.سأفترض مؤشرات الصفيف ذات الأساس الصفري.

لنسمي موضع بداية الصف i b(i) وموضع النهاية e(i)، بحيث يكون طوله الإجمالي هو e(i) - b(i) + 1.دعونا أيضًا نحدد الدالة التالية (i) التي تُرجع الموضع داخل قائمة الصف من الصف الأول الذي يمكن أن يظهر على الجانب الأيمن من الصف i.لاحظ أنه يمكن حساب التالي(i) في وقت O(log n) باستخدام بحث ثنائي:فقط احتفظ بجميع مواضع البداية b(i) في المصفوفة b[]، وابحث عن أول j في المصفوفة الفرعية b[i+1 ..n-1] وجود b[j] > e(i).

دعونا نحدد f(i) ليكون الحد الأقصى للتغطية لأي مجموعة غير متداخلة من الصفوف التي تبدأ عند أو بعد صف أنا.نظرًا لأن tuple 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) واحد لوظيفة البحث الثنائي upper_bound().

يمكننا إعادة بناء مجموعة فعلية بهذا الحجم عن طريق حساب كل من المدخلات إلى max() لـ f(0)، ومعرفة أي منها أنتج الحد الأقصى بالفعل، وتسجيل ما إذا كان يشير إلى وجود أو عدم وجود المجموعة 0، ثم التكرار للتعامل مع الباقي (الموافق لـ f(next(0)) أو f(1)).(إذا كان كلا المدخلين متساويين، فهناك حلول مثالية متعددة ويمكننا اتباع أي منهما.)

Answer 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>";