从子网格向外扩展以最大化边值的图问题是否有对应名称与算法？

你的问题属于增量式最大权连通子图扩展问题，也可归类为收益驱动的图扩张场景，已有成熟解决方案：

• 增量式最大生成树变种：如果目标是构建包含起始节点、总边权最大的连通子图，最大生成树是基础框架。但普通贪心（每次选当前最优边）会短视错过高价值边，你可以调整为带全局收益预估的增量生成策略，每次评估扩展路径的总潜在收益而非单次边际收益。
• 分支定界算法：枚举可能的扩展路径，剪去边际收益为负或不可能超越当前最优解的分支，能有效避免贪心的局限性，找到全局最优的扩展顺序。
• 最小割模型（最大权闭合子图）：将问题转化为最小割问题求解，能直接得到全局最优的子图扩展结果——不需要逐步迭代，一次性算出哪些边值得捕获。

完全可以用Dijkstra或A*算法解决，核心是把最大化收益转化为最小化等效成本，具体做法：

1. 成本反转转化：把每条边的权值取反，此时“最大化总边权”等价于“最小化总负边权”。将当前子图视为一个超级源点，用Dijkstra算法寻找从源点到各节点的最短路径（即总负权最小，对应原边权总和最大）。这样就能找到需要通过低价值边连接的高价值边的净收益：比如那条权值20的边，计算路径上所有前置低价值边的总和，用20减去这个总和，若结果为正，就比直接选12的边更划算。
2. 自定义成本函数：你提到的“边值减去路径段长度”思路是可行的，但这里的“路径段长度”应该替换为路径上所有未被当前子图包含的边的权值总和——也就是为了获取目标高价值边，必须先捕获的低价值边的总权值。此时扩展的净收益 = 目标边权值 - 前置边总权值，当净收益>0时，扩展就是划算的。
3. A*的优化：在Dijkstra基础上加入启发式函数，比如预估当前节点到所有未捕获高价值边节点的最大可能净收益，能大幅减少搜索范围，更快找到最优扩展路径。

不要只关注单次扩展的即时收益，要评估扩展到某个节点后能解锁的所有高价值边的总潜在收益。比如为了获取20的边，即使前置步骤的边际收益低，但只要总潜在收益（20 - 前置边总和）高于当前单次选12的收益，就值得优先执行。

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