标题： 计算警察在警察对赌徒游戏中最优策略 显示英文标题

标题： Computing optimal strategy for cop in the game of Cop v.s. Gambler

摘要： 我们提出了两种高效的算法，用于计算在警察与赌徒游戏中警察的最优策略，其中赌徒的策略不是最优的，但被警察所知。 第一个算法类似于单源最短路径问题的Bellman-Ford算法，运行时间为$O(|V(G)||E(G)|)$。 第二个类似于Dijkstra算法，运行时间为$O(|E(G)|+|V(G)|\log |V(G)|)$。 与彼此相比，它们分别更适合于稀疏图和密集图。 显示英文摘要

摘要： We present two efficient algorithms that compute the optimal strategy for cop in the game of Cop v.s. Gambler where the gambler's strategy is not optimal but known to the cop. The first algorithm is analogous to Bellman-Ford algorithm for single source shortest path problem and runs in $O(|V(G)||E(G)|)$ time. The second is analogous to Dijkstra's algorithm and runs in $O(|E(G)|+|V(G)|\log |V(G)|)$ time. Compared with each other, they are more suitable for sparse and dense graphs, respectively.