0

重み付けされた間隔のスケジューリング問題では、各間隔が連続した範囲を表す間隔 のシーケンスがあります (私の場合、非負の整数の範囲; たとえば)。通常の目標は、各間隔の重みをその幅に等しく設定し、合計重みが最大になる重複しない間隔のサブセットを決定することです。私が提供したリンクで優れた解決策が提供されています。{i_1, i_2, ..., i_n}i_xi_x = [5,9)

特定のリンクで提供されているアルゴリズムから始めて、ソリューションを C++ で実装しました ( GitHub リポジトリのPython で記述されています。

ただし、指定されたリンクでの現在のソリューション (および私がそれについて議論した他のすべての場所) は、単一の最大フィットをキャプチャする方法のみを提供します。もちろん、場合によっては、複数の最大適合があり、それぞれが同じ合計 (全体的な最大) 重みを持つ場合があります。

以下で説明するように、すべての最大適合をキャプチャするための「ブルート フォース」アプローチを実装しました。

ただし、私が使用したブルート フォース アプローチの具体的な詳細について説明する前に、解決したい私のブルート フォース アプローチの重要な問題は、私のブルート フォース アプローチが、真の最大適合に加えて、多くの偽陽性を捕捉することです。 . 次の質問に答えることができれば、私のブルート フォース アプローチの詳細を掘り下げる必要はありません。

1 つの最大適合だけでなく、すべての最大適合をキャプチャすることをサポートする基本的なO(n log(n))ソリューションに対する最も効率的な拡張機能 (または) を知りたいです(ただし、誰かが偽陽性を回避する方法に答えることができれば、それも私を満足させます) ）。

私はこれについて何の進歩も遂げていません.私が使用している力ずくのアプローチは、数千を超える（おそらくそれ以下の）最大適合がある場合に、手に負えないほど爆発し始めます.

ありがとうございました！

私が使用しているブルートフォースアプローチの詳細は、興味があるか有用な場合にのみ:

上記でリンクした既存のソース コードには、すべての最大適合をキャプチャできるパスをたどるのではなく、アルゴリズムが 1つの最大適合を選択するという事実に関与する 1 行のコードがあります。 ここをクリックして、そのコード行を確認してください。 ここにあります：

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

>(大なり記号)に注意してください。このコード行は、特定のサブ問題の他の間隔の組み合わせよりも高い合計重みを持つ間隔の組み合わせが保持されることを正常に保証します。に変更>すること>=で、検討中の現在の間隔セットの合計重みが以前の最大の合計重みと等しいシナリオをキャプチャできます。これにより、すべての最大適合をキャプチャできるようになります。このシナリオを捉えたいので、私の C++ 移行では を使用し、>=等号が成り立つ場合は、再帰的な関数呼び出しを介してフォーク内の両方のパスを進みます。

以下は、サブ問題ごとにすべての最適な間隔セット (および重み)を取得する (重要な) 関数の C++ コードです (サブ問題が問題全体に対応する最後のインデックスで最終的な解が得られることに注意してください)。

はすべての潜在的な解 (最大間隔セット)の でOPTsあることに注意してくださいlist(つまり、 の各要素自体が、間隔のセットとすべての副問題の対応する重みでOPTs構成されるすべての副問題の単一の完全な解です) 。単一のそのような完全なソリューションを記述するために使用されます - それを構築するために使用されるすべての間隔での潜在的な最大適合、各サブ問題に対して1つ。OPT

上で示した重み付きインターバル スケジューリング問題の標準的な解決策の場合、得られる解決策はOPT(リストではなく 1 つのみ) だけです。

以下のコードのRangeElement型は、私が議論している問題とは関係のない単純なメタデータです。

RangesVec問題への入力である間隔のセットが含まれています (終了値で適切にソートされています)。 上記のリンクで説明されているPreviousIntervalVecものに対応します。compute_previous_intervals

(注: 上にリンクされた Python コードを見ている人は、最大セットで間隔を保存することに関連するバグを見つけたと思うことに注意してください。このバグに関するコメントについては、こちらを参照してください。以下の私の C++ コードで修正されました。)

これは、すべての最大適合をキャプチャする私の「ブルートフォース」実装です。 私のブルート フォース アプローチは、最後に削除する必要があるいくつかの誤検知もキャプチャします。誤検知を除外するための最も効率的なアプローチを提供するが、それ以外の場合は以下のアルゴリズムと同等のアルゴリズムを使用する回答に満足します。

void CalculateOPTs(std::vector<std::pair<INDEX_TYPE, std::vector<RangeElement const *>>> & 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 && 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;
        }

    }
}
4

1 に答える 1

0

等しい重みの最適なサブソリューションがある場合、すべてのサブソリューションに次の間隔を追加する必要がありますが、これが起こっているとは思いません。一般的なフォームは次のようになります

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
}
于 2014-06-26T16:42:48.937 に答える