基于强化学习的最大公共诱导子图(Maximum Common Induced Subgraph,MCIS)算法在处理历史搜索中低频出现的顶点时存在局限,难以评估其真实重要性并进行有效探索。为此,提出一种基于动作与环境反馈的前向预测方法。动作反馈通过奖励机制...基于强化学习的最大公共诱导子图(Maximum Common Induced Subgraph,MCIS)算法在处理历史搜索中低频出现的顶点时存在局限,难以评估其真实重要性并进行有效探索。为此,提出一种基于动作与环境反馈的前向预测方法。动作反馈通过奖励机制量化分支顶点的剪枝效果,环境反馈则用双域个数来表征待搜索子图的大小。前向预测通过单边采样选择顶点模拟分支,并根据反馈确定最佳顶点。实验结果表明,新算法McSplitLA比McSplitDAL多解决7个算例,平均求解时间减少11.2%~17.9%,有效提高了剪枝率并优化了探索方向。展开更多
文摘基于强化学习的最大公共诱导子图(Maximum Common Induced Subgraph,MCIS)算法在处理历史搜索中低频出现的顶点时存在局限,难以评估其真实重要性并进行有效探索。为此,提出一种基于动作与环境反馈的前向预测方法。动作反馈通过奖励机制量化分支顶点的剪枝效果,环境反馈则用双域个数来表征待搜索子图的大小。前向预测通过单边采样选择顶点模拟分支,并根据反馈确定最佳顶点。实验结果表明,新算法McSplitLA比McSplitDAL多解决7个算例,平均求解时间减少11.2%~17.9%,有效提高了剪枝率并优化了探索方向。
