2

背景故事

事情就是这样。我住在三口之家，我们中的老大已经厌倦了一个人做所有的家务。我们尝试为任务制定不同的时间表，但总是会出现问题，因为我们中的一个人不在家，家务活没有完成，或者有人觉得他们比其他人做的工作更多，导致怨恨和不愿意完成家务活。

问题

人类会犯错，但计算机程序是万无一失的，对吧？这个想法是，可以使用计算机程序公平地分配要完成的家务，这样没有人会觉得他或她正在做更多的工作。我正在尝试提出一种算法来分配符合这些标准的家务：

  • 从长远来看，它应该以大约 1/3 的概率平均分配家务。
  • 它应该返回一个有序的人员列表，所以如果第一个不可用，第二个可以完成它。
  • 它应该避免在同一天为每个人安排多项家务。
  • 它应该避免连续多次将相同的家务安排给同一个人。
  • 它应该是容忍偏差的。如果安排的人没有做家务，只要反馈实际做家务的人，它应该仍然是公平的。
  • 它应该以不同的频率处理不同的家务（你需要每天洗碗，但每周只打扫一次浴室，......）

我的问题是：实现此算法的最佳/最酷/最公平的方法是什么？ （非常可笑的过于复杂的解决方案受到赞赏：D）

我尝试了什么？

我认为实现这种算法的一种简单方法是为不同的标准定义一个成本表，然后只使用加权随机数来选择这个人，但我认为这从长远来看是不公平的（它确实必须限制每人 1/3，否则将不被接受:))。

4

3 回答 3

1

您的问题由两部分组成：

1)定义评分函数。你如何定义公平、高效……？他们之间的取舍是什么？有不同的技术可以进行权衡：

  • 得分权重，例如：1次（分布不均）== 5次（一天多活）
  • 分数水平，例如：（分布不均匀）总是高于（一天中的多项家务）
  • 帕累托评分：见维基百科

2）使用优化算法找到得分最高的时间表（在所有可能的时间表中）。如果您的问题是 NP 完全的，那么就没有这样完美的算法。但也有非常好的。我更喜欢从First Fit Decreasing开始，然后是Tabu Search。

有关具有实现代码的类似示例的完整详细概述，请遵循本教程。Computer在心里用Person和替换这个词Process。Chore

于 2012-07-13T08:40:15.493 回答
1

您可以尝试某种“有趣的货币”经济，以信用或奢侈品的价格和工资，而不是真正的货币，希望出现一个有效的市场并提供最佳解决方案。

如果您真的想要一些复杂的东西，请考虑Vickrey-Clarke-Groves 拍卖中的 Clarke Pivot 规则。在这里做或不做家务，或一批家务，是一个可能的结果。你应该会发现，组织拍卖的银行利润微薄，当积累足够多时，它可以作为节日重新分配给所有人。

于 2012-07-12T18:59:50.847 回答
1

一般来说，您的约束似乎足够松散，并且您的算法不需要扩展太多，因此您应该能够制定一个算法来强制计划满足您的所有标准，并且有一个吨不同的方式来实现它。以下是一些可能有助于您入门的随机沉思。

假设我有一个要为给定日期分配的家务清单（但这应该适用于任何时间段）。每件家务都有一个重量（人们认为它有多艰巨或需要多长时间等等）。每个家务都有一个名称或者是某个类的一个实例（这样我们就可以知道两次浴室清洁是同一个家务，我们不太可能将它分配给同一个人两次）。我也有一份过去人们做过的所有家务的清单（包括谁实际做过这些家务，而不仅仅是分配给谁）。

如果你想以 1/3 的概率分配家务，一个简单的方法是这样说：

while has_more_chores()
  randomize the order of the persons list
  foreach person:
    if (has_more_chores()):
      person.assign_chore()

这基本上保证了每个人都做了和其他人一样多的家务。但是，这不会考虑重量。如果重量很重要，那么这样做可能更有意义

foreach chore:
  chore.choose_person()

无论您是在做 person.assign_chore() 还是 chore.choose_person()，您都需要应用某种平衡功能，这样一个人就不会一直打扫浴室。您可以使用修改后的指数退避来减少在完成一堆家务后获得家务的可能性。

也许解决这个问题的一种更简单的方法是随机生成无数个不同的人事时间表，并取消任何不符合您的限制的人的资格（即，一个人连续多次做同样的家务，或者一个人做多项家务）一天）。

于 2012-07-11T17:07:52.390 回答