逻辑博弈:最大化(或最小化)两个代理人相遇的机会

Question

language-agnostic和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与团队成员一起调用为图，为B组成员调用S-B。您可以使用S-B图将值赋值给插槽，然后使用S-A图来选择使A组的值最大化或最小化的移动。

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

给定插槽的值，选择A组的移动成为一个标准问题：赋值问题。这与漏报的答案中建议的最大二部匹配有关，但需要考虑槽的值；边可以被赋予的权重等于边缘入射的时隙的值，最大加权二部匹配等价于分配问题。使用标准算法来解决(或近似)这部分问题。

那么，我们如何为插槽分配值呢？我建议只为B组的成员生成随机的移动，计算占空时间的频率，并将计数除以您考虑的示例移动数。从问题中还不清楚产生一组随机的移动会有多难；假设每个团队成员都可以选择留在原地，那么通过随机顺序为每个成员随机选择移动是很容易的。

两个阶段的一个简化因素是，有一种简单的方法可以将问题分解为独立的子问题。二部图的连通部分显示哪些团队成员可以以干扰其他成员的方式移动，例如，如果团队成员在董事会的不同部分被分成两组，那么组可以被独立处理。这在两个阶段都适用，既可以用S-B图对槽进行概率计算，也可以优化A-S图中的分配。当然，如果任何组件都足够小，则始终可以枚举各种可能性并精确地解决子问题。

Answer 2

这是一种蛮力解决方案，但可能不如列举所有可能性的明显办法那么残忍。正如其他解决方案所指出的，这个问题与二部图上的二部图有关。

步骤1:计算每个站点被 B 占用的概率

构造如下二部图。顶点是B代理B1,B2,...,BK和站点S1,S2,...,SN，如果agent Bi可以占据站点Sj，则在Bi和Sj之间有一个边缘。在这个图上找到所有的最大匹配(或者最大匹配，如果这是B代理的算法)，比如有它们的M。对于每个站点Si，B代理占用站点的概率为

Pi = #(matchings using Si) / M

需要考虑的算法：

• Hopcroft-Karp算法

步骤2:为 A agents寻找最高权重匹配

构造下面的边加权二分图。顶点是A代理A1,A2,...,AL和站点S1,S2,...,SN，如果agent Ai可以占据站点Sj，并且该边缘具有权重Pi，则在Ai和Sj之间存在一个边缘。找到最大或最小权重的最大匹配。

需要考虑的算法：

• Bellman算法
• 迪克斯特拉算法
• 斐波纳契堆
• 匈牙利算法

现在，这不过是对问题的重申，但或许以这种方式思考它将导致一种不那么野蛮的蛮力方法。例如，一旦完成了第1步，您就可以采取贪婪的算法，通过包含那些概率最高/最低的Si来为A代理选择一个游戏。虽然找到匹配可能很困难，但是知道是否存在匹配是不存在的。一旦您选择了最可能/最不可能的霍尔婚姻定理，就可以使用Si来确定是否存在完美的匹配。

Answer 3

如果我理解正确的话，当你知道B的位置时，找到A的最优策略的问题和在二分图中找到最大匹配是一样的。

第一组顶点表示A代理，第二组顶点表示B代理捕获的槽，如果代理可以选择占据时隙，则存在边。

问题是找出最大数目的边，你可以不接触多个顶点，超过一个边。

有一些简单的多项式算法来解决这个问题。其中最经典的是基于增强路径的。

while you can find a path, augment the path

a path is a sequence of vertices a1, b1, a2, b2, ... an, bn such that
  ai -> bi is an unmatched edge
  bi -> a(i+1) is a matched edge
  a1 and bn are unmatched

to augment a path
  match all the unmatched edges (ai -> bi)
  unmatch all the matched edges (bi -> a(i+1))
  (this results in one aditional matched edge after the iteration)

这个算法的一个简单的实现是O(V*E)，但是您可能会在某个地方找到更高效的python实现。