Nik*_* B. 13 algorithm graph game-theory bipartite
我在编程竞赛(安德鲁·斯坦克维奇竞赛21)中遇到一个关于如下游戏的问题时遇到了困难:
尼克和彼得喜欢玩以下游戏[...].他们在一张纸上绘制一个无向二分图G,并将一个标记放在其顶点之一上.之后他们轮流行动.尼克先行动.
移动包括沿着图形边缘移动令牌.之后,在移动之前令牌所在的顶点以及与其相关的所有边缘都将从图形中移除.没有有效动作的玩家输掉游戏.
给出了图表,现在的任务是找到给定的起始节点,如果两个玩家都以最佳方式玩,则起始玩家是赢还是输.总结一下
由于图表是二分图,Nick(第一个玩家)将始终从左侧移除一个节点,Peter将始终从右侧移除一个节点.
图表最多可以有1000个节点(最多500每侧)和50000个边缘,所以需要一个很好的多项式时间算法(这里的时间限制为2秒解决所有首发位置,但我认为我们可以分享很多不同起始位置之间的信息).
我很确定这可以简化为某种顶点覆盖或打包问题,因为图是二分的,但我找不到与这些相关的策略.
我知道一个特殊情况的解决方案:假设两侧分别有n 1和n 2个顶点.如果匹配大小为min(n 1,n 2)并且如果较小侧的玩家开始,则存在获胜策略:他只需跟随匹配的边缘并自动获胜.
有任何想法吗？
主张.v如果此顶点属于给定图形的每个可能的最大匹配,则Nick(第一个玩家)从顶点开始获胜.我们将分两步证明这一点.
如果没有最大匹配v,尼克输了.
实际上,由于匹配是最大的,因此没有增强路径v.这意味着每个简单的奇数路径v都可以通过匹配的边缘延长.就我们的问题而言,这意味着每次尼克的举动后,彼得都可以继续比赛.
如果没有最大匹配v,尼克赢了.
考虑任何可能的最大匹配.沿着此匹配的边缘移动v到比方说u.现在,初始匹配减去边缘u-v是剩余图形的最大匹配,不包括u.正如我们从第1步所知,现在移动的玩家(这是彼得)是亏本的.
至于实现,我们可以首先利用简单的算法在O(VE)中构造最大匹配(参见这里的示例实现) - 结果通用名称是Kuhn的扩充路径算法.
之后,您将保持最大匹配并查看每个顶点.如果顶点,例如v,当前不在匹配中,尼克会失败.如果是,v-u则从匹配中移除相应的边缘,v暂时禁止顶点并从uO(E)中搜索扩充路径.如果你没有找到这样的路径,尼克会赢,你必须恢复你删除的边缘.否则,尼克再次失败,新的最大匹配可以保持不变.总运行时间再次为O(VE).