12

区間（a、b）と、和集合がすべて（a、b ）であるいくつかの部分区間{（a i、b i）} iがあるとします。（a、b）をカバーするこれらのサブインターバルの最小カーディナリティサブセットを選択する効率的な方法はありますか？

4

4 に答える 4

15

a または b から始まる貪欲なアルゴリズムは、常に最適解を与えます。

証明: aをカバーするすべての部分区間の集合 S aを考えます。明らかに、そのうちの 1 つが最適解に属している必要があります。それを S a のサブインターバル (a max ,b max )で置き換えた場合、右端点 b maxが S a で最大になる(右端に達する) と、カバーされていない残りのインターバル (b max ,b) は次のサブセットになります。最適解からの残りの間隔であるため、最適解からの類似のカバーされていない間隔よりも多くのサブ間隔でカバーすることはできません。したがって、(a max ,b max ) と残りの区間の最適解 ( b max ) から構成される解、b) も最適になります。

したがって、a から始めて、最も右側に到達する (そして前の間隔の終わりをカバーする) 間隔を繰り返し選択し、b に到達するまで繰り返します。間隔を拡張間隔ツリーに保存すると、次の間隔の選択は log(n) で実行できると思います。

于 2008-11-16T21:27:16.137 に答える
1

動的計画法のように聞こえます。

アルゴリズムの図を次に示します (間隔が終了時刻でソートされたリストにあると仮定します)。

//works backwards from the end
int minCard(int current, int must_end_after)
{
    if (current < 0)
        if (must_end_after == 0)
            return 0; //no more intervals needed
        else
            return infinity; //doesn't cover (a,b)

    if (intervals[current].end < must_end_after)
        return infinity; //doesn't cover (a,b)

    return min( 1 + minCard(current - 1, intervals[current].start),
                minCard(current - 1, must_end_after) );
           //include current interval or not?
}

ただし、キャッシング（メモ化）も必要です。

于 2008-11-15T22:53:50.597 に答える
0

考慮すべき 2 つのケースがあります。
ケース 1: インターバルの終了時刻の後に重複するインターバルがない。この場合、開始時刻が最も短く、終了時刻が最も長い次のインターバルを選択します。（アミン、bmax）。
ケース 2: 表示している最後の間隔と重複する 1 つ以上の間隔があります。この場合、開始時間は問題ではありません。そのため、仕上げ時間を最適化します。(a、bmax)。

ケース 1 では、常に最初の間隔が最適なセットの最初の間隔として選択されます (証明は @RafalDowgrid が提供したものと同じです)。

于 2012-04-05T18:00:47.907 に答える
-2

(a,b) がすべてのポイントで完全にカバーされたままになるように、サブインターバルがまだ重複していることを意味しますか?

おそらく、サブインターバル自体を、それらがどこから来たのかに関連付けられた基本ブロックに分割するので、サブインターバルでカバーされる他の領域を考慮して、各基本ブロックインターバルのオプションをリストできます。次に、各サブサブインターバルに基づいて検索を使用し、少なくともギャップが残っていないことを確認できます。
次に、検索する必要があります..効率的に..それは難しいでしょう。

より小さな数の別のセットによって完全にカバーされている間隔のコレクションを排除し、前処理後に問題を解決できます。
全体の最小は、少なくとも半分の最小ではないでしょうか? わからない。

日誌へのリンクが見つかりましたが、読むことができませんでした。:(

これはヒッティング セットの問題であり、一般的に NP_hard です。これ
も 読めませんでしたが、逆の種類の問題のようです。 それを読むことができませんでしたが、間隔の分割について言及している別のリンクです。これは、幾何学的最適化問題のランダム化アルゴリズムに関する利用可能なリファレンスです。このpdfの35 ページには貪欲なアルゴリズムがあります。Karp (1972) の 11 ページは、ヒッティング セットについて言及しており、多く引用されています。 Googleの結果. 研究は楽しかったが、もう行かなければならない。




于 2008-11-16T00:09:29.570 に答える