游戏类的题，每一个玩家都是做optimal move，结果最后是什么。首先我们想到的应该就是minimax tree的思路，我们可以用mouse代表老鼠的位置，cat代表猫的位置，turn代表当前的player(1代表老鼠，2代表猫)，那么可以用(mouse, cat, turn)代表当前的状态，假设输入图总共有n个节点:
- (1, 2, 1)是起始状态
- (0, i, k)是老鼠获胜的状态, 其中1 <= i < n, 1 <= k <= 2
- (i, i, k)是猫获胜的状态，其中1 <= i < n, 1 <= k <= 2
我们只需要从起始开始状态递归即可，每个节点(i, j, k)当前的player都取最优的move:
- 如果某个相邻节点的结果是对手无法获胜，当前player取的肯定是这个move，所以当前状态肯定获胜
- 否则，如果有draw的节点，会取这个move，所以当前节点对应的状态下的结果就是draw
- 如果以上两点都不成立，说明当前节点没有任何一个move可以导致获胜或者平局的结果，所以一定会输
用这种思路我们可以写出DFS的minimax做法，我们需要一个hashset来检测环的存在。但是这种方法在处理较大的数据时会TLE。代码如下：
我们自然会思考可能的优化，比如我们用memorization的思路，对于每一个状态(mouse, cat, turn)我们存下他们对应的结果，这样在之后在到达这个节点的时候直接return即可。代码如下：
这种思路乍看之下没有错，并且可以过绝大部分test case，但是对于一些特殊的test case他会fail，比如对于如下的状态图:
图一
如图一所示，其中每一个节点代表一个状态(mouse, cat, turn)。假设我们从1开始dfs，假设我们先取了1->4->3->2->1这条路径，那么我们就会把2, 3, 4在dfs的时候都在memo里mark成draw，但是事实上他们都应该mark成winning。
换句话说，dfs + memorization在处理cycle的时候会把某些节点错误地mark成draw，然而这些点真实的状态可能是在之后dfs找到的其他状态。
为了解决这个问题，我们可以用BFS从所有确定的状态开始，把每个能够确定状态的节点标记:
- 对于当前节点，假设赢家为winner，我们把相邻的节点turn为winner的节点的赢家也标记成winner
- 对于相邻节点turn不为winner的节点，我们将其degree(邻接节点的数量)减一。当其减为0的时候，代表当前节点任何一个move都是输，我们将赢家标记成对手
整体的思路和上面讲的dfs minimax的思路是类似的。这样我们从一定确定状态的节点开始BFS并且mark所有节点的话，就不会有之前提到的问题。时间复杂度O(N^3)，我们总共有O(N^2)个状态，每个节点最多对对应N个邻接节点。代码如下：
No comments:
Post a Comment