1

これは、そこにいるアルゴリズムの達人への質問です:-)

Sを重なる可能性のある自然数の間隔の集合とボックスbサイズとする。各間隔で、範囲が厳密に 未満であると仮定しますb。

サイズの間隔の最小セットを見つけたいb( と呼びましょうM) のすべての間隔が の間隔にS含まれるようにしますM。

些細な例:

S = {[1..4], [2..7], [3..5], [8..15], [9..13]}
b = 10
M = {[1..10], [8..18]}
// so ([1..4], [2..7], [3..5]) are inside [1..10] and ([8..15], [9..13]) are inside [8..18]

貪欲なアルゴリズムは常に機能するとは限らないと思うので、誰かがこの問題の解決策 (または変換できる同様の問題) を知っていれば、それは素晴らしいことです.

ありがとう！

更新私はそれについてもう少し考えてきました.おそらく私の最初の直感は間違っていました.貪欲なアルゴリズムはこれを解決する方法です.最終的にはすべての間隔をカバーする必要があり、それは何もしませんスーパーインターバルの選択方法の違い...質問を削除する必要がありますか、それとも誰かがこれを主張できますか?

4

2 に答える 2

4

アルゴリズムは次のようになります。

  1. a = 0
  2. curr = > a である S の最小数。(私たちの場合 = [1..4] の 1.)
  3. 間隔 [curr..b] を M に追加します (この場合、M = {[1..10]} )。
  4. a = M の最大上限 (この場合は a = 10 )
  5. 2へ。
于 2010-03-22T16:15:42.663 に答える
3

はい、貪欲なアルゴリズムが最適です。非公式に、任意の解 M を考えます。区間数を増やさずに、貪欲な解 M' のスーパーセットに変換します。M - M' の一番左の間隔 I を繰り返し検討します。I が s を含む M の左端の区間である S の左端の区間を s とします。左から右への貪欲なアルゴリズムは、左端が s と整列する間隔 I' を選択します。I' は s を含む最も右の間隔であるため、最初に I' が I の右側にあると主張し、次に M - {I} U {I'} が有効な解であると主張します。しかし I' は s の左側にあるわけではないので、すでに他の間隔に含まれています。貪欲な解にない区間の数が減少するため、最終的に貪欲な解に到達します。

于 2010-03-22T16:42:24.857 に答える