arXiv:2502.03669v1 交叉公告类型： 摘要：AI方法，如生成模型和强化学习，最近已被应用于组合优化(CO)问题，尤其是NP难问题。本文将基于GPU的方法与基于经典CPU的方法在最大独立集(MIS)问题上进行了比较。在标准图家族的实验中显示，基于AI的算法未能超越最先进的经典求解器KaMIS在单个CPU上的解决方案质量，在许多情况下甚至无法匹配其解决方案质量。一些基于GPU的方法甚至与基于度数的贪心算法类似，即便使用了局部搜索等后处理技术，基于AI的方法仍然不如基于CPU的求解器。 我们将开发一种新的分析模式来揭示，非回溯AI方法，例如基于GFlowNets的LTFT，最终推理方式与最简单的基于度数的贪心方法类似，并且比KaMIS更差。我们还发现，基于经典CPU的算法，尤其是KaMIS，在稀疏随机图上的性能很强，这似乎驳斥了Coja-Oghlan与Efthymiou（2015年）提出的高效算法的已知上界猜想。