选择最佳组合

Question

我有一个问题，我目前正在通过暴力解决，但我正在寻找一个更优雅的解决方案。我有一个跨多个节点运行各种功能的系统。每个函数都由一个“角色”定义。可以将每个“角色”定义为允许一个或多个客户端持有它。另外，可以优先于特定客户端(或多个客户端)而不是其他客户端。

复杂性在于，“角色”也有可能相互关联。例如，客户端可能只能在不持有“RoleB”的情况下持有“RoleA”，或者在持有“RoleC”的情况下只能持有“RoleD”。此外，角色可以优先相关(即，最好是持有'RoleE‘的客户端持有'RoleF'，但这不是强制性的)。

客户可以宣传其愿意担任任何数量的角色，但不是必须这样做。即'client1‘可以通告角色'A’、'B‘和'C'，而'client2’只能通告角色'A‘和'B’。

我已经以蛮力的方式解决了这个问题，但显然，随着相关角色数量的增加，解决它所需的时间会呈指数级增长。

目前，我的算法是:为广告给定角色的客户找出所有可能的组合，然后单独评估该角色，以生成按偏好排序的合法组合列表。

为上一步中生成的列表生成所有可能的组合，并迭代这些组合，根据角色组的强制关系、非法关系、偏爱关系和不偏爱关系，基于启发式确定哪个是最优的。这是随着相关角色数量的增加而呈指数级增长的部分。

我已经尝试了一些“早期”的方法，根据角色关系来确定理论上可能的最大“分数”，一旦我们遇到一个“分数”>= this的组合，我们就会停止处理，但我想知道是否有更数学的解决方案。任何解决方案都可能是最佳组合的近似值，但这很好。

理想情况下，我需要一些可以运行亚秒级的东西。

希望我的解释不会太含糊，有人能给我指明正确的方向！提前谢谢。凸轮

Answer 1

听起来像是Boolean satisfiability problem，但有一些额外的复杂性。BSP是一个NP完全问题，因此没有算法可以在少于指数时间内解决它，但是有一些算法(在链接中提到)可以比蛮力更好地解决它。