几何感知MCTS：组合几何极值问题求解新突破

组合几何中的极值问题要求寻找满足严格全局几何约束的点配置方案，传统精确求解器面临组合爆炸难题，而标准强化学习和Transformer模型则受限于稀疏奖励和二次令牌消耗限制。为解决这些瓶颈，研究团队开发了几何感知蒙特卡洛树搜索（MCTS）框架。该框架通过增量更新可行动作空间严格执行几何约束，针对共线点集合约束（如经典“无三点共线”问题），将约束检查复杂度从O(n³)降至O(n²)。研究还通过两种方式利用几何对称性提升搜索效率：节点扩展时的规范剪枝降低分支因子，对称批量转换加速发现优质配置。实验表明，该方法在六个测试问题中的五个上取得了当前最佳计算结果。在最大无三点共线问题中，对82≤n≤119的网格发现了规模约1.8n的配置；在最小完备集问题中，发现了规模约0.95n的配置，为测试网格提供了新的上界。这项工作确立了几何感知MCTS作为组合几何中新配置发现的高度适应性框架。