逻辑游戏:最大化(或最小化)两个代理人见面的机会

Question

注意:这个问题被标记为语言无关和python,因为我主要关心的是找到实现问题解决方案的算法,但有关如何在python中有效实现它(=快速执行!)的信息是一个加号.

游戏规则:

• 想象一下两个团队中的一个A代理(An)和一个B代理(Bn).
• 在游戏空间中,可以占用一定数量的可用插槽(Sn).
• 在每个转弯处,每个代理被给予他/她可以占用的一部分时隙.
• 一个代理程序一次只能占用一个插槽,但每个插槽可以由两个不同的代理程序占用,前提是它们各自来自不同的团队.

问题:

我试图找到一个高效的方式来计算可能的最佳移动为A代理商,其中"最佳移动"意味着要么最大化或最小化占用的球队住在同一插槽的机会B.团队的行动B事先不知道.

示例场景:

这种情况故意是微不足道的.它只是为了说明游戏机制.

A1 can occupy S1, S2
A2 can occupy S2, S3
B1 can occupy S1, S2

在这种情况下,解决方案是显而易见的:A1 ? S1并且A2 ? S2是保证满足B1[ B1无法避免占用任何一个S1或S2]的选项,A2 ? S3而且A1 ? random(S1, S2)是最大化避免机会的选项B1.

现实场景:

在现实生活场景中,插槽可以是数百个,每个团队中的代理可以是几十个.到目前为止我尝试的天真实施的难点在于我基本上考虑了团队的每一个可能的移动集合B,并为每个可能的替代移动集合评分A.所以,我的计算时间呈指数增长.

不过,我不确定这是一个只能通过"蛮力"解决的问题.即使是这种情况我也不知道:

1. 如果最佳蛮力解决方案必然呈指数增长(按时间).
2. 如果有办法计算非最佳的,本地最佳的解决方案.

谢谢!

Answer 1

两个团队的成员和插槽定义了一个三方图A-S-B,边缘由可能的移动给出.由一个小组的成员和成员组成的二分子图是有意义的; 将这些A-S用于团队A成员和S-B团队B成员的图表.您可以使用S-B图表为插槽分配值,然后使用S-A图表选择最大化或最小化团队A值的移动.

对时隙值的适当选择是在该时隙中找到B队成员的可能性.这样,团队A的一组移动的值是时隙值的总和,即,将找到团队B成员的预期时隙数.请注意,团队成员的行动并不是独立的,因此这两个阶段都存在一些挑战.

给定插槽的值,为团队A选择移动成为标准问题:分配问题.这与missno的答案中建议的最大二分匹配有关,但需要考虑时隙的值; 边缘的权重可以等于边缘入射的槽的值,最大加权的二分匹配等同于分配问题.使用标准算法来解决(或近似)问题的这一部分.

那么我们如何为插槽分配值？我建议只为团队B的成员生成随机移动,计算插槽的占用频率,并将计数除以您考虑的样本移动次数.从生成一组随机动作的难度来看,这一点并不十分清楚; 假设每个团队成员都可以选择留在原地,只需随机选择每个成员的移动即可.

两个阶段的简化因素是有一种简单的方法将问题分解为独立的子问题.二分图的连通组件显示哪些团队成员可以以干扰其他人的方式移动,例如,如果团队成员在董事会的不同部分被分成两组,则可以独立对待这些组.这适用于两个阶段,包括使用S-B图形概率性地评估槽并优化图中的分配A-S.当然,如果任何组件足够小,您可以始终枚举可能性并完全解决子问题.