Блог

В задаче планирования взвешенных интервалов имеется последовательность интервалов {i_1, i_2, ..., i_n} , где каждый интервал i_x представляет непрерывный диапазон (в моем случае, диапазон неотрицательных целых чисел; например i_x = [5,9) ). Обычная цель — установить вес каждого интервала равным его ширине, а затем определить подмножество неперекрывающихся интервалов, общий вес которых является максимальным. Отличное решение приведено по ссылке, которую я только что предоставил.

Я реализовал решение на C , начиная с алгоритма, предоставленного по данной ссылке (который написан на Python в репозитории GitHub здесь .

Однако текущее решение по указанной ссылке — и везде, где я его видел, обсуждалось, — предоставляет только способ захвата одного максимального соответствия. Конечно, в некоторых случаях может быть несколько максимальных соответствий, каждое с одинаковым общим (глобально максимальным) весом.

Я реализовал подход «грубой силы» для захвата всех максимальных соответствий, который я описываю ниже.

Однако, прежде чем обсуждать конкретные детали подхода грубой силы, который я использовал, ключевая проблема в моем подходе грубой силы, которую я хотел бы решить, заключается в том, что мой подход грубой силы фиксирует много ложных срабатываний в дополнение к истинным максимальным соответствиям. Нет необходимости вникать в особенности моего подхода грубой силы, если вы можете просто ответить на следующий вопрос:

Я хотел бы знать, каково (или а) наиболее эффективное улучшение базового O(n log(n)) решения, которое поддерживает захват всех максимальных соответствий, а не только одного максимального соответствия (но если кто-нибудь может ответить, как избежать ложных срабатываний, это также удовлетворит меня).

Я не добиваюсь никакого прогресса в этом, и подход грубой силы, который я использую, начинает неуправляемо взрываться в случаях, когда максимальных подгонок более тысячи (возможно, меньше).

Спасибо!

Подробности подхода грубой силы, который я использую, только если это интересно или полезно:

В существующем исходном коде, на который я ссылался выше, есть одна строка кода, которая отвечает за то, что алгоритм выбирает одно максимальное соответствие, а не идет по пути, по которому он мог бы захватить все максимальные соответствия. Нажмите здесь, чтобы увидеть эту строку кода.Вот оно:

 if I[j].weight   OPT[p[j]] > OPT[j - 1]:
 

Обратите внимание на > (больше знака). Эта строка кода успешно гарантирует, что любая комбинация интервалов с более высоким общим весом, чем любая другая комбинация интервалов для данной подзадачи, сохраняется. Изменив > на >= , можно захватить сценарии, в которых рассматриваемый текущий набор интервалов имеет общий вес, равный наибольшему предыдущему общему весу, что позволило бы захватить все максимальные соответствия. Я хочу зафиксировать этот сценарий, поэтому в моей миграции на C я использовал >= и, в случае, когда выполняется равенство, я продолжаю оба пути в fork с помощью рекурсивного вызова функции.

Ниже приведен код C для (критической) функции, которая фиксирует все оптимальные наборы интервалов (и веса) для каждой подзадачи (отмечая, что окончательное решение получается при последнем индексе, где подзадача соответствует всей проблеме).

Пожалуйста, обратите внимание, что OPTs является одним list из всех потенциальных решений (наборов максимальных интервалов) (т. Е. Каждый элемент OPTs сам по себе является единственным полным решением всех подзадач, состоящих из набора интервалов и соответствующего веса для каждой подзадачи), в то время OPT как используется для описания одного такого полного решения — aпотенциальное максимальное соответствие со всеми интервалами, используемыми для его построения, по одному для каждой подзадачи.

Для стандартного решения задачи планирования взвешенных интервалов, которое я указал выше, полученное решение является простым OPT (единственным, а не списком).

RangeElement Тип в приведенном ниже коде — это просто метаданные, не связанные с обсуждаемой мной проблемой.

RangesVec содержит набор интервалов, который является входным для задачи (правильно отсортирован по конечному значению). PreviousIntervalVec соответствует compute_previous_intervals описанному по ссылке выше.

(Примечание: для всех, кто просматривает приведенный выше код Python, пожалуйста, обратите внимание, что я думаю, что нашел в нем ошибку, связанную с сохранением интервалов в максимальном наборе; пожалуйста, смотрите Здесь комментарий об этой ошибке, которую я исправил в своем коде на C ниже.)

Вот моя реализация «грубой силы», которая фиксирует все максимальные соответствия. Мой подход грубой силы также фиксирует некоторые ложные срабатывания, которые необходимо удалить в конце, и я был бы удовлетворен любым ответом, который дает наиболее эффективный подход для исключения ложных срабатываний, но в остальном использует алгоритм, эквивалентный приведенному ниже.

 void CalculateOPTs(std::vector<std::pair<INDEX_TYPE, std::vector<RangeElement const *>>> amp; OPT, size_t const starting_index = 0)
{
      forks;
    for (size_t index = starting_index; index < RangesVec.size();   index)
    {

        INDEX_TYPE max_weight_to_be_set_at_current_index {};

        INDEX_TYPE max_weight_previous_index {};
        INDEX_TYPE max_weight_previously_calculated_at_previous_interval {};

        INDEX_TYPE current_index_weight = RangesVec[index]->range.second - RangesVec[index]->range.first;

        if (index > 0)
        {
            max_weight_previous_index = OPT[index - 1].first;
        }

        size_t previous_interval_plus_one = PreviousIntervalVec[index];
        if (previous_interval_plus_one > 0)
        {
            max_weight_previously_calculated_at_previous_interval = OPT[previous_interval_plus_one - 1].first;
        }

        INDEX_TYPE weight_accepting_current_index = current_index_weight   max_weight_previously_calculated_at_previous_interval;
        INDEX_TYPE weight_rejecting_current_index = max_weight_previous_index;

        max_weight_to_be_set_at_current_index = std::max(weight_accepting_current_index, weight_rejecting_current_index);

        //if (false amp;amp; weight_accepting_current_index == weight_rejecting_current_index)
        if (weight_accepting_current_index == weight_rejecting_current_index)
        {

            // ***************************************************************************************** //
            // Fork!
            // ***************************************************************************************** //

            // ***************************************************************************************** //
            // This is one of the two paths of the fork, accessed by calling the current function recursively
            // ***************************************************************************************** //

            // There are two equal combinations of intervals with an equal weight.
            // Follow the path that *rejects* the interval at the current index.

            if (index == 0)
            {
                // The only way for the previous weight to equal the current weight, given that the current weight cannot be 0,
                // is if previous weight is also not 0, which cannot be the case if index == 0 
                BOOST_THROW_EXCEPTION(std::exception((boost::format("Logic error: Forking a maximal fitting path at index == 0")).str().c_str()));
            }

            std::vector<std::pair<INDEX_TYPE, std::vector<RangeElement const *>>> newOPT = OPT;
            OPTs.emplace_back(newOPT);
            OPTs.back().push_back(std::make_pair(weight_rejecting_current_index, std::vector<RangeElement const *>())); // std::max returns first value if the two values are equal; so here create a fork using the second value
            OPTs.back()[index].second = OPTs.back()[index-1].second; // The current index is being rejected, so the current set of intervals remains the same for this index as for the previous
            CalculateOPTs(OPTs.back(), index   1);

        }

        // ***************************************************************************************** //
        // If we forked, this is the other path of the fork, which is followed after the first fork, above, exits.
        // If we didn't fork, we proceed straight through here anyways.
        // ***************************************************************************************** //

        OPT.push_back(std::make_pair(max_weight_to_be_set_at_current_index, std::vector<RangeElement const *>()));

        if (max_weight_to_be_set_at_current_index == weight_accepting_current_index)
        {
            // We are accepting the current interval as part of a maximal fitting, so track it.
            //
            // Note: this also works in the forking case that hit the previous "if" block,
            // because this code represents the alternative fork.
            //
            // We here set the intervals associated with the current index
            // equal to the intervals associated with PreviousIntervalVec[index] - 1,
            // and then append the current interval.
            //
            // If there is no preceding interval, then leave the "previous interval"'s
            // contribution empty (from the line just above where an empty vector was added),
            // and just append the current interval (as the first).
            if (previous_interval_plus_one > 0)
            {
                OPT.back().second = OPT[previous_interval_plus_one - 1].second;
            }
            OPT.back().second.push_back(RangesVec[index]); // We are accepting the current interval as part of the maximal set, so add the corresponding interval here
        }
        else
        {
            if (index == 0)
            {
                // If index is 0, we should always accept the current interval, not reject, so we shouldn't be here in that case
                BOOST_THROW_EXCEPTION(std::exception((boost::format("Logic error: Rejecting current interval at index == 0")).str().c_str()));
            }

            // We are rejecting the current interval, so set the intervals associated with this index
            // equal to the intervals associated with the previous index
            OPT.back().second = OPT[index - 1].second;
        }

    }
}
 

Когда существует оптимальное подмножество с равным весом, вам нужно добавить следующий интервал к каждому подмножеству, я не вижу, чтобы это происходило. Общая форма будет выглядеть так

 function go(lastend){

    for(i=0;i<n;i  ){
         if(interval[i].start>lastend){
             optimalsubs = go(interval[i].end)
             if optimalsubs.cost   interval[i].cost > optimal.cost {
                  for(os in optimalsubs){
                        os.add(interval[i])
                  }
                  optimal = optimalsubs
                  optimal.cost  = optimalsubs.cost   interval[i].cost
             }
             else if equal{
                for(os in optimalsubs){
                        os.add(interval[i])
                }
                optimal.append(optimalsubs)
             }
         }

    }
    return optimal
}