寻找最佳可用时间的算法

Question

这是我的设想，

我经营按摩的地方，提供各种类型的按摩。比方说30分钟按摩，45分钟按摩，1小时按摩等。我有50间客房，100名员工和30件equipment.When客户预约按摩预约，预约需要1间房、1名员工和1件设备。

在给定的一天内，为10位客人找到可用资源的好算法是什么？

资源

房间- 50

工作人员- 100

设备- 30

营业时间:上午九时至下午六时

工作时间:上午九时至下午六时

没有客人: 10

服务

5位客人- (1小时按摩)

3位客人-(45分钟按摩)

2名客人- (1小时按摩)。

他们同时来了。假设那天没有其他约会

获得以下信息的最佳方法是：

• 前10名结果--满足所有条件的最快搜索将获得前10名的结果集。前十位是根据最早的可用时间来定义的。上午9点11分是最佳结果集。不是指good.
• Exhaustive搜索(查找所有组合)-所有集合-所有可能的combination
• First可用配置(只返回第一次匹配)-在满足

的条件下停止搜索。

我很感谢你的帮助。

谢谢尼克

Answer 1

首先，员工、房间和设备的数量似乎无关紧要。似乎你只关心哪一个是最低的数字。那是你的存货。所以在你的例子中，存货= 30。

接下来，听起来你可以在工作的第一个小时内同时为10个人提供服务。事实上，你可以同时为30个人提供服务。

所以，不需要任何算法来解决这个问题，这是一个静态的解决方案。如果你采纳了“马里奥勺子”的建议，并将不同的持续时间按摩与其相应的利润进行加权，那么当你一次有超过30个客户时，你就可以开始优化了。

Answer 2

看起来你正在试图解决一个问题，其中有相当专门的软件应用程序。如果你的问题足够小，你可以尝试使用一些循环和回溯的蛮力方法，但一旦问题变得太大，它将花费太多的时间来迭代所有的可能性。

如果问题开始变得更严重，请寻找更专业的软件。需要寻找的是“基于约束的优化”和“约束规划”。

例如，ECLIPSe工具是一个开源的约束编程环境。您可以在http://eclipseclp.org/examples/index.html上找到一些示例。一个很好的例子就是SEND+MORE=MONEY问题。在这个问题中，您有以下等式：

    S E N D
+   M O R E
-----------
= M O N E Y

用一个数字替换每一个字母，这样和是正确的。这也说明了，尽管你可以解决这个蛮力，但有更聪明的方法来解决这个问题(参见http://eclipseclp.org/examples/sendmore.pl.txt)。

Answer 3

这只是一个寻找解决方案的想法：

您可能想用约束满意问题(CSP)算法来解决这个问题。这是一些人做的，如果他们必须解决时间表的问题，在一般(例如，在大学的房间预订)。

有几个技巧可以提高CSP的性能，比如前向检查，建立DAG，然后进行拓扑排序等等。

只要让我知道，如果你需要更多关于CSP的信息:)