解决图形游戏
我在编程比赛（Andrew Stankevich Contest 21）的一个问题上挣扎了一段时间，这个比赛如下所示：
尼克和彼得喜欢玩下面的游戏[...]。 他们在一张纸上绘制一张无向二分图G，并将一个标记放置在其顶点之一上。 之后，他们轮流做出动作。 尼克先动。
移动包括沿着图形边缘移动令牌。 在它之后，移动之前令牌所在的顶点以及与之相关的所有边将从图中移除。 没有有效动作的玩家会失去比赛。
给出图表，现在的任务是找到给定的开始节点，如果两个玩家最佳地玩，起始玩家是赢还是输。 总结
由于图形是双向的，因此尼克（第一个玩家）将总是从左侧移除一个节点，彼得总是会从右侧移除一个节点。
该图可以有多达1000个节点（每边最多500个）和50000个边，所以需要一个好的多项式时间算法（这里的时间限制是2秒来解决所有的起始位置，但我认为我们可以分享很多不同起始位置之间的信息）。
我敢肯定，这可以归结为某种顶点覆盖或包装问题，因为图形是双向的，但是我找不到与这些关联的策略。
我知道一个特例的解决方案：假设双方分别有n1和n2个顶点。 如果匹配的大小为min（n1，n2），并且较小一侧的玩家开始比起存在一个获胜策略：他只需要遵循匹配的边缘并自动获胜。
有任何想法吗？
主张。 尼克（第一个球员）从顶点v开始，如果这个顶点属于给定图形的每个可能的最大匹配的话。 我们将分两步证明。
如果没有v情况下有最大匹配，Nick会丢失。
事实上，由于匹配是最大的，所以没有从v增加的路径。 这意味着从v每条简单的奇长路径都可以被匹配的边缘延长。 就我们的问题而言，这意味着在尼克的每一步之后，彼得都可以继续比赛。
如果没有v没有最大匹配，尼克赢。
考虑任何可能的最大匹配。 沿v匹配的边缘从v到u ，比如u 。 现在，初始匹配减去边缘uv是剩余图形的最大匹配，其不包含u 。 正如我们从第一步所知道的那样，现在移动的球员（彼得）不知所措。
至于实现，我们可以首先使用直接算法（参见这里的示例实现）在O（VE）中构造最大匹配 - 证明通用名称是库恩增广路径算法。
之后，您保持最大匹配并查看每个顶点。 如果顶点v （如v ）目前不在匹配中，那么Nick会丢失。 如果是，则从匹配中删除相应的边（比如说vu ，暂时禁止顶点v ，然后在O（E）中从u中搜索增强路径。 如果你没有找到这样的路径，尼克赢了，你必须恢复你删除的边缘。 否则，尼克再次失去，新的最大匹配可以保持不变。 总运行时间再次为O（VE）。
可爱的问题。 我相信预期的解决方案是计算最大匹配，然后确定哪些左顶点属于每个最大匹配。 这是第一名球员的胜利。
获胜策略是选择属于最大匹配的边。 如果开始顶点v属于每个最大匹配，则由玩家1选择的边e的另一个端点w不属于该图的每个最大匹配减v（因为v属于每个最大匹配，最大值的基数删除后匹配减1，所以由于e属于某个最大匹配M，所以M-e在新图中是最大的，并且使e的另一个端点不匹配）。 相反，如果存在v不属于的最大匹配，则其所有邻居w都属于图的所有最大匹配减v（否则，找到没有w的最大匹配并将v从边到w添加边，矛盾当我们删除v时，匹配的最大基数没有减少的假设）。
链接地址: http://www.djcxy.com/p/30703.html上一篇: Solving a graph game
下一篇: winning strategy algorithm for simple game [2 players moving on grid field]