Games on Graphs: A Time-Efficient Algorithm for Solving Finite Reachability and Safety Games

近年来，由于在经济、政治和流行病学等应用中的相关性，学术界对于图游戏的兴趣日益增长。本文旨在全面详述设计决策，以开发一种高效解决图上有限可达性和安全游戏的算法。本工作的主要贡献在于引入一种新颖的算法，通过利用它们的固有二元性，有效地解决了可达性和安全游戏。所提出的算法的性能是通过随机化测试框架进行严格评估的，以传统方法为对照。本文的结构如下：首先，我们为读者提供可达性和安全游戏的理论概述，接着深入讨论了游戏场地的构建。然后，给出了可达性和安全游戏的正式定义，并回顾了传统算法的解决方法。随后，介绍了多角度算法及其优化。最后，通过广泛的实验和对结果的全面讨论来总结本文。

本论文旨在全面详细地介绍设计决策，以开发一种时间高效的算法，用于解决有限可达性和图形安全游戏。该算法的主要贡献是引入了一种新颖的算法，通过利用可达性和安全游戏的内在二元性，有效地解决了这两种游戏。

该论文提出了一种新的算法，通过利用可达性和安全游戏的内在二元性，将这两种游戏有效地解决。相比传统方法，该算法具有更高的时间效率。

该论文的亮点包括：1.使用随机测试框架对提出的算法进行了严格评估；2.提出的算法相较于传统算法具有更高的时间效率；3.该算法可以同时有效地解决可达性和安全游戏；4.通过详细介绍游戏的构建，使读者了解游戏的理论基础；5.提供了大量实验结果和讨论，以及对未来工作的展望。

近年来，对于图形游戏的研究越来越受到关注，特别是在经济、政治和流行病学等应用领域。与本论文相关的研究包括：1.《Solving Parity Games in Practice》；2.《On the Complexity of Reachability Problems for Continuous-Time Markov Decision Processes》；3.《Solving Mean-Payoff Games on Graphs: Simplex Algorithm and Combined Strategies》等。