活動選択問題

アクティビティ選択問題 は、開始時刻 (s _i ) と終了時刻 (f _{i ) でマークされた}一連のアクティビティが与えられた場合に、指定された時間枠内で実行する競合しないアクティビティを選択する組み合わせ最適化問題です。問題は、人が一度に作業できるアクティビティは 1 つだけであると仮定して、 1 人の人間または1 台のマシンで実行できるアクティビティの最大数を選択することです。アクティビティ選択問題は、より一般的な間隔スケジューリング問題の特殊なタイプである間隔スケジューリング最大化問題 (ISMP)としても知られています。

この問題の典型的な応用例は、それぞれ独自の時間要件 (開始時間と終了時間) を持つ複数の競合するイベントのために部屋をスケジュールすることですが、オペレーションズ リサーチの枠組みではさらに多くの問題が生じます。

開始時刻s _iと終了時刻f _iで表されるn個のアクティビティが存在すると仮定します。s _i ≥ f _jまたはs _j ≥ f _iの場合、2 つのアクティビティiとj は競合しないと言われます。 アクティビティ選択問題は、競合しないアクティビティの最大ソリューション セット (S) を見つけることです。より正確には、複数の最大ソリューションが同じサイズである場合、|S'| > |S| となる ソリューション セットS'は存在しません。

アクティビティ選択問題では、貪欲アルゴリズムを使用して解決策を見つけると、常に最適な解決策が得られるという点が注目に値します。アルゴリズムの反復バージョンの疑似コードスケッチと、その結果の最適性の証明を以下に示します。

貪欲反復アクティビティセレクター（A 、s 、f ）：​​​   

    fに保存されている終了時間でAをソートする       
    S = { A [ 1 ]}   
    1 = 1です  
    
    n = A .長さ  
    
    i = 2からnの場合:     
        s [ i ] ≥ f [ k ]の場合:    
            S = S U { A [ i ]}    
            k =私  
    
    リターンS 

1 行目:このアルゴリズムは、まず貪欲アルゴリズムであり、反復的であるため、 Greedy-Iterative-Activity-Selectorと呼ばれます。この貪欲アルゴリズムの再帰バージョンもあります。

• ${\displaystyle A}$アクティビティを含む配列です。
• ${\displaystyle s}$は、 内のアクティビティの開始時刻を含む配列です。${\displaystyle A}$
• ${\displaystyle f}$は、 内のアクティビティの終了時刻 を含む配列です。${\displaystyle A}$

これらの配列は、1 から対応する配列の長さまでインデックスが付けられることに注意してください。

3 行目:配列に格納されている終了時間を使用して、アクティビティの配列を終了時間の昇順でソートします。この操作は、マージ ソート、ヒープ ソート、クイック ソートなどのアルゴリズムを使用して時間 内に実行できます。${\displaystyle A}$${\displaystyle f}$${\displaystyle O(n\cdot \log n)}$

4 行目:選択したアクティビティを格納するセットを作成し、終了時間が最も早いアクティビティで初期化します。 ${\displaystyle S}$${\displaystyle A[1]}$

5 行目:最後に選択されたアクティビティのインデックスを追跡する 変数を作成します。${\displaystyle k}$

9 行目:配列の 2 番目の要素から最後の要素まで反復処理を開始します。 ${\displaystyle A}$

10 行目、11 行目:アクティビティ ( )の開始時刻が 最後に選択されたアクティビティ( )の終了時刻以上である場合、 はセット 内の選択されたアクティビティと互換性があり、 に追加できます。 ${\displaystyle s[i]}$${\displaystyle ith}$${\displaystyle A[i]}$ ${\displaystyle f[k]}$${\displaystyle A[k]}$${\displaystyle A[i]}$${\displaystyle S}$${\displaystyle S}$

12 行目:最後に選択されたアクティビティのインデックスが、追加されたばかりのアクティビティに更新されます。 ${\displaystyle A[i]}$

を終了時間順に並べたアクティビティの集合とします。 が最適解であり、これも終了時間順に並べられているとします。また、 Aの最初のアクティビティのインデックスが であるとします。つまり、この最適解は貪欲な選択から始まっていません。貪欲な選択 (アクティビティ 1) から始まる は、もう 1 つの最適解であることを示します。 、および A のアクティビティは定義により互いに素であるため、B のアクティビティも互いに素です。B にはAと同じ数のアクティビティ、つまり があるため、Bも最適です。 ${\displaystyle S=\{1,2,\ldots ,n\}}$${\displaystyle A\subseteq S}$${\displaystyle k\neq 1}$${\displaystyle B=(A\setminus \{k\})\cup \{1\}}$${\displaystyle f_{1}\leq f_{k}}$${\displaystyle |A|=|B|}$

貪欲な選択が行われると、問題はサブ問題の最適解を見つけることに集約されます。A が貪欲な選択を含む元の問題Sの最適解である場合、 はアクティビティ選択問題 の最適解です。 ${\displaystyle A^{\prime }=A\setminus \{1\}}$${\displaystyle S'=\{i\in S:s_{i}\geq f_{1}\}}$

なぜでしょうか? そうでない場合は、S ′の貪欲な選択を含むA ′よりも多くのアクティビティを持つS ′へのソリューションB ′ を選択します。次に、B ′ に 1 を追加すると、 Aよりも多くのアクティビティを持つSへの実行可能なソリューションBが生成され、最適性と矛盾します。

活動選択問題の一般化バージョンでは、合計重みが最大になるように、重複しない活動の最適なセットを選択することが含まれます。重み付けされていないバージョンとは異なり、重み付けされた活動選択問題には貪欲な解決策はありません。ただし、次のアプローチを使用して動的プログラミングソリューションを簡単に作成できます。^[1]

アクティビティk を含む最適解を考えてみましょう。これで、 kの左側と右側に重複しないアクティビティができました。最適なサブ構造のため、これら 2 つのセットの解を再帰的に見つけることができます。 k は不明なので、各アクティビティを試すことができます。このアプローチにより、解が得られます。 内のアクティビティの各セットについて、 の解がわかっていれば最適解を見つけることができることを考慮すると、これはさらに最適化できます。ここで、t は内でj を含む最後の重複しない間隔です。これにより、解が得られます。これは、すべての範囲を考慮する必要はなく、 だけを考慮する必要があることを考慮すると、さらに最適化できます。したがって、次のアルゴリズムにより、解が得られます。 ${\displaystyle O(n^{3})}$${\displaystyle (i,j)}$${\displaystyle (i,t)}$${\displaystyle (i,j)}$${\displaystyle O(n^{2})}$${\displaystyle (i,j)}$${\displaystyle (1,j)}$${\displaystyle O(n\log n)}$

重み付けアクティビティ選択( S ) : // S =アクティビティのリスト  

    終了時間順にSを並び替え    
    opt [ 0 ] = 0 // opt[j]はS[1,2..,j]の最適解（選択されたアクティビティの重みの合計）を表す    
   
    i = 1からnまでの場合:     
        t =終了時刻<=開始時刻のアクティビティをiに対して検索するバイナリ検索              
            // そのようなアクティビティが複数ある場合は、最終終了時刻が最新のアクティビティを選択します
        opt [ i ] = MAX ( opt [ i -1 ], opt [ t ] + w ( i ))     
        
    リターンオプト[ n ] 

• 活動選択問題