この問題に可能な貪欲なアルゴリズムはありますか。私はそのための DP アルゴリズムを作成しましたが、貪欲なアルゴリズムについては確信が持てません。貪欲なアルゴリズムが存在するかどうかを説明してください。
問題に精通していない人のために：
a1 から an までの 'n' 個のアクティビティがあります。各活動 ai には、関連する開始時刻 si と終了時刻 fi [si,fi) があります。各アクティビティ ai には、それに関連付けられた値 vi もあります。2 つのアクティビティが同時に発生することはありません。タスクは、相互に互換性のあるアクティビティを選択して、合計値、つまりスケジュールされたすべてのアクティビティの合計を最大化することです。相互に互換性があるとは、実行時間が重複しないことを意味します。
問題の貪欲な解決策を見つけるには、その背後にある直感を見つけなければなりません。この問題は、CLRS のテキストにある活動選択問題の問題 ( ) に似ていますsection 16.1。その問題では、すべてのアクティビティが相互に互換性のある最大サイズのセットを見つける必要があります。しかし、この問題には別の目標があり、カバレッジまたはリソースの使用を最大化するセットを見つける必要があります。
私の意見では、この問題の解決策は、最初にすべてのアクティビティを開始時間に基づいて並べ替えることです。その背後にある直感は、時間/価値/リソースをできるだけ早く使用し、何も無駄にしたくないということです。次に、最も長いアクティビティの選択を開始し、これまでに選択された他のアクティビティと互換性があるかどうかを確認します。そして、あなたは最後まで拾い続けます。これを本の例に適用すると、アクティビティのセットが得られます{3, 7, 11}。
すべての一連のアクティビティに対して正しいとは限りません。たとえば、 と の 2 つのアクティビティのセットactivity(1) = <0, 2>ですactivity(2) = <1, 5>。
ご覧のとおり、この場合、このアイデアは機能しません。したがって、もう一度適用する必要がありますが、右から左に適用します。(終了時間に基づいてそれらを並べ替え、最初に終了し、より長く続いたものを最初に選びます!) 最後に、最もカバレッジの高いセットを選択します!
私はまだ最高の結果を出していないかもしれません。別のアクティビティを追加するactivity(3)=<4, 6>と、それらのアプローチは答えになりません。したがって、アクティビティの長さに基づいて降順にソートすることが答えかもしれません。
最後に、これら 3 つのアプローチのいずれかで答えが得られるはずです。