2

我只是想知道您是否可以看到我为解决此问题而提出的贪婪算法的任何缺陷或问题。问题是：

  • 他们是一组员工
  • 每个员工都有一个工作班次，这是一周中的一个时间间隔。员工的轮班有重叠的可能性。
  • 一部分员工组成一个监督组。
  • 监督组有一个属性，即在每个员工轮班的每一刻，都有一名主管在工作。

目标是产生一个规模尽可能小的监督组。

现在，我的贪心算法来解决这个问题。假设有一个员工列表：

  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

由于每个员工正好轮班工作，很容易证明贪婪策略会产生最佳解决方案。

让我们假设您的算法没有产生最佳解决方案。这意味着存在一名员工E0可以替换至少两名员工E1，并E2在两个背靠背的时间间隔内被指派主管。这意味着E0' 的转变至少早在E1s 开始，并在 s 之后或更晚才结束E2。E0然而，如果这是真的，那么你的贪心算法就会被选为E1监督者，这是一个矛盾。这意味着您的算法找到了问题的最佳解决方案。

于 2013-02-19T03:24:42.327 回答