13

我正在解决一个旧的编程竞赛中的一些示例问题。在这个问题中，我们输入了我们有多少调酒师，以及他们知道哪些食谱。每个鸡尾酒的制作时间为 1 分钟，我们需要使用所有调酒师计算订单是否可以在 5 分钟内完成。

解决这个问题的关键是尽可能高效地分配鸡尾酒。这就是我卡住的地方，我当前的算法将订单交给了对其他食谱了解最少的调酒师。但当然，这还不是 100% 正确的。谁能指出我正确的方向（或给我一个算法名称给谷歌）来解决这个“调酒师问题”？

4

4 回答 4

7

这可以通过流网络来解决。

  • 源对每个调酒师都有边，容量为 5。
  • 每个调酒师对他/她可以制作的每种饮料都有优势，容量为 5。
  • 每种饮料都有边缘到水槽，容量与订购的数量相对应。

计算从源到汇的最大流量。如果任何订单仍未完成，则没有解决方案。

于 2013-06-12T15:28:03.140 回答
1

在订单上创建鸡尾酒列表，按知道如何制作鸡尾酒的投标人数量排序

即订单为 (2*CocktailA, 1*CocktailB, 2*CocktailC, 1*CocktailD)

CocktailA 可以由 4 个标书制作（标书 A、B、C、D）
CocktailA 可以由 4 个标书制作（标书 A、B、C、D）
CocktailB 可以由 3 个标书制作（标书 A、B、C）
CocktailC可由 1 份投标 (Tender A)
制作 CocktailC 可由 1 份投标 (Tender A)
制作 CocktailD 可由 1 份投标 (Tender B) 制作

通过该列表向后工作，将工作分配给投标。如果多个投标人可以制作鸡尾酒，则选择已分配工作量最少的投标人。

CocktailD = Tender B
CocktailC = Tender A
CocktailC = Tender A（再次）
CocktailB = Tender C
CocktailA = Tender D
CocktailA = Tender B（再次）

投标人 A 和 B 都有 2 个工作，因此订单需要 2 分钟。

于 2013-06-12T15:22:10.230 回答
1

这是一个顶点着色问题。它完全类似于研究得很好的寄存器分配问题。请参阅http://en.wikipedia.org/wiki/Register_allocation。它也可以被认为是类似于顶点着色的集合覆盖问题。

当然，这里我们不需要找到实际的着色，我们只需要确定它的基数是否为 5 或更少。如果调酒师图表可以用 5 种或更少的颜色着色，那么答案是肯定的，否则不会。这是另一篇很好的论文，用“任务”、“天”和“机器”来描述这个问题：http://www .polymtl.ca/pub/sites/lagrapheur/docs/en/documents/NotesChap7.pdf。

现在，为了弄清楚这一点，图的“色数”或“色指数”是 NP 难的。事实上，有人已经在 SO 上询问了一种算法来查找图的色数，但遗憾的是没有得到太多回应，请参阅Algorithm for Chromatic Number of a Graph？

只是环顾网络，我确实找到了一些用于着色的代码资源。可以解决这个问题的一个叫做SMALLK。SMALLK 最多可以找到 8 种颜色。因为这个问题我们只需要 5 种颜色，这个包就可以做到。

于 2013-06-12T15:35:07.217 回答
0

这是大学匹配问题的一个变体。饮料是学生，调酒师是大学。反过来，它是稳定婚姻问题的概括，可能对你更有用。

于 2013-06-12T15:07:49.920 回答