面向反恐安全博弈的连通因子理论与应用

This project will study well-known Matthews-Sumner conjecture using computer algorithms, and wish to give out positive part or whole answer to this conjecture, and also research its related problems, which will lead to an important affect in graph theory circle. In this project, we research even [a, b]-factors and star decomposition problems droved by real-life problems, and their related problems, will obtain several new results which improve these known ones. We will explore anti-terrorism game theory models for real-life city common scenarios using connected 2-factors, even [a, b]-factors and star decomposition techniques and algorithms and so on, and design new optimal solutions for anti-terrorism resources and new patrol schedule mechanism. In real-life, consider various uncertainties （including effectness errors, execution errors, cooperation errors and observation errors and so on）to affect anti-terrorism resources assignment strategies. These researches are to find applications for graph theory and new methods and tools for the study of security game theory and so are of important theory meaning and applied values.

本项目对长期未解决的世界著名Matthews-Sumner猜想进行攻关，即进行计算机算法设计与分析，给出其正面理论证明（部分或者全部）或者给出反例，同时研究与这个猜想相关的问题， 这个问题的解决将对世界图论界产生重大影响； 研究由实际问题驱动的图论中的偶[a, b]-因子和星因子分解等问题以及他们的相关问题， 希望得到几个新结果并改进已知结果； 研究针对城市公共场合的反恐安全博弈模型，和利用连通2-因子、偶[a, b]-因子和星因子分解理论和算法等方法设计新反恐安全博弈模型中的反恐资源优化分配方案以及巡逻路线安排机制；研究在实际环境中，如何考虑各种不确定性(包括效用误差、执行误差、协调误差以及观测误差等）对安全资源分配策略算法的影响。这些研究为图论找到了新的应用， 为安全博弈论找到新的设计方法和工具，因此具有重大理论价值和应用价值。

本项目研究了无爪图中的世界著名Matthews-Sumner猜想并证明了每一个具有最大度至少3n/4的边着色n阶临界图有连通2-因子，借助于图论理论成果来解决当今反恐安全中迫在眉睫的相关问题进行研究，如安全防守资源数量的受限问题，大规模环境寻求保护问题以及恐怖分子行为难以预测问题等等。为了更好地解决上述难题，本项目组利用博弈论、整数规划以及概率论统计等数学基础理论工具来分析及模拟敌我双方的交互行为以及完成资源优化模型的搭建。同时，在根据实际情况下制定优化目标以及相应的约束条件之后，针对模型研究具体的求解方案。事实上，大部分的求解问题均面临着NP难问题，因此，本项目组提出了基于double-oracle、列生成等大量的启发式近似算法，该算法可以提高求解速度的同时保证求解质量。另外，本项目组还采用了目前较为高效的机器学习算法来训练模拟恐怖分子的行为策略，这一举措为我们防守策略的制定提供了更为有效的支撑。综上，本项目组围绕酒驾查询、城管督查非法占地营业、选举保护以及恐怖分子持续性攻击等实际问题展开一系列的相关研究，并取得了不俗的成果，该成果为反恐安全问题在理论分析方面提供了强有力的支撑条件。