- 题目描述
- 思路
- 动态规划
- Python实现
- Java实现
题目描述
猫和老鼠
思路 动态规划
根据题意，猫和老鼠都按照最优策略进行游戏。
博弈论有三个状态：必胜状态、必败状态和必和状态。
- 对于特定状态，如果游戏已经结束，根据结束时的状态决定必胜、必败和必和状态。
- 如果分出胜负，特定状态对于获胜方为必胜状态，对于落败方为必败状态；
- 如果是平局，则该特定状态对于双方都是必和状态。
- 从某一个特定状态开始，如果当前玩家存在一种 *** 作将使对方玩家变为必败状态，则当前玩家可以选择该 *** 作，所以该特定状态对于当前玩家为必胜状态。
- 从某一个特定状态开始，如果当前玩家的所有 *** 作都将使对方玩家变为必胜状态，则当前玩家无论怎么 *** 作，都会输，所以该特定状态对于当前玩家为必输状态。
- 从某一个特定状态开始，如果当前玩家的所有 *** 作都不能将对方玩家变为必败状态，但是存在一种 *** 作使状态变为必和状态，则当前玩家可以选择该 *** 作，所以该特定状态下对于当前玩家为必和状态。
博弈问题通常使用动态规划求解。但是因为数据规模的原因，这么做会导致超时。
使用三维数组dp表示状态，dp[mouse][cat][turns]表示老鼠位于结点mouse，猫位于cat，游戏已经进行了turns轮的状态开始，猫和老鼠都按照最优策略的情况下的游戏结果。假设图中的节点数为n，则有0<=mouse,cat
边界条件包括三种情况： - 如果mouse=0，则老鼠获胜，因此不论cat和turns是多少都有dp[0][cat][turns]=1；
- 如果cat=mouse，猫和老鼠占据相同的结点，猫获胜，所以不论mouse、cat和turns是多少，都有dp[mouse][cat][turns]=2，但是猫不能进入洞中，即猫不能进入结点0，所以当mouse为0时，一定有cat≠mouse。
- 如果turns>=2n(n-1)，则平局。这主要是因为，游戏开始后，老鼠和猫的可以移动的位置分别为n和n-1，轮到移动的一方共有2种可能，因此游戏所有可能出现的局面有2n(n-1)。当游戏进行了2n(n-1)轮时，必然存在至少一个猫和老鼠重复经过的局面。所以必和。
由于老鼠先开始移动，所以turns为偶数时老鼠移动，turns为奇数时，猫移动。
如果轮到老鼠移动，则对于老鼠从当前节点移动一次后可能到达的每个结点，进行如下 *** 作： - 如果存在一个结点，老鼠到达该节点后，可以获胜，则老鼠在移动到这个节点前的当前状态为必胜状态。
- 如果老鼠到达任何节点后的状态都不是老鼠的必胜状态，但是存在一个结点，老鼠到达该节点后，可以平局，则老鼠在到达该节点后为必和状态，因此在老鼠移动到这个节点前的当前状态为必和状态。
- 其他情况下，老鼠在移动之前的当前状态为必败状态。
如果轮到猫移动，对于猫从当前结点移动一次之后可能到达的每个结点，有如下 *** 作： - 如果存在一个节点，猫到达该节点后，猫可以获胜，则猫到达该节点之后的状态为必胜状态，因此在猫移动之前的当前状态为猫的必胜状态；
- 如果猫到达任何节点后都不是猫的必胜状态，但是存在一个节点，猫到达该结点后，结局为平局，猫到达该结点后的状态为双方的必和状态，因此猫仔移动之前的当前状态为必和状态。
- 如果猫到达任何节点后的状态都不是猫的必胜状态或必和状态，则都必败，猫在移动之前的当前状态为猫的必败状态。
具体实现时，由于移动策略相似，可以使用一个函数实现移动策略，根据游戏已进行的轮数的奇偶性决定当前轮到的玩家。
因为老鼠的可能的位置有n个，猫的可能位置有n-1个，游戏最大轮数为2n(n-1)。所以动态规划状态数为 O ( n 4 ) O(n^4) O(n4)，每个状态需要O(n)的时间计算状态值，所以总的时间复杂度为 O ( n 5 ) O(n^5) O(n5)，超出时间限制。
DRAW = 0
MOUSE_WIN = 1
CAT_WIN = 2
class Solution:
def catMouseGame(self, graph: List[List[int]]) -> int:
n = len(graph)
dp = [[[-1] * (2 * n * (n - 1)) for _ in range(n)] for _ in range(n)]
def getResult(mouse: int, cat: int, turns: int) -> int:
if turns == 2 * n * (n - 1):
return DRAW
res = dp[mouse][cat][turns]
if res != -1:
return res
if mouse == 0:
res = MOUSE_WIN
elif cat == mouse:
res = CAT_WIN
else:
res = getNextResult(mouse, cat, turns)
dp[mouse][cat][turns] = res
return res
def getNextResult(mouse: int, cat: int, turns: int) -> int:
curMove = mouse if turns % 2 == 0 else cat
defaultRes = MOUSE_WIN if curMove != mouse else CAT_WIN
res = defaultRes
for next in graph[curMove]:
if curMove == cat and next == 0:
continue
nextMouse = next if curMove == mouse else mouse
nextCat = next if curMove == cat else cat
nextRes = getResult(nextMouse, nextCat, turns + 1)
if nextRes != defaultRes:
res = nextRes
if res != DRAW:
break
return res
return getResult(1, 2, 0)
class Solution {
static final int MOUSE_WIN = 1;
static final int CAT_WIN = 2;
static final int DRAW = 0;
int n;
int[][] graph;
int[][][] dp;
public int catMouseGame(int[][] graph) {
this.n = graph.length;
this.graph = graph;
this.dp = new int[n][n][2 * n * (n - 1)];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Arrays.fill(dp[i][j], -1);
}
}
return getResult(1, 2, 0);
}
public int getResult(int mouse, int cat, int turns) {
if (turns == 2 * n * (n - 1)) {
return DRAW;
}
if (dp[mouse][cat][turns] < 0) {
if (mouse == 0) {
dp[mouse][cat][turns] = MOUSE_WIN;
} else if (cat == mouse) {
dp[mouse][cat][turns] = CAT_WIN;
} else {
getNextResult(mouse, cat, turns);
}
}
return dp[mouse][cat][turns];
}
public void getNextResult(int mouse, int cat, int turns) {
int curMove = turns % 2 == 0 ? mouse : cat;
int defaultResult = curMove == mouse ? CAT_WIN : MOUSE_WIN;
int result = defaultResult;
int[] nextNodes = graph[curMove];
for (int next : nextNodes) {
if (curMove == cat && next == 0) {
continue;
}
int nextMouse = curMove == mouse ? next : mouse;
int nextCat = curMove == cat ? next : cat;
int nextResult = getResult(nextMouse, nextCat, turns + 1);
if (nextResult != defaultResult) {
result = nextResult;
if (result != DRAW) {
break;
}
}
}
dp[mouse][cat][turns] = result;
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）