用规划算法解决图论中抓匪问题，判断最少需几名警探能必擒匪。
Domain Design for the Cops and Robbers Problem
- 将抓匪过程建模为非确定性规划问题，模拟所有可能的警探策略。
- 通过现代规划器验证图是否满足k警探必胜条件，支持多类图结构扩展。
- 适合对图论博弈、自动推理感兴趣的科研人员参考。
Cops and Robbers 是图论中的经典问题：在无向图上，一名或多名警探与一名匪徒轮流移动，目标是让至少一名警探与匪徒位于同一顶点。若存在一个有限步数内无论初始位置如何都能捕获匪徒的策略，则称该图为“k-警探必胜”（k-copwin）。本文将判定图是否为k-警探必胜的问题转化为非确定性规划问题，利用最先进的规划引擎求解。警探行动采用非确定性移动以覆盖所有可能策略，而匪徒行动为确定性移动。同时，本文还引入了图论文献中的多种变体进行扩展。
原文摘要 · Abstract (English)
Cops and Robbers is a well-studied problem in graph theory. The setting consists of a robber and one or more cops placed on an undirected graph. Taking turns moving throughout the graph, the cops try to capture the robber. The property of interest is whether $k$ cops suffice to ensure at least one cop occupies the same vertex as the robber, after a finite number of turns, given any configuration of their initial placement; if successful, the graph is referred to as ``$k$-copwin''. In this work, we cast the problem of determining whether a graph is $k$-copwin as a non-deterministic planning problem and use state-of-the-art planners to compute this property. The cop movement is cast as non-deterministic movement (to capture all possible strategies), while the robber movement is deterministic in nature. We also extend the base model using several variations from the graph theory literature.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。