基于无数据神经网络( dNNs )的图论环覆盖变体研究：从理论构建到优化验证

这篇开创性论文探索了图论中环覆盖（Cycle Cover）变体的新型求解范式，作者团队创新性地采用无数据神经网络（dNNs）框架，为VDk+CC、VDk+CCD等变体构建了可微分函数体系，通过反向传播机制实现组合优化，突破了传统依赖数据训练的机器学习局限，为网络设计和生物信息学等领域提供了算法新思路。

　　

研究亮点

问题陈述

本节正式定义本文研究的核心问题：VDk⁺CC（顶点k⁺环覆盖）、VDk⁺CCD（有向图版本）、VDk⁺CCO（带约束优化）及其衍生变体。

定义1

顶点环覆盖(VCC)：给定图G=(V,E)，寻找一组覆盖所有顶点的子图循环结构，且每个顶点仅属于单一循环。

示例1

循环集合C={{v₁,v₂,v₃}, {v₁,v₃,v₅,v₄}, {v₄,v₅,v₆}}构成典型VCC解。

研究进展

现有成果表明，无向图VDCC可通过多项式时间转化为完美匹配问题求解，而有向图版本同样存在高效转化算法。

环覆盖变体建模

我们为每种变体定制了独特的dNNs架构：

1. 1.

   将离散约束编码为可微分损失函数

2. 2.

   利用全1向量e_n作为固定输入

3. 3.

   通过θ参数空间探索最优解

结论

本研究成功构建了针对VDk⁺CC系列问题的微分函数体系，并严格证明：当且仅当获得问题解时，函数值达到全局最小。这种"无数据驱动"的优化范式，为组合优化领域提供了媲美AlphaGo的创新方法论。

二次结论

未来工作将探索dNNs在蛋白质相互作用网络和交通流优化等生命科学/工程领域的应用潜力。