带节点状态约束的最小非完全生成树相关算法与文献查询

• 节点属性依赖最小生成树
• 状态依赖边权生成树优化
• 节点配置与生成树联合优化
• 边权由节点颜色决定的着色最小生成树
• 图上双层组合优化问题
• 带节点状态的Steiner树

• 双层优化建模：该问题属于典型的双层组合优化问题，上层决策每个节点的颜色选择，下层求解对应边权配置下的最小生成树，总优化目标是最小化最终生成树的总权重。节点颜色可选数量少的小规模场景可以用分支定界法求精确解，大规模场景可结合元启发式算法（如遗传算法、模拟退火）搭配每轮的最小生成树快速求解得到近似最优解。
• 特殊性质下的近似算法：如果边权重与两端节点颜色的映射关系满足单调性、次模性等特殊性质，已有研究证明可以通过贪心框架得到近似比可控的解，可检索「次模边权 最小生成树 节点配置」相关内容。
• 参数化最小生成树变体：该问题可以归为多参数离散化的参数化最小生成树问题，常规参数化MST的边权是连续参数的函数，你的场景下参数为每个节点的离散颜色变量，参数化MST的剪枝、枚举框架可以直接迁移用于该问题的效率优化。
• 整数规划求解：小规模场景可以直接建模为混合整数线性规划问题求解：用0-1变量表示每个节点的颜色选择，用辅助变量关联两端节点颜色与对应边的权重，再叠加最小生成树的标准整数规划约束即可，可直接调用Gurobi、Cplex等商用求解器求解。

你之前尝试的按节点状态复制多份的建模思路可以调整适配需求：不需要强制遍历所有副本节点，只需要给同一个原始节点的所有颜色副本之间连接权重为0的边，同时约束每个原始节点恰好有一个副本被纳入生成树，即可转化为标准的 Steiner 树问题，未被选中的颜色副本会自动被排除在最优结构外，相关内容可以检索「带节点状态的Steiner树」关键词。

内容的提问来源于stack exchange，提问作者SomeoneHere