2

この問題を解決するために思いついた欲張りアルゴリズムに欠陥や問題が見られるかどうか疑問に思っていました。問題は：

  • 彼らは一組の従業員です
  • 各従業員には、1週間の1つの時間間隔である1つの勤務シフトがあります。従業員のシフトは重複する可能性があります。
  • 従業員のサブセットが監督グループを形成します。
  • 監督グループには、すべての従業員のシフトのあらゆる瞬間に、上司も働いているという特性があります。

目標は、可能な限り小さいサイズの監督グループを作成することです。

さて、これを解決するための欲張りアルゴリズム。従業員のリストがあると仮定します。

  While(there are employee's who aren't supervisors and are not removed )
      Choose first employee working with longest work shift to be supervisor. 
      Remove any employee whos finish time is less than the current supervisor finish time.

      If(supervisor shift is ending)
         Turn employee whos shift interests with supervisor shift,
         with longest work time remaining into a supervisor as well.
      end if
  End while

      return list of supervisors

これは機能しますか？そして、これは実際に可能な限り最小の監督者グループを返すのでしょうか？これがこれを行うための最良の方法であるかどうかはわかりません。

ありがとう

4

1 に答える 1

3

各従業員が正確に 1 つのシフトで働いているため、貪欲な戦略が最適なソリューションを生み出すことを証明するのは簡単です。

アルゴリズムが最適な解を生成しないことにしましょう。E0これは、少なくとも 2 人の従業員を置き換えることができ、E12E2回連続して監督者を割り当てられた従業員が存在することを意味します。これは、E0のシフトが少なくともE1s と同じくらい早く開始され、遅くまたはそれ以降に終了したことを意味しE2ます。しかし、それが本当なら、あなたの貪欲なアルゴリズムはスーパーバイザーになることを選んE0だでしょうE1。これは矛盾しています。これは、アルゴリズムが問題の最適解を見つけることを意味します。

于 2013-02-19T03:24:42.327 に答える