求和接近给定值的顶点加权图的连通子图的算法
Algorithm for finding connected subgraph of a vertex weighted graph with a sum close to a given value
给定一个顶点加权图 G（如下所示）、该图中的一个顶点 v 和一个整数值 x，是否有一种已知的算法可以找到 G 的连通子图，使得目标顶点位于该子图中图和这个子图的权重之和尽可能接近x？此外，如果无法找到 x 的精确匹配，算法仍应尽可能 return 个最接近 x 的子图。
下图给出了一些示例：
v = F, x = 12。A,B,F,I 和 F,G,C,D 是解。
v = C, x = 16。C,D,E,H 是解。
对我来说，寻找解决方案就像是背包问题的一个变体，额外的限制是背包中的所有物品必须形成一个连通图。
一种方法是检查所有可能包含 v 的子图并搜索最大权重（达到您的 x）：
您可以使用某种贪婪算法，从节点 v 开始，然后逐个添加相邻节点，跟踪总子图权重。如果你到达 x，你就完成了，如果超过 x，你必须为你的子图回溯和 select 其他节点。在整个算法过程中，您会跟踪您的 "best" 子图，因此如果最终没有找到精确解，您仍然有最佳近似值。
您可以选择节点的顺序以使用启发式方法添加到您的子图中，例如最适合，但这只会影响 运行 时间，不会影响结果质量..
给定一个顶点加权图 G（如下所示）、该图中的一个顶点 v 和一个整数值 x，是否有一种已知的算法可以找到 G 的连通子图，使得目标顶点位于该子图中图和这个子图的权重之和尽可能接近x？此外，如果无法找到 x 的精确匹配，算法仍应尽可能 return 个最接近 x 的子图。
下图给出了一些示例：
v = F, x = 12。A,B,F,I 和 F,G,C,D 是解。
v = C, x = 16。C,D,E,H 是解。
对我来说，寻找解决方案就像是背包问题的一个变体，额外的限制是背包中的所有物品必须形成一个连通图。
一种方法是检查所有可能包含 v 的子图并搜索最大权重（达到您的 x）：
您可以使用某种贪婪算法，从节点 v 开始，然后逐个添加相邻节点，跟踪总子图权重。如果你到达 x，你就完成了，如果超过 x，你必须为你的子图回溯和 select 其他节点。在整个算法过程中，您会跟踪您的 "best" 子图，因此如果最终没有找到精确解，您仍然有最佳近似值。
您可以选择节点的顺序以使用启发式方法添加到您的子图中，例如最适合，但这只会影响 运行 时间，不会影响结果质量..