求和接近给定值的顶点加权图的连通子图的算法
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" 子图,因此如果最终没有找到精确解,您仍然有最佳近似值。
您可以选择节点的顺序以使用启发式方法添加到您的子图中,例如最适合,但这只会影响 运行 时间,不会影响结果质量..